The ultimate non-deterministic Turing machine

How Turing machines work?
Given an input (w), a Turing machine is in its initial state (q0), this being its first configuration (C0=q0w) through the computation. Then, it’s going through the unique sequence C0, C1, … Ci, Ci+1 until it reaches its last configuration, that being the one with q∈{qaccept,qreject}.

Now, the computation it’s said that it’s based on an algorithm (it’s having rules). Then again, it’s said that a NTM “may have a set of rules that prescribes more than one action for a given situation” and it’s choosing the right one every time. How it’s doing that it’s not important.

But, what if the algorithm is “write the answer”? Just like that! We assume that the algorithm for a NTM is similar to the algorithms for a DTM… but, having this possibility of choosing the right next state and symbol to write, why not a straight way (the straightest way) for finding the answer?

From this point of view, the number of steps (time) a NTM runs is the length of the answer.

This entry was posted in Turing machines. Bookmark the permalink.

2 Responses to The ultimate non-deterministic Turing machine

  1. Joe Marshall says:

    That isn’t a correct definition of a Non-deterministic Turing machine. You state `it’s choosing the right one [action] every time. How it’s doing that is not important.’ Actually, it *is* important. The action chosen is from a set of possible state transitions. When the machine reaches an `accept’ state, there is a path from the initial state, through the state transitions, to the final path that *effectively computes* the result.

    • stanmarian says:

      From a combination of state and symbol, NTM can choose more than an action to follow. The next state does not depend, entirely (not at all, in my opinion), on the previous state. Characteristic for NTM is that it’s choosing the right next state. If my understanding is wrong, please correct me, but the word “state” means all the symbols on the tape and the current instruction. Now, if “the next state” is not uniquely determined by the previous one, what is the limit of choices for this “next state”? Can it be exponential, depending on input size? I guess it can.
      Although, if a NTM is not making the right choice for its next state, the machine is useless (because it’s, at most, a Probabilistic Turing Machine), and the whole idea for this machine it’s also useless.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s