Consider the following Turing Machine descriptions
Clearly, all three Turing Machines recognize the same language . The way some TM is described is arbitrary. However, different TM descriptions can point to the same language. The latter is defined as the property of that language.
Let be the set of all TM descriptions. We say is a property of the language of TMs, if for two TMS, and , implies that both belong to or neither belong to .
In other words, a property is the essence of the equivalence of languages defined by Turing Machines. Note that, a property applies to the language of the Turing Machine and not its description.
This property is satisfied by all Turing Machines. This is considered a trivial property.
This property is satisfied by no Turing Machine. This is also considered a trivial property.
All other properties are considered non-trivial. For every non-trivial property there is some Turing Machine that belongs to it and some other Turing Machine that does not belong to it.
Property is . Some TMs accept more than strings and some do not.
Property is . Some TMs accept exactly strings and some do not.
Property is . is a specific string, and some TMs accept it and some do not.
is not a property. Consider two TMs and . Say for some input, halts and rejects. For this input let run forever. Now these two machines still have the same language. However but .
This is not a Turing Machine description and thus not a property.
Halting doesn’t provide info whether a string is in the language or not. Property is is a TM.
Length of the string encoding of a machine does not provide info whether a string is in the language or not. Property is is a TM.
Property is is a TM that accepts palindromes.