# Behavior of non-deterministic Turing Machines after $t_i$ seconds

Suppose that I have a non-deterministic Turing Machine $M_1$ and its clone $M_2$. Given a string $x \in \Sigma^*$, it is possible that after $t_i$ seconds $M_1$ accepts $x$ and $M_2$ does not halt ? What happens if i run $M_2$ $2t_i$ seconds?

My approach

It is possible because the transition function $\delta_N$ is a partial function and the machines do random guesses, but it can't be that a machine reject and the other accept. If i run $M_2$ for $2_i$ seconds, the outcomes may be different.

• What exactly do you mean? Talking about wall-clock time in complexity theory doesn't make much sense, even less so when nondeterministic models of computation are involved. Nov 5 '17 at 1:44
• Imagine that this is an abstract experiment. Let Bob have a computer that generate random strings $x_i$ in a alphabet $\Sigma^*$ and random numbers $t_i$ that code when make a picture of the current computation in progress. So after $t_i$ second a picture is made, and Bob have to check what the outcomes of $M_1$ and $M_2$
– Jack
Nov 5 '17 at 1:50
• Two identical NDTM are by definition the same object. They will always behave in the same way. I still have no idea of what you're trying to say, I'm sorry. Nov 5 '17 at 1:53

There are no seconds of execution, you might want to use steps instead.
Non-deterministic Turing Machine does not behave randomly at all, so two machines $\mathcal M_1$ and $\mathcal M_2$ (being copy) are identical, they do not in any random way pick the steps, so the simulation on the first one goes like on the second one. At any time after the same number of steps the tape content matches and the current state matches.

In sny transition there might be more than one rule, the NDTM accepts when one of the paths accepts, but these are executed in copied machines. This effectively may mean that the NDTM have "guessed" the next step (counting steps to the accepted path is the shortest possible one if such exist) but it will always be the same one for given configuration. Please note that if you imagine every step as producing copy of the machine with a different transition taken then these copies might differ.

• Imagine that Bob has a red button that stops the execution of $M_1$ after $t_i$, and the other machine $M_2$ stops after $2t_i$ seconds. In this case, may $M_{2}$ halt & accept (or reject) and $M_{1}$ does not accept ?