patternMinor
Language of Turing machines that loop on all inputs, recognizable?
Viewed 0 times
inputsalllooprecognizablelanguagethatmachinesturing
Problem
Prove that the language Loop Turning Machine = { | M is a TM that loops on all inputs} is recognizable.
I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or reject. Do I need to establish a decider?
EDIT:
Can I say that a halting Turing Machine $M$ is a machine for which exists a word $w$ such that $M$ halts on $w$?
This makes the language recognizable but the machine may go on forever if executed.
I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or reject. Do I need to establish a decider?
EDIT:
Can I say that a halting Turing Machine $M$ is a machine for which exists a word $w$ such that $M$ halts on $w$?
This makes the language recognizable but the machine may go on forever if executed.
Solution
$L$ isn't recognizable. We'll first establish a couple of preliminary results
I. $\overline{L}$ is recognizable
The complement of $L$,
$$
\overline{L}=\{\langle M\rangle\mid M \text{ halts on at least one input}\}
$$
is recognizable. Define a recognizer TM as follows:
It should be clear that $R$ accepts all and only those $\langle M \rangle$ for which $\langle M \rangle\in \overline{L}$ and so $\overline{L}$ is recognizable. Now if $L$ were also recognizable, then we could use the two recognizers to make decider for $L$, which brings us to our second result.
II. L is undecidable
If $L$ were decidable, then $\overline{L}$ would also be, and conversely. If that were the case, we could define a reduction from the known undecidable language
$$
HALT = \{(\langle M\rangle \mid M \text{ halts on input }w\}
$$
to $\overline{L}$ by the mapping
$$
(\langle M\rangle, w)\rightarrow M_w
$$
where, as babou has already noted,
Now observe that $M$ halts on $w$ $\Longleftrightarrow$ $M_w$ halts (on every input $y$, in fact) $\Longleftrightarrow$ $M_w\in \overline{L}$. In summary, if $L$ were decidable, then we could $L$'s decider (reversing the roles of accept and reject) to decide the halting problem, a contradiction.
Now we can show that $L$ is not recognizable. If it were, then, using (I) we could conclude that $L$ was decidable, a contradiction to result (II).
I. $\overline{L}$ is recognizable
The complement of $L$,
$$
\overline{L}=\{\langle M\rangle\mid M \text{ halts on at least one input}\}
$$
is recognizable. Define a recognizer TM as follows:
R() =
for n = 1, 2, 3, ...
for each x in {x_1, x_2, ... , x_n} // in some canonical order
run M on x for one move
if M halts
return acceptIt should be clear that $R$ accepts all and only those $\langle M \rangle$ for which $\langle M \rangle\in \overline{L}$ and so $\overline{L}$ is recognizable. Now if $L$ were also recognizable, then we could use the two recognizers to make decider for $L$, which brings us to our second result.
II. L is undecidable
If $L$ were decidable, then $\overline{L}$ would also be, and conversely. If that were the case, we could define a reduction from the known undecidable language
$$
HALT = \{(\langle M\rangle \mid M \text{ halts on input }w\}
$$
to $\overline{L}$ by the mapping
$$
(\langle M\rangle, w)\rightarrow M_w
$$
where, as babou has already noted,
M_w(y) =
erase the input y
write w on the input tape
simulate M on wNow observe that $M$ halts on $w$ $\Longleftrightarrow$ $M_w$ halts (on every input $y$, in fact) $\Longleftrightarrow$ $M_w\in \overline{L}$. In summary, if $L$ were decidable, then we could $L$'s decider (reversing the roles of accept and reject) to decide the halting problem, a contradiction.
Now we can show that $L$ is not recognizable. If it were, then, using (I) we could conclude that $L$ was decidable, a contradiction to result (II).
Code Snippets
R(<M>) =
for n = 1, 2, 3, ...
for each x in {x_1, x_2, ... , x_n} // in some canonical order
run M on x for one move
if M halts
return acceptM_w(y) =
erase the input y
write w on the input tape
simulate M on wContext
StackExchange Computer Science Q#43185, answer score: 5
Revisions (0)
No revisions yet.