# Does a Non deterministic TM halt after the same number of steps on the same input? [closed]

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 ?

• this is better suited to Mathematics – Suresh Venkat Feb 23 '12 at 22:59
• 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. – Bruno Feb 24 '12 at 8:56
• @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 Feb 24 '12 at 9:16
• @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 Feb 24 '12 at 12:05
• @bruno, you are right, tks. – Xavier Labouze Feb 24 '12 at 12:09