HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Language of Turing machines that loop on all inputs, recognizable?

Submitted by: @import:stackexchange-cs··
0
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.

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:

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 accept


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,

M_w(y) =
   erase the input y
   write w on the input tape
   simulate M on w


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).

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 accept
M_w(y) =
   erase the input y
   write w on the input tape
   simulate M on w

Context

StackExchange Computer Science Q#43185, answer score: 5

Revisions (0)

No revisions yet.