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).

Ex5

    \begin{equation*} \{<M, x>: M \text{ is a TM, $x$ is a string, and there exists a TM, $N$, such that } x \notin L(M) \cap L(N) \} \end{equation*}

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

Ex6

    \begin{equation*} \{<M>: M \text{ is a TM, and there exists an input whose length is less than $100$, on which $M$ halts } \} \end{equation*}

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

Ex7

    \begin{equation*} \{<M>: M \text{ is a TM, and } |M| < 1000 \} \end{equation*}

Length of the string encoding of a machine does not provide info whether a string is in the language or not. Property is M is a TM.

Ex8

    \begin{equation*} \{<M>: M \text{ is a TM, and $M$ accepts only palindromes} \} \end{equation*}

Property is M is a TM that accepts palindromes.

Leave a Reply

Your email address will not be published. Required fields are marked *