motivation and idea of defining non-deterministic Turing machine

Question

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

1. A Turing machine is a machine performing works specified on a cookery book (algorithm).
2. The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
3. So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.

---

OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a "relation". That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!

---

update From the linked post, it looks like the introduction of NTM naturally leads to a class of "problems" (not algorithms because a problem can be solved by several algorithms with different efficiencies) called NP problems. Forgive me that I still feel that every step is such a huge jump... Could someone close the gaps a little bit? thanks a lot!

Motivated by @reinierpost's answer, I found this explanation of NP problems on CMI website. The example problem is to choose 100 students from 400 candidates subject to some constraint that some pairs of students cannot be included. In this case, I can imagine that a Turing machine trying to solve this may naturally equip itself with a cloning ability such that it is able to generate the solution with multiple choices in the steps. Then, as long as some choices or branches of the NTM work, the machine finds the solution(s). In this sense, an NTM looks like a multi-threading parallelization to save time?

Answer 1

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.

I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".

An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.

Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.

• A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(

• An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.

This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible. For example, if we input $9$ to the NTM we just described, then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.

It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?

No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.

If no, why do we need to allow multiple choices for a Turing machine?

We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.

In this sense, an NTM looks like a multi-threading parallelization to save time?

Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.

In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.

Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.

Answer 2

You're getting caught up in definitions. Algorithms are usually defined to be deterministic because they are usually introduced in a context where deterministic computation is the norm, the vehicle of choice for the task at hand.

Many real-life algorithms are nondeterministic (e.g. many cookbook recipes are very nondeterministic, and many algorithms in pseudo-code have lines that say "pick an x"). If we are denied the option of calling them "algorithms", and thus are left without a useful term to describe what they are, that is purely a matter of definition, it's not because such things do not exist.