debugModerate
Why won't a Turing machine halt?
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 ?
$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:
, 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.
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.