What is an example of an infinite decidable language $L$, such that $L \subseteq \overline { A_{TM}}$ (which is known to be not Turing Recognizable)?

And of coures some evidence that L is indeed decidable and a subet as required

  • 1
    $\begingroup$ Any finite subset $L$ would be decidable. You probably want to require $L$ be infinite. $\endgroup$ – fade2black Nov 30 '17 at 6:36
  • $\begingroup$ @fade2black - any finite $L$ is decidable but not all are subsets of $\overline { A_{TM}}$ $\endgroup$ – Joezer Nov 30 '17 at 6:46
  • $\begingroup$ You ask "What is an example of a decidable language $L$...". The answer: take first $10$ elements of $\overline{A_{TM}}$ and define it as $L$. This language $L$ is decidable. $L$ is clearly a subset of $\overline{A_{TM}}$ isn't it? $\endgroup$ – fade2black Nov 30 '17 at 6:50
  • $\begingroup$ @fade2black - You are right, I will update the question to require an infinite language $\endgroup$ – Joezer Nov 30 '17 at 7:00

Fix a special TM $M_d$ which infinitely loops on any input $x$. In other words, $M_d$ does not care about input $x$ and always infinitely loops on any input. Such a TM could consist of a single state and instructions such as $\delta(q_0, a) = (q_0,a)$ for all input symbols $a \in \Sigma$, which tells $M$ to stay in the same state and never move the head. So, given its description $\langle M \rangle$ it is easy to recognize this machine by inspecting its states and instructions.

Since $M_d$ never halts on any input $x$ the following language must be infinite

$$L = \{\langle M_d,x \rangle \mid x \in \Sigma^*, M_d \text{ is the fixed TM} \}$$. This language is also a subset of $\overline{A_{TM}}$ since $M_d$ never halts on any input $x$. Thus, if we are given $\langle M_i,x \rangle$ we simply decide by checking whether $i=d$, i.e., whether $M_i$ is the same as $M_d$ by inspecting $M_i$'s states and instructions meaning $L$ is decidable.


A Turing machine $M$ whose head always moves right and never modifies the tape is essentially a deterministic finite-state automaton (https://en.wikipedia.org/wiki/Read-only_right_moving_Turing_machines), and it is decidable if $M$ accepts a given input $w$. Moreover, we can easily check if a Turing machine description $\langle M \rangle$ describes a read-only right-moving Turing machine.

Therefore the language

$$\{ \langle M,w \rangle \mid M \text{ is a read-only right-moving TM that does not accept } w\}$$

is a subset of $\overline{A_{\mathsf{TM}}}$ that is decidable. It is easy to see that this language is infinite, as the set of read-only right-moving Turing machine is infinite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.