Property of the language of Turing Machines

Consider the following Turing Machine descriptions

$\begin{equation*} M_1 = \{ <M>: M \text{ is a TM that accepts strings of the type } 0^n1^n \} \end{equation*}$

$\begin{align*} M_2 = \{ <M>: M & \text{ is a TM that accepts strings which have equal number of 0s and 1s} \\ & \text{ and all the 1s lie after the 0s } \} \end{align*}$

$\begin{align*} M_2 = \{ <M>: M & \text{ is a TM that accepts strings which have equal number of 1s and 0s} \\ & \text{ and all the 0s lie before the 1s } \} \end{align*}$

Clearly, all three Turing Machines recognize the same language $0^n1^n$ . 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 $\mathcal{M}$ be the set of all TM descriptions. We say $P \subseteq \mathcal{M}$ is a property of the language of TMs, if for two TMS, $M_1$ and $M_2$ , $L(M_1) = L(M_2)$ implies that both belong to $P$ or neither belong to $P$ .

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

$\begin{equation*} \{ <M>: M \text{ is a TM} \} \end{equation*}$

This property is satisfied by all Turing Machines. This is considered a trivial property.

$\begin{equation*} \{ <M>: M \text{ is not a TM} \} \end{equation*}$

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

$\begin{equation*} \{<M>: M \text{ is a TM and } |L(M)| \leq 3\} \end{equation*}$

Property is $|L(M)| \leq 3$ . Some TMs accept more than $3$ strings and some do not.

Ex2

$\begin{equation*} \{<M>: M \text{ is a TM and } |L(M)| = 3\} \end{equation*}$

Property is $|L(M)| = 3$ . Some TMs accept exactly $3$ strings and some do not.

Ex3

$\begin{equation*} \{<M>: M \text{ is a TM, $N$ is a TM that halts on all inputs, and } <N> \in L(M) \} \end{equation*}$

Property is $<N> \in L(M)$ . $<N>$ is a specific string, and some TMs accept it and some do not.

Ex4

$\begin{equation*} \{<M>: M \text{ is a TM, $N$ is a TM that halts on all inputs, and } <M> \in L(N) \} \end{equation*}$

$<M> \in L(N)$ is not a property. Consider two TMs $M_1$ and $M_2$ . Say for some input, $M_1$ halts and rejects. For this input let $M_2$ run forever. Now these two machines still have the same language. However $<M_1> \in L(N)$ but $<M_2> \notin L(N)$ .