Re: NTM -> DTM Transformation?


Chris Johnson wrote:
> I've been reading lately about non-deterministic Turing machines, and
> everything I read says that for any NTM a comparable DTM exists (though
> it may be horribly slow), and I'm just curious if there's a formal way
> to transform a NTM to a DTM. Particularly, say I have an NTM with a
> state A that when it reads a 1 loops back to itself (and writes
> something to the tape, and moves the head), and but also has a
> transition where it reads a 1, loops back to itself, but writes
> something different to the tape and/or moves the head in the opposite
> direction as the other transition. Thanks for any information.

Shortly, given NTM M1, an equivalent DTM M2 is constructed by simulating M1
using three tracks. I have in front of me a proof, but it is written in
Croatian and I don't have the willpower to translate it at this moment. You
may try http://www.cs.uiowa.edu/~rus/Courses/Theory/Notes/turing3.pdf or
http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html, there you
may find a more precise formulation.

Zeljko


.