Hacker News Reader

Comment by aphextron | Hacker News Reader

Wouldn't that imply that P/NP is not a problem? All turing machines are capable of processing non-deterministic instructions, making them nothing like a state machine.

View on HN

You're on the right track, but the wrong problem. What this theoretically renders irrelevant is the halting problem. Ignoring IO (which allows the importing of arbitrary amounts of state from the exterior world), it is in fact possible to take a real computer and determine if a program will halt. It's easy. You just run it and record every state it passes through. It will either return to a previously-existing state in a finite period of time, in which case the program does not terminate, or it will halt in a finite period of time.

The problem is that it doesn't take much computer before the fact that the halting problem is theoretically solvable doesn't matter much. The Commodore 64 had 524,288 bits, which means even ignoring the other hardware that could have its own states it has 2^524288 states, approx. equal 10^157,828 states. You can't fit a record of all of the states that it might pass through in our universe. And it gets exponentially worse with every bit you add. An impoverished computer with a mere gigabyte of RAM would be 10^2,585,827,973 states.

So while in theory our computers are state machines, in practice we are much better suited to using the tools of Turing machines to analyze their behavior.

(I'm pretty sure you could construct an argument using the usual formulation of the halting problem to prove there is no practical easier way to tell that a computer will halt in general, but it would be more involved than I can sketch out. There is more to it than just swapping out "Turing machine" for "Turing machine limited to a tape of size X" everywhere.)

(Edit: Incidentally, I skimmed over the article the first time, assuming it was based on this observation. Deeper reading shows that it doesn't mean this, and in fact I don't actually know what it is intending to say, honestly. But the above still holds. Technically, all computers are state machines, not Turing machines, as Turing machines don't fit in our universe.)

Well not quite. The search space for the Commodore 64 is already many magnitudes of times larger than the total number of atoms in the universe, so unless you had access to alternate universes, it would actually be impossible to solve the halting problem on C64, even if you had the resolve and all resources available.

This is what lead Joe Armstrong (Erlang) to say that when you include memory and storage, no two computers on the planet are ever in the exact same state unless they've just been reinstalled or restarted. This is why software never quite works the same way twice and internet instructions for fixing it never seem to work for you either.

[] https://www.youtube.com/watch?v=lKXe3HUG2l4

There's no need to store all previous states to detect a cycle: it can be done using just twice the original memory.

You can model the state transitions as a linked list and use Floyd's classical tortoise and hare algorithm to (eventually) determine a cycle exists. Initialize "tortoise" and "hare" as two copies of initial state and advance hare by two instructions and tortoise by one each iteration. A cycle is reported if the two states become equal again.

It's true your solution will work, but you're essentially trading space complexity for time complexity. With 2^524288 states, instead of requiring more RAM than there are atoms in the universe worth of RAM, you'll now need more seconds of compute time than we have left before the heat death of the universe.

Note that the time taken is linear with respect to the original execution.

A cycle of n instructions starting at instruction n0 will be detected in between n0 and n0+n iterations (i.e. <= 3*(n0+n) underlying instructions) since n0 iterations gets both into the cycle and the offset between them will become 0 some time in the next n iterations.

n could be very large, of course (e.g, using all of memory as a giant counter so the cycle length is huge), but the cycle detection is not really making your problem worse.

Thank you. This is the sort of thing I was alluding to when I suggested it was harder than just doing a simple replacement on the standard halting argument.

In this case, I'll back it down to suggesting there's probably some way to prove it can't be done without some unreasonable amount of at least one of time and space.

Do not confuse nondeterministic Turing machines with nondeterministic (finite) state machines/automata. The latter are proven to be equivalent to their deterministic counterparts, the former are not.

A nondeterministic Turing machine is no more powerful than its deterministic Turing machine, if you define "powerful" as "can solve problems." If you instead define "powerful" as "can solve problems within a given amount of time," then there may be a distinction.

Put another way, you can simulate a nondeterministic Turing machine with a deterministic one, just as you can simulate a nondeterministic finite-state machine with a deterministic one. However, this simulation does come with increased time and space requirements.

Uh.. non deterministic state machines can all be expressed as deterministic state machines.

This also has nothing to do with P vs NP

Reply on news.ycombinator.com