5 ms·

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 m

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.

ethanwillis 6y ago
Uh.. non deterministic state machines can all be expressed as deterministic state machines. This also has nothing to do with P vs NP
frabert 6y ago
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.
- jcranmer 6y ago
  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.
jerf 6y ago
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.)
- tathougies 6y ago
  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.
- deleted 6y ago
  [deleted]
- sibrahim 6y ago
  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.
  - jwalton 6y ago
    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.
    - sibrahim 6y ago
      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.
  - 6y ago

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.

ethanwillis 6y ago

Uh.. non deterministic state machines can all be expressed as deterministic state machines. This also has nothing to do with P vs NP

frabert 6y ago

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.

jcranmer 6y ago
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.

jerf 6y ago

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.)

tathougies 6y ago
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.
deleted 6y ago
[deleted]
sibrahim 6y ago
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.
- jwalton 6y ago
  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.
  - sibrahim 6y ago
    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.
- 6y ago