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

Why won't a Turing machine halt?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whymachinewonhaltturing

Problem

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 ?

Solution

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)
{ 
   do_nothing
}


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

Code Snippets

while (true)
{ 
   do_nothing
}

Context

StackExchange Computer Science Q#48293, answer score: 19

Revisions (0)

No revisions yet.