[Solved]: Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

ignougroup
Problem Detail: Let a input string be given as $w_1w_2…w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two NFA, one being in state $r$ and other being in $s$, if there is a transition of the type $r xrightarrow{epsilon} s$. If there is a cycle of the type $r xrightarrow{epsilon} s xrightarrow{epsilon} q_1….xrightarrow{epsilon} q_k xrightarrow{epsilon} r$, where $q_i$ are some states of NFA, then it’s no use remembering another NFA in state $r$ upto the point where input has been read till alphabet $w_i$.

If a PDA ( non-deterministic ) is in state $r$ ( and input is read till $w_i$ ) and there exists a cycle $r xrightarrow{epsilon,epsilon to a} s xrightarrow{epsilon,epsilon to a} q_1….xrightarrow{epsilon,epsilon to a} q_k xrightarrow{epsilon,epsilon to a} r$ ( where transition $epsilon,epsilon to a$ means thatnothing after $w_{i}$ is read from input, nothing is popped or read from stack and alphabet $a$ is pushed onto the stack ) then before reading the next input alphabet $w_{i+1}$ there will be infinite PDA in states $r,s,q_1,…q_k$ because unlike the NFA although the states are finite stack contents can be different ( infinite possibilities ), if I am not wrong.
As with NFA and PDA the power of non-determinism comes from $epsilon$ transitions. So I assume that non-deterministic Turing machine also gets it’s non-determinism from $epsilon$ transitions like NFA and PDA ( more like PDA ). I know that a deterministic Turing machine can simulate a non-deterministic one ( I know the proof which uses bread-first search ). But now I am doubtful as to how that is possible. Because if a cycle of the type in PDA above, exists in the state diagram of the non-deterministic Turing machine then before reading the next symbol $w_{i+1}$ the deterministic Turing machine even when simulating a configuration in some branch of non-deterministic Turing machine ( while bfs ) would have to keep track of infinite Turing machine ( again the states are finite but the symbols on the tape have infinite possibilities ).
So how exactly non-determinism in defined in case of Turing machines ? Am I misunderstanding something trivial ? Do non-deterministic Turing machines use $epsilon$ transitions ?
I am sorry for my trivial doubts. If anything is incorrect I can update my question.

Asked By : sashas

Answered By : Yuval Filmus

Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define total functions, while Turing machines (deterministic or non-deterministic) in general define partial functions. A partial function is one defined only on part of the domain. If $f$ is not defined on $x$ then we write $f(x) = bot$. (So $f$ is really a total function, but there is a special element in the range signifying that the output is undefined.) A deterministic Turing machine $M$ defines a partial function as follows: if $M$ halts on $x$ then $M(x)$ is the contents of the tape when $M$ halts on $x$; and otherwise, $M(x) = bot$. A deterministic Turing machine decider has two kinds of halting states, accepting and rejecting, and defines a partial function as follows: if $M$ halts on $x$ at an accepting state, then $M(x)=1$; if it halts at a rejecting state, then $M(x)=0$; if it doesn’t halt, then $M(x)=bot$. If $M$ always halts then we say that it accepts the language $L = {x : M(x) = 1}$. A non-deterministic Turing machine (which is always a decider) is allowed to “branch” (have several possible options at any given point in time), and has the following semantics:

  • $M(x) = 1$ if on input $x$, the machine $M$ halts on all branches, halting at an accepting state for at least one branch.
  • $M(x) = 0$ if on input $x$, the machine $M$ halts on all branches, always halting at a rejecting state.
  • $M(x) = bot$ if on input $x$ there exists a branch on which $M$ doesn’t halt.

Given this definition, it is hopefully clear how to simulate a non-deterministic Turing machine using a deterministic Turing machine decider: you try all branches, checking whether any of them leads to an accepting halting state. After all branches have halted, you can decide whether to go to an accepting state or to a rejecting state. If the non-deterministic Turing machine doesn’t halt on some branch, then so would the deterministic one. What about $epsilon$-moves? They cause trouble in that the corresponding automaton might never halt. For finite automata (NFAs and PDAs) we silently ignore non-halting computations. Our reason for doing that is that the resulting languages are always computable, even though the naive algorithm for simulating them deterministically (simulating all computation paths) doesn’t quite work. This is not so difficult for NFAs, which can be converted to DFAs. However, deterministic PDAs are strictly weaker than non-deterministic PDAs. Nevertheless, you can show that every PDA is equivalent to one without $epsilon$-transitions (though the proof might go through context-free grammars). You can simulate $epsilon$-moves in Turing machines, but you have to be careful that there are no loops which cause non-halting computations. In some cases, however, we can use the same trick as above. For example, suppose that your Turing machine is space-constrained: we know an upper bound on the space that it uses (depending on the input length). In that case every non-halting computation necessarily cycles (since the Turing machine has finitely many states, including the tape contents), and so if we “ignore” non-halting computations as above, the resulting model of computation is still computable. More generally, this works as long as we are guaranteed that every non-halting computation cycles. (This is the case for NFAs but not for PDAs.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48224