NTM -> DTM Transformation?
- From: "Chris Johnson" <ccjohnson@xxxxxxxxx>
- Date: 20 Jun 2005 12:24:28 -0700
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.
.
- Follow-Ups:
- Re: NTM -> DTM Transformation?
- From: Zeljko A.
- Re: NTM -> DTM Transformation?
- Prev by Date: Re: NP-complete and NP-Hard?
- Next by Date: Re: NTM -> DTM Transformation?
- Previous by thread: to CNF efficiently
- Next by thread: Re: NTM -> DTM Transformation?
- Index(es):