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.

  • $\begingroup$ 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. $\endgroup$ – quicksort Nov 5 '17 at 1:44
  • $\begingroup$ 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$ $\endgroup$ – Jack Nov 5 '17 at 1:50
  • $\begingroup$ 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. $\endgroup$ – quicksort 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.

Please read also the difference between non-determinism and randomness

| cite | improve this answer | |
  • $\begingroup$ 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 ? $\endgroup$ – Jack Nov 5 '17 at 11:33
  • $\begingroup$ @Jack there are no seconds. Period. Yes, if e.g. 10 steps are required, the first run for 6 steps (so doesn't finish), and the second for twice as much then it stops. $\endgroup$ – Evil Nov 5 '17 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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