How Turing machines work?

Given an input (*w*), a Turing machine is in its *initial state* (q_{0}), this being its first configuration (C_{0}=q_{0}*w*) through the computation. Then, it’s going through the unique sequence C_{0}, C_{1}, … C_{i}, C_{i+1} until it reaches its last configuration, that being the one with q∈{q_{accept},q_{reject}}.

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.

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.

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.