<p>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 <em>then</em> 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.</p>

<p>On the other hand, if you define a <em>run</em> of the TM as one possible execution, and define that the TM <em>accepts</em> a word if there exists <em>a</em> 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).</p>

CC BY-SA 3.0
2012-02-24T09:21:40.643Z
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 ?
Xavier Labouze
CC BY-SA 3.0
2012-02-24T12:52:45.147Z
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.
Janoma
CC BY-SA 3.0
2012-02-24T01:53:52.707Z
2012-02-24T01:53:52.707Z
Janoma
<p>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.</p>

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

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

CC BY-SA 3.0
2012-02-23T22:59:11.493Z
this is better suited to [Mathematics.SE]
Suresh Venkat
CC BY-SA 3.0
2012-02-24T08:56:29.770Z
You should read the first two chapters of the textbook by Arora & Barak ([draft](http://www.cs.princeton.edu/theory/index.php/Compbook/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.
Bruno
CC BY-SA 3.0
2012-02-24T09:16:53.410Z
@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.
Xavier Labouze
CC BY-SA 3.0
2012-02-24T12:05:23.073Z
@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.
Bruno
CC BY-SA 3.0
2012-02-24T12:09:27.053Z
@bruno, you are right, tks.
Xavier Labouze
<cc.complexity-theory><turing-machines><nondeterminism>
Does a Non deterministic TM halt after the same number of steps on the same input?
Xavier Labouze
# Does a Non deterministic TM halt after the same number of steps on the same input?

(Asked by: username_0 on 2012-02-23)

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 ?

**Tags:** cc.complexity-theory, turing-machines, nondeterminism
> **Comments:**
> **username_1**: this is better suited to [Mathematics.SE]  
> **username_2**: You should read the first two chapters of the textbook by Arora & Barak ([draft](http://www.cs.princeton.edu/theory/index.php/Compbook/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.  
> **username_0**: @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.  
> **username_2**: @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.  
> **username_0**: @bruno, you are right, tks.  

---

## 1 answers

### Answer by username_3 on 2012-02-24. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: 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 ?  
> **username_3**: 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.  

---

