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
    Commented Nov 30, 2017 at 6:36
  • $\begingroup$ @fade2black - any finite $L$ is decidable but not all are subsets of $\overline { A_{TM}}$ $\endgroup$
    – Joezer
    Commented Nov 30, 2017 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
    Commented Nov 30, 2017 at 6:50
  • $\begingroup$ @fade2black - You are right, I will update the question to require an infinite language $\endgroup$
    – Joezer
    Commented Nov 30, 2017 at 7:00

2 Answers 2


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 and acknowledge you have read our privacy policy.

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