How Turing machine can loop forever when input length is always finite? I think this is a basic doubt but unable to understand how TM go into infinite loop? I think it can make transition forever on empty string. What are the other cases? Can it make without any empty alphabet ?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Closely related question. $\endgroup$– Raphael ♦Dec 30, 2016 at 10:47
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
A simple example is a Turing Machine with one state $q$, alphabet $\Sigma = \{a\}$, tape alphabet $\Gamma = \Sigma \cup \{\sqcup\}$ and the two transitions $q\times a \to q \times a \times \mathcal{R}$ and $q \times \sqcup \to q \times \sqcup \times \mathcal{R}$. It doesn't even change the tape.
answered Dec 30, 2016 at 9:21
$\begingroup$
$\endgroup$
It might help to think of Turing machines as a programming language. It's easy to see how a program in your favourite language might loop (its input is finite, too!) so you can translate that to a Turing machine.
answered Dec 30, 2016 at 19:08
$\begingroup$
$\endgroup$
Assuming the tape contains a string over $\{0,1\}$, so it represents a binary number.
Repeat: go to right end, add $1$.
answered Dec 30, 2016 at 19:03
$\begingroup$
$\endgroup$
1
Is is a property of the transition function. Transition function might take the turing machine into an infinite loop on a particular input even when the input length is finite. Consider the transition function below with states Q0 and Q1 Q0 is the halt state If Q1 reads ‘L’, then stay in Q1 and go left one cell. If Q1 reads ‘R’, then stay in Q1 and go right one cell. If Q1 reads ‘H’, then change to Q0 and remain at this cell.
On the input RRRLLLL the machine goes into a loop but that doesn't mean language accepted by the machine is empty. It does halts on inputs such as RRRRH etc.
answered Dec 30, 2016 at 6:28
-
$\begingroup$ Thanks for your answer, can you provide such function. Would be helpful. $\endgroup$ Dec 30, 2016 at 6:30