I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on some inputs. The language to be precise is $L=\{\langle M,w \rangle| \ M \text{is a turing machine and } w \text{ is a string M accepts} \}$. Let $D$ be the turing machine that recognises $L$. Inability of $D$ to halt on some inputs is due to the fact that there exist Turing Machine $M$ which do not halt on some input. Thus the reason for not halting is kind of recursive ( if I consider only this example ). I am still not able to understand in crux why a turing machine won't halt. But can't come up with language over $\{0,1\}$ which is turing recognisable but not decidable. What are all the reasons a Turing machine won't halt ?

  • $\begingroup$ The reason $D$ does not halt is because $D$ recognizes an undecidable language. If $D$ halted and recognized an undecidable language $L$ then it would decide $L$! $\endgroup$ – Tom van der Zanden Oct 15 '15 at 13:34
  • $\begingroup$ I'm the \langle \rangle fairy, here to let you know that $\langle, \rangle$ plays nicer with TeX than <, > does :) $\endgroup$ – Patrick Stevens Oct 16 '15 at 9:03

A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following:

while (true)

, then it will never halt!

The language $L$ goes over all possible machines $M$, and therefore it must encounter some machines that don't halt, for instance, the one stated above.

There is a deep difference between the reason the above machine doesn't halt (it is just programmed to do so), and the reason that any machine for $L$ will not halt–no machine for $L$ exists since that language is undecidable.

regarding your question about finding a more "natural" language that is undecidable, see Is there a “natural” undecidable language?. You may get some more intuition about undecidable languages here.

| cite | improve this answer | |
  • 1
    $\begingroup$ beautiful proof by example - I signed up to the site just to +1 such an elegant way of putting it $\endgroup$ – MD-Tech Oct 16 '15 at 8:41
  • $\begingroup$ Standard description of a Turing machine that never halts: DADDNDA; run with a blank tape $\endgroup$ – sdleihssirhc Oct 17 '15 at 7:56

A Turing machine doesn't halt if it never reaches a halting state. For example, it might keep moving its head to the right, never stopping. Or it might count $1,2,3,\ldots$, never halting. It doesn't need a reason not to halt.

What we know about the language $L$ is that there is no machine $T$ that satisfies the following two properties:

  1. If $\langle M,x \rangle \in L$ then on input $\langle M,x \rangle$, $T$ halts and outputs YES.
  2. If $\langle M,x \rangle \notin L$ then on input $\langle M,x \rangle$, $T$ halts and outputs NO.

How do we know that? Sipser proves it in his textbook. The naive attempt at deciding $L$, that is simulating $M$ on $x$, doesn't halt when the answer is NO; but there could be a completely different algorithm whose principle of operation is different and doesn't suffer from this problem. What Sipser shows (following Turing) is that no matter what you do, you cannot come up with a machine $T$ deciding $L$.

| cite | improve this answer | |
  • $\begingroup$ Maybe something else that $L$ being undecidable, but recognizable implies: while there is a recognizing machine $M$ for $L$ (meaning one that halts on and accepts inputs that are in $L$; this makes $L$ "recognizable" or "semidecidable"), there is no recognizing machine $M'$ for $\bar L$ since if there was, we could alternate between running one step at a time of the computations of $M$ and $M'$ and thus decide $L$, because either $M$ or $M'$ would halt in finite time. This immediately gives us that whenever a language is recognizable but not decidable, its complement is not even regonizable. $\endgroup$ – G. Bach Oct 16 '15 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.