|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |