4
$\begingroup$

Prove that the language Loop Turning Machine = { < M > | 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.

$\endgroup$
5
  • 2
    $\begingroup$ Turning $\mapsto$ Turing $\;\;\;\;$ $\endgroup$
    – user12859
    Jun 2, 2015 at 20:44
  • $\begingroup$ It sounds like a solution to the halting problem. $\endgroup$
    – babou
    Jun 2, 2015 at 21:03
  • 1
    $\begingroup$ @RickyDemer, unless it is a Turning machine, then it definitely loops on all inputs ;) ba-dum-ching. $\endgroup$ Jun 3, 2015 at 0:51
  • 2
    $\begingroup$ Does "loops" mean "runs forever" or "enters a cycle"? $\;$ $\endgroup$
    – user12859
    Jun 3, 2015 at 1:10
  • $\begingroup$ @RickyDemer "loop¨ is the informal, and not quite accurate, way of saying "does not halt". We should not use it, but we do all the time. $\endgroup$
    – babou
    Jun 3, 2015 at 9:21

4 Answers 4

5
$\begingroup$

$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(<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

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

$\endgroup$
4
  • $\begingroup$ This is proving that L is unrecognizable. I'm under the impression that it's indeed recognizable by reducability or the halting problem. I was looking at the complement having to halt on every input, but it only needs to be one input? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:28
  • $\begingroup$ @Sam. See my answer. The complement of $L$ is the set of all TM descriptions $\langle M\rangle$ that halt on at least one input. They don't have to halt on all inputs, just one or more. $\endgroup$ Jun 3, 2015 at 1:22
  • $\begingroup$ @RickDecker I'm a little confused by this answer because the book I'm using says that the language L is recognizable, but your proof shows that it is not. $\endgroup$
    – Yawn
    Jun 3, 2015 at 1:43
  • $\begingroup$ I have corrected my answer, contemplating a distinction that may clarify things. $\endgroup$ Jun 3, 2015 at 12:13
3
$\begingroup$

Note: obviously, here, "loops" must be understood as "does not halt".

Consider a machine $M$ and an input $w$. From that you can build a machine $M_w$ that, given any input, will just erase this input, replace it by $w$, and then will simply mimic $M$ on input $w$. Obviously $M$ loops on input $w$ iff $M_w$ loops on all inputs.

If the language $L_{\bar h}$ is recognizable, then we have a semi-decision procedure to know whether $M_w$ loops, hence whether $M$ loops on $w$. Since we also have a semi-decision procedure to check whether $M$ halts on $w$, by simply running it, we have a decision procedure for $M$ running on input $w$. This being true for any $M$ and any $w$, we have solved the halting problem.

So there seem to be a good chance that $L_{\bar h}$ might be there incognito. (I mean $L_{\bar h}$ is not recognizable)

$\endgroup$
6
  • $\begingroup$ This is using L halting as a decider for M? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:50
  • $\begingroup$ @Sam Not sure I understand what you mean. $\endgroup$
    – babou
    Jun 2, 2015 at 21:56
  • $\begingroup$ If L halting complement is recognizable then use it to determine if M is looping on string input w? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:58
  • $\begingroup$ Well, if $L$ is recognizable, then you can know whether machine $M$ will loop on input $w$ , for any $M$ and any$w$, in whatever finite time is necessary, if M is looping. Since running $M$ on $w$ also gives you a halting answer in finite time (when it halts, you can do both "in parallel" to get an answer in finite time from one computation or the other. $\endgroup$
    – babou
    Jun 2, 2015 at 22:13
  • $\begingroup$ So by contradictition using the halting problem. $\endgroup$
    – Yawn
    Jun 2, 2015 at 23:18
2
$\begingroup$

Here's a different proof that this language isn't recognizable, this time using self-referential TMs and the recursion theorem.

Suppose that your language is recognizable. Let $R$ be a recognizer for it. We'll assume that $R$ never rejects - we can do this by replacing any rejecting states of $R$ with states that loop infinitely. Therefore, if we run $R$ on a TM encoding $\langle M \rangle$, then $R$ accepts if $M$ loops on all inputs and $R$ loops of $M$ halts on any input.

So consider this self-referential TM:

$M$ = "On input $w$:

Use the recursion theorem to obtain $\langle M \rangle$.

Run $R$ on $\langle M \rangle$.

If $R$ accepts, accept $w$."

Now, either $M$ always loops or $M$ halts at least once. If $M$ always loops, then $R$ will accept $\langle M \rangle$, causing $M$ to halt - a contradiction! Otherwise, $M$ halts at least once. But that means that $R$ will loop on $\langle M \rangle$, causing $M$ to always loop - a contradiction!

The only bad assumption we made is that we had a recognizer for $L$, so our assumption was wrong and $L$ is not recognizable.

Hope this helps!

$\endgroup$
1
  • $\begingroup$ Very nice. Likely unknown to the OP, but the recursion theorem is a handy addition to any theorist's toolkit. $\endgroup$ Jun 4, 2015 at 1:45
1
$\begingroup$

A machine that necessarily loops (for all inputs) is a machine whose final states (accepting or rejecting) are unreachable.

There are two kinds of machines that behave this way: those that use a finite amount of tape (and repeat configurations forever), and those that don't. Encodings of the first kind form a language that is recognizable: you just have to keep track of the recurrence of configurations.

If you combine these two types of machines in one class, any language of their encodings will not be recognizable - as the other answers have shown.

For further discussion, check out this other question: Does a never-halting machine always loop?

$\endgroup$
6
  • $\begingroup$ Which makes it undecidable, but the language can still be recognizable right? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:08
  • $\begingroup$ So an approach to solving this problem is to assume a turing machine called Halt TM which is equal to a turning machine M where any input halts? The opposite of looping forever? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:24
  • $\begingroup$ @Sam. The logical negation of "runs forever on all inputs" is "halts on at least one input". $\endgroup$ Jun 2, 2015 at 21:32
  • $\begingroup$ @AndréSouzaLemos So if the final state is the initial state a path would exist to the final state? Using Rick Decker's negation, then at least one input would end the loop resulting in a halt inside of the final state? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:37
  • $\begingroup$ @AndréSouzaLemos Well my final state is L complement because it halts on at least one input. L complement must be in M because it takes ALL inputs right? $\endgroup$
    – Yawn
    Jun 2, 2015 at 21:47

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.