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