33

I do not the understand the concept of Non Deterministic Turing Machine. I guess I understand the term Non deterministic algorithm : (nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.) So the algorithm could be like :

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

But for non-deterministic turing machine I read , it can be in more than one state at a given time. Also a wikipedia article suggests "A non-deterministic Turing machine (NTM), may have a set of rules that prescribes more than one action for a given situation".

What does that mean ? ..More than one action for a given stituation...multiple states... I simply do not understand this.

Community
  • 1
  • 1
Suhail Gupta
  • 22,386
  • 64
  • 200
  • 328
  • check out http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html and see "Turing machine accepting a+" in the end. it's a more descriptive model for the solution space. in "tangible" terms, a set of parallel processors each applying a rule for the next state and they aren't in contact with one another. – ashley Nov 23 '12 at 06:36
  • 13
    I think these admins close questions they dont like. Thank you Admins for making Stack Overflow more usless. – DollarAkshay Jul 12 '15 at 07:20
  • 1
    @AkshayLAradhya: Well, IMHO, this kind of questions are more on-topic on [Computer Science Stack Exchange](http://cs.stackexchange.com/). – Mario Cervera Nov 29 '16 at 13:30

1 Answers1

47

In a Non Deterministic Turing machine, in each branch - you do both possibilities - and only when you are done you "choose" which one is the one you need for the solution (if one exists).

For example, let's look at the subset sum problem, with S = {a,b,c... }. The Non Deterministic Turing machine has a linear solution:

for each element:
   "guess" if it is in the subset
check if the subset has the specified sum

The tree generated will be something like that:

                                       start
                 with a                                      without a
               /         \                                   /          \
              /           \                                 /            \
             /             \                               /              \
      with b               without b                  with b              without b
      /     \               /       \                 /     \             /        \
  with c    without c    with c     without c     with c    without c    with c     without c

It is enough that one calculation (path in the tree) is correct in order for the algorithm to yield "true". It yields "false" only if there is no such calculation.

The concept of Non Deterministic Turing Machine is purely theoretical - there is no non-deterministic turing machine available.

Bonus:
Note that everything that can be done with Non Deterministic Turing Machine - can be done with a Deterministic Turing Machine (and vise versa) - for example, the Halting Problem is not decideable in either. However, NPC problems can be done polynomially in Non Deterministic Turing Machines, and we do not know (and we assume we cannot) how to do it polynomially on Deterministic Turing Machines.

DRKblade
  • 347
  • 2
  • 13
amit
  • 175,853
  • 27
  • 231
  • 333
  • 3
    A Non-Deterministic TM exists to the same extent as a Deterministic TM. Neither really exists, because all real computers have bounded storage, but we can simulate them. The big difference is that the time to simulate an NDTM tends to increase exponentially, rather than linearly, in the number of steps simulated. A simulator has to track all the configurations the machine might be in at the end of a given step. A simulator for a DTM only has to track one configuration at a time. – Patricia Shanahan Nov 23 '12 at 07:01
  • @PatriciaShanahan: This is not completely correct. Though we have "bounded storage", a RAM machine can use disk to store data as well. The capacity of data that can be stored on disk is limited by a non realistic number (and can be increased on the fly while the algorithm runs). However - if you try to do it hard and cold - yes, the number of atoms in the universe is a finite number and thus the number of states/configurations one can achieve is also finite. – amit Nov 23 '12 at 07:04
  • 1
    Great simplification of the concept. I was wracking my brain over this one as most definitions I've run across are too academic to easily understand. – Chris Walter Oct 24 '15 at 14:03
  • 1
    The concept of Non Deterministic Turing Machine is purely theoretical - there is no non-deterministic turing machine available. helps a lot. – roottraveller Jul 14 '17 at 07:27