Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt.

If $M$ is a deterministic TM, it will obviously halt at the same step on the same input.

Suppose $M$ is a non deterministic TM. Does $M$ halt after the same number of steps on the same input ?

  • 6
    $\begingroup$ this is better suited to Mathematics $\endgroup$ Feb 23 '12 at 22:59
  • 3
    $\begingroup$ You should read the first two chapters of the textbook by Arora & Barak (draft) where TM and NDTM are defined. My short answer to your questions is no. But you can often build from a NDTM build a new one with all paths (accepting and rejecting) of same length. Often does not mean anything of course, but what I meant is that if you consider a NDTM deciding a language in time $f(n)$ for some nice function $f$ (time-constructible for instance), then it is possible. Of course, you can also build TM with very chaotic behaviors. $\endgroup$
    – Bruno
    Feb 24 '12 at 8:56
  • $\begingroup$ @Bruno , Tks for the reference (I already read it actually) and your comment. Yes, it is often possible to build a TM with all paths of same lenght. But, it doesn't really answer the question which holds essentially when all paths are not of the same lenght. I thought (wrongly) that a NDTM "tried" each non deterministic possibility at each step, and then halts as soon as possible. $\endgroup$ Feb 24 '12 at 9:16
  • 2
    $\begingroup$ @XavierLabouze You really need to think of a NDTM as an unrealistic model. It accepts a word if it has a way to do so. This is very different from a probabilistic TM for instance. $\endgroup$
    – Bruno
    Feb 24 '12 at 12:05
  • $\begingroup$ @bruno, you are right, tks. $\endgroup$ Feb 24 '12 at 12:09

That depends on how you define the computation process. If you consider that the TM executes all possible computations at the same time ("in parallel", if you want) and then decides if accepts by looking at the states in which it finished, then obviously it will always halt after the same number of steps for a given input, or never halt at all.

On the other hand, if you define a run of the TM as one possible execution, and define that the TM accepts a word if there exists a run that ends in an accepting state, then the answer is "no", and it should be pretty simple to define a TM which halts after different number of steps for the same input on different runs (for example, one that accepts in a run, but ends in an infinite loop in other run).

  • $\begingroup$ Tks for your answer. That is exactly the point : is there a unique definition of computation process ? Why not use your first one instead of the second one ? $\endgroup$ Feb 24 '12 at 9:21
  • 1
    $\begingroup$ One reason is that nondeterminism is easier to explain when you have the idea of "guessing": the TM guesses a path that will accept. Formally, that is defined with a run, not with a parallel execution of all possible runs. $\endgroup$
    – Janoma
    Feb 24 '12 at 12:52

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