[nyrikki]

Note of clarification.

This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP.

There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step.

But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrealizable.

[cha42]

It is the same notion exactly actually.

The code isn't magically solving NP vs P but it does simulate non deterministic run through a potentially exponential exploration.

[alephaleph]

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.