9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ regarding the title question, there is not much difference in formal definitions. as for the emergent power, yes it has much different implications in each machine model. as for the rest of the question, find it hard to parse. :( $\endgroup$ – vzn Oct 13 '15 at 15:19
  • 1
    $\begingroup$ Have you checked Wikipedia? en.wikipedia.org/wiki/Non-deterministic_Turing_machine $\endgroup$ – Yuval Filmus Oct 13 '15 at 15:21
  • $\begingroup$ @YuvalFilmus yes I have. The definition of transition function includes power set which I understand. But the thing about $epsilon$ transitions in Turing machines is still unclear to me. $\endgroup$ – sashas Oct 13 '15 at 15:25
  • $\begingroup$ @vzn I thought so. I am really sorry. I am bad at putting forward my doubts. But I can improve if you give suggestions. $\endgroup$ – sashas Oct 13 '15 at 15:26
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. I had one last doubt. In a PDA with the transition $r \xrightarrow{b,c \to a} s $, if the PDA is in state $r$ then it will split only if $b$ ( $b$ is alphabet read from input tape, $c$ is alphabet popped from stack and $a$ is pushed to stack ) is $\epsilon$ irrespective of what $a$ and $c$ are ( $\epsilon$ or regular stack alphabets ). Am I right ? $\endgroup$ – sashas Oct 14 '15 at 3:04
  • $\begingroup$ @sasha Execution "splits" whenever there is more than one option to proceed. $\endgroup$ – Yuval Filmus Oct 14 '15 at 4:09
  • $\begingroup$ How do I go about proving that a PDA with $\epsilon$ transitions can be converted to one without them ? I know I can always prove language accepted by any PDA is decidable by converting it to its CFG in normal Chomsky form. But still can't convert to PDA with no epsilon transitions. I would really appreciate any hint. $\endgroup$ – sashas Oct 15 '15 at 5:38
  • 1
    $\begingroup$ @sasha You can convert a context-free grammar in Greibach normal form to a PDA with no $\epsilon$ transitions (at least according to Wikipedia). $\endgroup$ – Yuval Filmus Oct 15 '15 at 5:41
  • 1
    $\begingroup$ @YuvalFilmus, a nondeterministic construction from GNF is essentially recursive descent: For a production $A \to a B_1 B_2 \ldots B_n$, if $A$ is at the top of the stack, on input $a$ replace the $A$ by $B_1 \ldots B_n$ on the stack. No $\epsilon$ in sight. Still nonteterministic (there might be several $A$-productions that start $a\ldots$). $\endgroup$ – vonbrand Oct 15 '15 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.