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.

## Property

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.

## Trivial Properties

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.

## Non-Trivial Properties

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.

### Ex1

Property is . Some TMs accept more than strings and some do not.

### Ex2

Property is . Some TMs accept exactly strings and some do not.

### Ex3

Property is . is a specific string, and some TMs accept it and some do not.

### Ex4

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 .

### Ex5

This is not a Turing Machine description and thus not a property.

### Ex6

Halting doesn’t provide info whether a string is in the language or not. Property is is a TM.

### Ex7

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.

### Ex8

Property is is a TM that accepts palindromes.