# 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. – quicksort 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. – quicksort Nov 5 '17 at 1:53

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.
• 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 ? – Jack Nov 5 '17 at 11:33