# motivation and idea of defining non-deterministic Turing machine

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?

• – Yuval Filmus Oct 23 '19 at 14:25
• Thanks @YuvalFilmus, so NTM is just a theoretical construct which is a generalization of Turing machine and makes Turing machine more "time efficient"? (though it is still hard to imagine for me why it becomes more time-efficient if we make a set of sequential rules to a set of branches of tree-like rules? – chichi Oct 23 '19 at 14:41
• There are many possible reasons to consider nondeterministic computation. Time efficiency is just one of them. The polynomial hierarchy (which generalizes nondeterminism for polytime machines) is a useful construct for other reasons - for example, the assumption that PH doesn't collapse implies many other complexity results. – Yuval Filmus Oct 23 '19 at 14:58
• Perhaps you should also take a look at this: cs.stackexchange.com/questions/5008/…. – Yuval Filmus Oct 23 '19 at 14:58

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.

• This is awesome and spot on!! I am so happy to read your answer that solved my confusing and questions. – chichi Mar 23 '20 at 15:00
• @chichi I'm glad it was helpful :) – 6005 Mar 23 '20 at 15:05

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.

• So, the NTM is just a generalisation of the definition of a Turing machine. The non-deterministic branching has nothing to do with the randomisation or parallelisation, am I right? Usually, randomisation and parallelisation may be done only on some particular steps, however, the non-deterministic branching is defined at every step. So I am imaging that it is simply a kind of Turing machine that clone themselves and go on to do things on different branches. Then, as long as one of the branches can halt, this NTM can do some work. – chichi Oct 24 '19 at 2:07
• The way I see it, the nondeterministic machine just picks a choice and continues. There is no randomization - randomization means you have a deterministic machine that tries to make choices fairly, but we have no deterministic machine here. There is no parallelism or cloning - you might employ those to build a deterministic machine that walks all paths the nondeterministic machine might walk, which you need to do to deterministically accept the language in question. – reinierpost Oct 31 '19 at 9:27
• The nondeterministic machine and nondeterministic acceptance are similar to working with possible worlds in modal logic. The machine's actions are seen as a walk through a state space of possible configurations. – reinierpost Oct 31 '19 at 9:38