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?

  • $\begingroup$ See this: cs.stackexchange.com/questions/88403/why-nondeterminism. $\endgroup$ – Yuval Filmus Oct 23 '19 at 14:25
  • $\begingroup$ 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? $\endgroup$ – chichi Oct 23 '19 at 14:41
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 23 '19 at 14:58
  • $\begingroup$ Perhaps you should also take a look at this: cs.stackexchange.com/questions/5008/…. $\endgroup$ – Yuval Filmus Oct 23 '19 at 14:58

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.

  • $\begingroup$ 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. $\endgroup$ – chichi Oct 24 '19 at 2:07
  • $\begingroup$ 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. $\endgroup$ – reinierpost Oct 31 '19 at 9:27
  • $\begingroup$ 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. $\endgroup$ – reinierpost Oct 31 '19 at 9:38

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.