Graph properties: definability and decidability [This is a side question to Supervenience in mathematics.]
There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not MSO-, TC-, or LFP-definable, but maybe in another, even more expressive language.
To claim that a graph property is not definable at all, would mean, that there is no language (in the class of all languages) in which it is definable. But what is this class of all languages? Is it definable?
One doesn't have to be bothered by undefinable properties, because "whereof one cannot speak, thereof one must be silent" (Wittgenstein). But alas, there's an alternate way of defining graph properties: by Turing machines. 
One might try to identify the set of graph properties with the set of (equivalence classes of) Turing machines which take adjacency matrices as input, eventually halt, and give 0 or 1 as output, giving the same output for "isomorphic" matrices. 
This set of properties isn't decidable (because of the halting property), but it's definable. 

Does it make sense to ask, whether
  there are graph properties (as Turing
  machines) that are not definable in
  any conceivable (logical) language?

 A: Yes, but it's trivial.
For all graph properties prop, with p(.) defined by p(g) if and only if g has property prop, prop is definable in FO+p.
A: Almost any language I can think of (FO theories, etc) isinvariant under isomorphism, i.e. if $\cal A$ satisfies the sentence $\sigma$ then so does $h(\cal A)$ for any isomorphism $h$. Hence if a class of graphs is not closed under isomorphism, it will not be definable in any conceivable language.
(Of course, such classes of graphs would not be very interesting).
A: I, like gowers in the comments, don't think it is a question which have anything to do with graphs in particular, as soon as you define graph property to be something recognizable by a Turing machine. 
Indeed you can enumerate graphs by natural numbers (for example by enumerating  the possible adjacency matrices) Then the set of graphs having a given property in your sense is precisely a recursive set of natural numbers.
Now, for every recursively enumerable set A of natural numbers there  exists a polynomial p such that 
$$
x \in A \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0),
$$
which, afaiu, is a kind of a definition in a logical language you're after.
