On 11/10/2010 7:23 PM, Darren New wrote:
> Is it possible for a non-deterministic turing machine to solve the
> halting problem of deterministic turing machines? That is, can I use a
> NDTM as an oracle for DTMs? I don't think so, right? There's no way to
> check your guess is correct, basically?
>

Since you can simulate a NDTM with a DTM (at the expense of an 
exponential increase in time), no.

Post a reply to this message