patternModerate
What is 'halting'?
Viewed 0 times
haltingwhatstackoverflow
Problem
I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just means to stop and asess an input.
But just to be clear, would somebody be so kind as to give me an easy to understand of what halting is in turing machines?
But just to be clear, would somebody be so kind as to give me an easy to understand of what halting is in turing machines?
Solution
Look at the definition of a Turing Machine (e.g., the one here). The machine has states. Each state can be final or non-final. If the machine's state is non-final, in the next step the machine "does" something, namely, it can write something on the tape, move its head, and/or change its state to a different state. This is how the machine makes a progress.
However, if the state is final, the machine just stops and continues no more. This will be its final setting, the head will not move anymore and the tape remains the same forever. This event is non-reversible and is what we call halting.
Machines can halt on all inputs, on some inputs, or no input(s). An example for a non-halting machine (on any input) is one that has only one state $q_0$ (which must be non-final), on which the head always moves to the right. Formally, this can be denoted as having the transition function $\delta(q_0,a) \to (q_0,R,a)$ for any symbol of the tape's alphabet $a\in \Gamma$.
A Final state can be either accepting or rejecting. It makes sense to have only two final states: $q_{accept}$ and $q_{reject}$. The first is equivalent to the output "yes" and the second to the output "no".
Machines that stop on every input are called deciders: their language is decidable. But it's better to look at it from the other side: some languages can be decided: there exists a machine that halts and accepts (e.g., ends in $q_{accept}$) for every input which is a word in the language; and halts and rejects (ends in $q_{reject}$) for every input which is not a word in the language.
Some languages cannot be decided: any machine that accepts all the words in that language, has some inputs on which it doesn't halt. These are semi-decidable languages. The co-semi-decidable languages have machines that only halt (and reject) on all the words not in the language, but will not halt on some other inputs, which are words in the language.
However, if the state is final, the machine just stops and continues no more. This will be its final setting, the head will not move anymore and the tape remains the same forever. This event is non-reversible and is what we call halting.
Machines can halt on all inputs, on some inputs, or no input(s). An example for a non-halting machine (on any input) is one that has only one state $q_0$ (which must be non-final), on which the head always moves to the right. Formally, this can be denoted as having the transition function $\delta(q_0,a) \to (q_0,R,a)$ for any symbol of the tape's alphabet $a\in \Gamma$.
A Final state can be either accepting or rejecting. It makes sense to have only two final states: $q_{accept}$ and $q_{reject}$. The first is equivalent to the output "yes" and the second to the output "no".
Machines that stop on every input are called deciders: their language is decidable. But it's better to look at it from the other side: some languages can be decided: there exists a machine that halts and accepts (e.g., ends in $q_{accept}$) for every input which is a word in the language; and halts and rejects (ends in $q_{reject}$) for every input which is not a word in the language.
Some languages cannot be decided: any machine that accepts all the words in that language, has some inputs on which it doesn't halt. These are semi-decidable languages. The co-semi-decidable languages have machines that only halt (and reject) on all the words not in the language, but will not halt on some other inputs, which are words in the language.
Context
StackExchange Computer Science Q#38228, answer score: 13
Revisions (0)
No revisions yet.