2
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .