|
|
|
|
|
|
by alephaleph
873 days ago
|
|
|
It's roughly the same, no? It emulates a non-deterministic Turing machine and gives the same results, just taking much longer. But runtime isn't everything! I think that if you're programming in a nondeterministic style, you're programming as if you have a NTM, whether or not you're actually running the code on one. Also, surely NTMs are only physically unrealizable if P!=NP, and so whether or not NTMs could exist is an open question. |
|
|