Margo Seltzer and folks wrote a fun paper about this a few years back at ASPLOS:
"We present an architecture designed to transparently and automatically scale the performance of sequential programs as a function of the hardware resources available. The architecture is predicated on a model of computation that views program execution as a walk through the enormous state space composed of the memory and registers of a singlethreaded processor. Each instruction execution in this model moves the system from its current point in state space to a deterministic subsequent point. We can parallelize such execution by predictively partitioning the complete path and speculatively executing each partition in parallel. Accurately partitioning the path is a challenging prediction problem. We have implemented our system using a functional simulator that emulates the x86 instruction set, including a collection of state predictors and a mechanism for speculatively executing threads that explore potential states along the execution path. While the overhead of our simulation makes it impractical to measure speedup relative to native x86 execution, experiments on three benchmarks show scalability of up to a factor of 256 on a 1024 core machine when executing unmodified sequential programs."
This is using the terminology a bit strangely. Usually a Turing machine is something that's in a complexity class above a stack automaton which is in a complexity class above a finite state machine. And then we think of computers as Turing machines because that's helpful but they are in practice finite state machines because they have a limited amount of state. But the equivalence between a Turing machine and a state machine in the article is only true if the state in the state machine can be infinite.
i can extrapolate even further and say that everything is a state machine. humans are a state machine, plants are a state machine, reality itself is a state machine.
we don’t see it like this because of the sheer complexity, but in the end we are a continuous computation that occurs at every moment in time.
Not in the standard regime of finite state machines. If you allow for infinite continuous state machines and infinitesimal steps, then it’s no problem. Every classical mechanical system is fully specified by positions and velocities. Transitions follow Newtonian mechanics. Every non-relativistic isolated quantum system is specified by the wave function and the transitions follow the Schrödinger equation.
Isn't this turning into a word game? If we're just saying "reality can be discrete state machines or continuous analog systems which I will call an infinite state machine" then are you really saying anything at all?
for my own clarification purposes: why is finite vs infinite an issue? IMHO, i don’t believe we have truly infinite state unless we’re talking about mathematical abstraction.
Don’t know if it is. But in computer science state machines are usually finite or at least discrete. Time evolution in quantum mechanics is certainly continuous, not discrete. Discrete are only some observables.
i think we maybe are mixing measuring with the actual evolution of the state. you cannot observe a quantum system without altering its state. also, there is no such thing as an isolated quantum system. this is true even for classic mechanics but we are cool with it since the measurement error is insignificant compared to what we measure.
i believe that the number of states a quantum system goes through is finite, albeit maybe very very large and the way we are treating it is based mostly on the tools we have not what is happening in reality.
If you refer to measuring and wave function collapse in QM, then yes, but for that you need interaction with the environment (the observer), that’s why I specified “isolated”. Regardless, even the wave function collapse is a state transition, albeit stochastic. I assume state machines allow for stochastic transitions?
wave function collapse is not an open and shut case. it’s fancy math in place to explain it.
there are multiple interpretations of what is going on including the many worlds interpretation and my personal favorite the GWR interpretation.
at the end of the day we don’t know what is going on at that level and we are speculating wildly based on the math we have.
the math is sometimes useful as it has some real life applications - but speculation is speculation
The Planck length is sometimes misconceived as the minimum length of space-time, but this is not accepted by conventional physics, as this would require violation or modification of Lorentz symmetry.[1]
Isn't it usually assumed spacetime is not discrete. At the very least there is no proof to say everything is discrete. Just because the universe can do computations doesn't mean it is a state machine.
state machine: you have a state that you can describe. you get input, you transform the state, you maybe output something. state transition can also be viewed as input.
so i believe that everything is a state machine. everything
nobody is "doing" quantum mechanics per se. they are applying predictions from a theory that has been around for a while and those predictions work well enough in narrow domains to be useful.
i know enough to understand some of the fancy math behind it, but one thing to keep in mind is that what people think of when they say quantum mechanics is the mathematical model we're working with, not the real thing.
the numbers of cells your eye perceives movement with it limited. you brain interpolates like crazy (did you know that most of the stuff you see, you actually don’t see? it’s a result of heavy editing done by the brain). so now the question: are you sure that the movement of an object is continuous?
How are vacuums, pure functions or abstract concepts state machines?
Philosophy has some pretty well fleshed out concepts around simple objects (without proper parts) and intrinsic properties as well that I think would contradict this.
the short answer that you’re not going to like is that everything you’re describing is a human construction. it therefore exists in the minds of people as a concept. we use it because it’s convenient.
a pure function that does not exist anywhere and nobody does not know about effectively does not exist.
philosophy is another things that is a human construction. a lot of our lives is lived inside our heads working with things we made up. it’s convention. you don’t get to ignore physics.
Well I think this is surely a cop out as a state machine is also a concept. Although If you are conceding we can't model all concepts with state machines then I think I'm satisfied.
the initial discussion was about all physical object. since you cannot have concepts without representing them onto something physical (paper, in the memory of a computer, in brain, etc) it immediately follows that concepts exist only with a state machine substrate. therefore concepts, distilled to their essential components are (insanely large insanely distributed) state machines
I don't think that's true. Not everything in this world follows from another. In a system, there will be things that are true in that system, that can't be derived from previous axioms. If I remember correctly, Godel proved this.
"The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers. "
Doesn't it follow that you can't write a program that proves all the true things about natural numbers. Therefore there will be true facts about the arithmetic of natural numbers not derivable from the axioms. That's my reading of it.
Basically there will be formulas, you can't get to by following an algorithm from the axioms. But if you lets say randomly stumble on a formula, you can easily prove it works or not.
That's my reading of it.
So for example, we can't write a program that will find all formulas, like for example.
a^2 + b^2 = c^2
But once we have a formula, we can prove that this formula works.
Thats my understanding of this Theorem. Correct me if I'm wrong.
You certainly can't write a state machine for the halting problem either.
i can extrapolate even further and say that everything is a state machine. humans are a state machine, plants are a state machine, reality itself is a state machine.
we don’t see it like this because of the sheer complexity, but in the end we are a continuous computation that occurs at every moment in time.
Godel incompleteness applies for math, logic, etc but you need to understand that math is human construct. formulas and numbers don't exist in a void. they need a substrate like a human mind or a computer.
Also by state machine i mean a system is basically a current state + state transitions. I was not using state machine as a way of modeling and solving a problem. That's a narrow definition of a state machine only applicable within a certain domain.
so everything in reality can be seen as a state machine
also as an orthogonal side note to the the halting problem: in theory you may conceive of systems and/or programs that will never halt but remember they are theoretical. Eventually, entropy gets to us all so for anything, even ideas of algorithms that may never halt, is temporary and are guaranteed that given enough time they will halt.
What does this mean in practise? I think this comes from the days of single core machines where going to multiple threads can't improve performance. But even on a single core device, threading is routinely used because a single state machine becomes to big to easily program
not sure if serious or trolling but this sounds like trolling. the reason we use threads is that they are a higher level abstraction that helps us keep the cognitive load down and focused on the layer we care about.
Surely it isn’t though? A state machine is generally considered to be a finite state automaton, isn’t it? Turing machines are substantially higher up the Chomsky hierarchy than finite state automata.
Edit: take finite out of it, and then I suppose it’s equivalent to a Turing machine, but it’s a weird use of terminology
A digital computer is definitely a FSM. In fact, creating the state diagram of a simple calculator, and mapping that to digital logic by hand, and then building it on a breadboard used to be a staple of most introductory computer architecture courses. Now they just simulate everything. :)
More like a composition of interacting, state machines. Far as computers, one model applied well to many things is Abstract, State Machines. They're like Turing Machines for structures vs tape or whatever. They've been used in verification of hardware and software, too. Asmeta is an example tool.
A real computer is not a state machine nor a Turing machine nor an abstract closed discrete model. It isn't a closed system. It is connected to the rest of the universe through IO, noise sources, and time has meaning there
State machines can have inputs and outputs - the new state is a function of the current state and the current input, the output is a function of the current state and optionally the current input. Noise is just part of the input and time obviously has meaning for state machines, too, as state transitions happen as time progresses.
I'm not saying state machines don't have changing state. I'm referring to the closed world assumption in the model. Also, I'm not saying state machines are not useful models for some types of computer use as in 'all models are wrong, some models are useful'. I use state machines in solutions all the time. It is a very useful pattern.
However, a statemachine model will not let me predict whether my computer driving an actuator will dribble this basketball or just randomly slap it. It is not going to help me predicting the size of a buffer needed to losslesly accept a certain rate of incoming packets.
Now in each of these cases I could extend my initial computer model to capture the relevant information. I could add a clock running 'ticks' for my 'computer', I could add a second clock running 'ticks' for the universe (i know, but let's keep it simple, remember, all models are wrong) and model the external system with wich my 'computer' interacts inside my new model and the above questions could be answered. But now I have no longer modeled a just a computer. You have modeled a closed world universe as a statemachine.
There is a huge difference for me in saying 'some computations can usefully be modeled as a state machine' and, to quote from the article, '[A] Computer, physically, is nothing more than a storage of various states, and combinational logic based on all the states (Program Counter, register values, RAM, Carry Flag, etc.) for state transition.'. Because even though usefull, like Newtinion Physics, or atomic models that look like small planets orbiting a sun can be usefull models, it is not complete. It will never tell me how my linear algebra library needs to be optimized for specific processor dies to minimize thermal throttling.
it is not just an incomplete but a leaky abstraction.
As an aside remember 'Row Hammer' [1]? That was sheer poetry in this regard. Using physical properties of a computer system to influence computation in a virtual computer from a different virtual computer just because they run on the same physical underlying hardware. The computer memory hardware itself was supposed to have abstracted this, the hypervisor was supposed to ahve abstracted the computer, and the VM was supposed to be a computer abstraction on top of the hypervisor.
I see what you mean but I think it is not totally correct to attribute this to a closed world assumption, after all state machines can have inputs and outputs. I would say the important thing is that in most of those scenarios there is an external feedback loop, the output affects future inputs and this makes the behavior unpredictable as you do not know the sequence of inputs unless you can accurately model the effect of the output on the input.
On the other hand that is not really different from a scenario without external feedback where you just do not know the input - if you do not know the sensor input, you can not predict the movement of the actuator but it does not really make a difference whether you just do not know the sensor input for arbitrary reasons or because of unknown effects of the outputs via the actuator on the sensor inputs.
Thermal throttling is a similar example, there is a feedback loop between the computations you perform, the heat this generates, and how the processor reacts to the resulting temperature sensor inputs. The unknown variable is again the sensor input, whether due to heat from the die are me removing the cooling fins.
Row Hammer is an example where the physical implementation has additional state changes not intended by the designer and which are even subject to variation in the production process. If you are just modelling the intended behavior than the model we obviously not be correct in cases were the unintended behavior is relevant.
In the end I would say that a computer is just a state machine as long as you stay in a regime where the physical implementation is not relevant but at some point this will break. But I also think that this is pretty academic, modern computers are so complex that thinking about it as a state machine will almost always not be useful at all, even in the most well behaved scenarios without the physical implementation becoming relevant or complex external feedback loops.
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.
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.)
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.
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.
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.
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.
Comments
Margo Seltzer and folks wrote a fun paper about this a few years back at ASPLOS:
"We present an architecture designed to transparently and automatically scale the performance of sequential programs as a function of the hardware resources available. The architecture is predicated on a model of computation that views program execution as a walk through the enormous state space composed of the memory and registers of a singlethreaded processor. Each instruction execution in this model moves the system from its current point in state space to a deterministic subsequent point. We can parallelize such execution by predictively partitioning the complete path and speculatively executing each partition in parallel. Accurately partitioning the path is a challenging prediction problem. We have implemented our system using a functional simulator that emulates the x86 instruction set, including a collection of state predictors and a mechanism for speculatively executing threads that explore potential states along the execution path. While the overhead of our simulation makes it impractical to measure speedup relative to native x86 execution, experiments on three benchmarks show scalability of up to a factor of 256 on a 1024 core machine when executing unmodified sequential programs."
https://collaborate.princeton.edu/en/publications/asc-automa... and a talk: https://www.youtube.com/watch?v=MHZDXC4zJ0c
speculative memoization on execution states? Wow, that can never be energy efficient, can it?
/update she actually says the word memoization in 22:15, so much for original thought.
Wow, that is fascinating. This should absolutely be pursued further.
This is using the terminology a bit strangely. Usually a Turing machine is something that's in a complexity class above a stack automaton which is in a complexity class above a finite state machine. And then we think of computers as Turing machines because that's helpful but they are in practice finite state machines because they have a limited amount of state. But the equivalence between a Turing machine and a state machine in the article is only true if the state in the state machine can be infinite.
i can extrapolate even further and say that everything is a state machine. humans are a state machine, plants are a state machine, reality itself is a state machine.
we don’t see it like this because of the sheer complexity, but in the end we are a continuous computation that occurs at every moment in time.
I don't think this is true. Continuous transition can't be modeled as a state machine as far as I know.
Not in the standard regime of finite state machines. If you allow for infinite continuous state machines and infinitesimal steps, then it’s no problem. Every classical mechanical system is fully specified by positions and velocities. Transitions follow Newtonian mechanics. Every non-relativistic isolated quantum system is specified by the wave function and the transitions follow the Schrödinger equation.
Isn't this turning into a word game? If we're just saying "reality can be discrete state machines or continuous analog systems which I will call an infinite state machine" then are you really saying anything at all?
Yeah, that’s probably the biggest weakness of this analogy—it’s kind of useless.
for my own clarification purposes: why is finite vs infinite an issue? IMHO, i don’t believe we have truly infinite state unless we’re talking about mathematical abstraction.
Don’t know if it is. But in computer science state machines are usually finite or at least discrete. Time evolution in quantum mechanics is certainly continuous, not discrete. Discrete are only some observables.
i think we maybe are mixing measuring with the actual evolution of the state. you cannot observe a quantum system without altering its state. also, there is no such thing as an isolated quantum system. this is true even for classic mechanics but we are cool with it since the measurement error is insignificant compared to what we measure.
i believe that the number of states a quantum system goes through is finite, albeit maybe very very large and the way we are treating it is based mostly on the tools we have not what is happening in reality.
In practice it doesn't matter at all.
But observables are stochastic, not deterministic.
If you refer to measuring and wave function collapse in QM, then yes, but for that you need interaction with the environment (the observer), that’s why I specified “isolated”. Regardless, even the wave function collapse is a state transition, albeit stochastic. I assume state machines allow for stochastic transitions?
wave function collapse is not an open and shut case. it’s fancy math in place to explain it. there are multiple interpretations of what is going on including the many worlds interpretation and my personal favorite the GWR interpretation.
at the end of the day we don’t know what is going on at that level and we are speculating wildly based on the math we have.
the math is sometimes useful as it has some real life applications - but speculation is speculation
i know it to be truth. if you go down deep enough (talking elementary particle deep) everything is discrete.
So, what do you know that physicists don't? Planck time & length is just the limit of what we can measure.
Can something exist at 0.5 Planck lengths from another thing?
Isn't the answer yes, but we wouldn't be able to measure it?
Why would guess the answer is yes then?
The Planck length is sometimes misconceived as the minimum length of space-time, but this is not accepted by conventional physics, as this would require violation or modification of Lorentz symmetry.[1]
[1] https://en.wikipedia.org/wiki/Planck_length
That is currently unknown. We suspect that the answer is "no", but we don't know.
Isn't it usually assumed spacetime is not discrete. At the very least there is no proof to say everything is discrete. Just because the universe can do computations doesn't mean it is a state machine.
state machine: you have a state that you can describe. you get input, you transform the state, you maybe output something. state transition can also be viewed as input.
so i believe that everything is a state machine. everything
nope. if you want to have your mind blown away look into Wolfram’s cellular automata and more recently his physics project
Wolfram isn't a crank but his graph idea is interesting and not much else at the moment.
IMHO the man is a genius and the idea is brilliant. it’s the only place i’ve seem a reasonable interpretation of the uncertainty principle.
How so? Have you done enough quantum mechanics to comment? I don't think I have
nobody is "doing" quantum mechanics per se. they are applying predictions from a theory that has been around for a while and those predictions work well enough in narrow domains to be useful.
i know enough to understand some of the fancy math behind it, but one thing to keep in mind is that what people think of when they say quantum mechanics is the mathematical model we're working with, not the real thing.
here, take a look for yourself: https://www.wolframcloud.com/obj/wolframphysics/Documents/so...
Genuine question: how do we know that elementary particles are in fact discrete (as opposed to modes on a space continuum)?
That is precisely what quantum fields are, continuous distributions. Coupling is the only reason quanta exist. But propagation is continuous.
I suspect you don't mean mode in the same sense but quantum field theory does model particles as vibrations in a field.
But, those particles have, as good as we can measure, infinitesimal volume
AFAIK they are treated as discrete, ie you cannot break it down more. that may change, but they are viewed as discrete
Are you sure there is such a thing in reality?
Have you ever witnessed an object moving?
What has that got to do with anything? Movies, games etc. all seems to have moving objects. And yet they are all discreet.
the numbers of cells your eye perceives movement with it limited. you brain interpolates like crazy (did you know that most of the stuff you see, you actually don’t see? it’s a result of heavy editing done by the brain). so now the question: are you sure that the movement of an object is continuous?
How are vacuums, pure functions or abstract concepts state machines?
Philosophy has some pretty well fleshed out concepts around simple objects (without proper parts) and intrinsic properties as well that I think would contradict this.
the short answer that you’re not going to like is that everything you’re describing is a human construction. it therefore exists in the minds of people as a concept. we use it because it’s convenient.
a pure function that does not exist anywhere and nobody does not know about effectively does not exist.
philosophy is another things that is a human construction. a lot of our lives is lived inside our heads working with things we made up. it’s convention. you don’t get to ignore physics.
Well I think this is surely a cop out as a state machine is also a concept. Although If you are conceding we can't model all concepts with state machines then I think I'm satisfied.
hahaha. oh nooo. you’re not satisfied :)
the initial discussion was about all physical object. since you cannot have concepts without representing them onto something physical (paper, in the memory of a computer, in brain, etc) it immediately follows that concepts exist only with a state machine substrate. therefore concepts, distilled to their essential components are (insanely large insanely distributed) state machines
I don't think that's true. Not everything in this world follows from another. In a system, there will be things that are true in that system, that can't be derived from previous axioms. If I remember correctly, Godel proved this.
nope. everything follow from something else. you cannot literally create something new. you only transform.
the Godel fellow proved something else: https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
it has to do with logic and formally proving things.
"The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers. "
Doesn't it follow that you can't write a program that proves all the true things about natural numbers. Therefore there will be true facts about the arithmetic of natural numbers not derivable from the axioms. That's my reading of it.
Basically there will be formulas, you can't get to by following an algorithm from the axioms. But if you lets say randomly stumble on a formula, you can easily prove it works or not.
That's my reading of it.
So for example, we can't write a program that will find all formulas, like for example.
a^2 + b^2 = c^2
But once we have a formula, we can prove that this formula works. Thats my understanding of this Theorem. Correct me if I'm wrong.
You certainly can't write a state machine for the halting problem either.
so my original claim was that:
Godel incompleteness applies for math, logic, etc but you need to understand that math is human construct. formulas and numbers don't exist in a void. they need a substrate like a human mind or a computer.
Also by state machine i mean a system is basically a current state + state transitions. I was not using state machine as a way of modeling and solving a problem. That's a narrow definition of a state machine only applicable within a certain domain.
so everything in reality can be seen as a state machine
also as an orthogonal side note to the the halting problem: in theory you may conceive of systems and/or programs that will never halt but remember they are theoretical. Eventually, entropy gets to us all so for anything, even ideas of algorithms that may never halt, is temporary and are guaranteed that given enough time they will halt.
"A Computer is a state machine. Threads are for people who can't program state machines" (Alan Cox)
What does this mean in practise? I think this comes from the days of single core machines where going to multiple threads can't improve performance. But even on a single core device, threading is routinely used because a single state machine becomes to big to easily program
not sure if serious or trolling but this sounds like trolling. the reason we use threads is that they are a higher level abstraction that helps us keep the cognitive load down and focused on the layer we care about.
Surely it isn’t though? A state machine is generally considered to be a finite state automaton, isn’t it? Turing machines are substantially higher up the Chomsky hierarchy than finite state automata.
Edit: take finite out of it, and then I suppose it’s equivalent to a Turing machine, but it’s a weird use of terminology
A digital computer is definitely a FSM. In fact, creating the state diagram of a simple calculator, and mapping that to digital logic by hand, and then building it on a breadboard used to be a staple of most introductory computer architecture courses. Now they just simulate everything. :)
This is the technique http://faculty.etsu.edu/tarnoff/ntes2150/statemac/statemac.h...
It depends on what you combine the state machine with.
State machine + sequential read of a tape = "fsm", regular languages
State machine + sequential read of a tape + stack = "pda" push down automaton aka stack machine, context free languages
State machine + arbitrary read of a tape + memory tape = Turing machine, do anything
But still the state machine is finite.
More like a composition of interacting, state machines. Far as computers, one model applied well to many things is Abstract, State Machines. They're like Turing Machines for structures vs tape or whatever. They've been used in verification of hardware and software, too. Asmeta is an example tool.
A real computer is not a state machine nor a Turing machine nor an abstract closed discrete model. It isn't a closed system. It is connected to the rest of the universe through IO, noise sources, and time has meaning there
State machines can have inputs and outputs - the new state is a function of the current state and the current input, the output is a function of the current state and optionally the current input. Noise is just part of the input and time obviously has meaning for state machines, too, as state transitions happen as time progresses.
I'm not saying state machines don't have changing state. I'm referring to the closed world assumption in the model. Also, I'm not saying state machines are not useful models for some types of computer use as in 'all models are wrong, some models are useful'. I use state machines in solutions all the time. It is a very useful pattern.
However, a statemachine model will not let me predict whether my computer driving an actuator will dribble this basketball or just randomly slap it. It is not going to help me predicting the size of a buffer needed to losslesly accept a certain rate of incoming packets.
Now in each of these cases I could extend my initial computer model to capture the relevant information. I could add a clock running 'ticks' for my 'computer', I could add a second clock running 'ticks' for the universe (i know, but let's keep it simple, remember, all models are wrong) and model the external system with wich my 'computer' interacts inside my new model and the above questions could be answered. But now I have no longer modeled a just a computer. You have modeled a closed world universe as a statemachine.
There is a huge difference for me in saying 'some computations can usefully be modeled as a state machine' and, to quote from the article, '[A] Computer, physically, is nothing more than a storage of various states, and combinational logic based on all the states (Program Counter, register values, RAM, Carry Flag, etc.) for state transition.'. Because even though usefull, like Newtinion Physics, or atomic models that look like small planets orbiting a sun can be usefull models, it is not complete. It will never tell me how my linear algebra library needs to be optimized for specific processor dies to minimize thermal throttling.
it is not just an incomplete but a leaky abstraction.
As an aside remember 'Row Hammer' [1]? That was sheer poetry in this regard. Using physical properties of a computer system to influence computation in a virtual computer from a different virtual computer just because they run on the same physical underlying hardware. The computer memory hardware itself was supposed to have abstracted this, the hypervisor was supposed to ahve abstracted the computer, and the VM was supposed to be a computer abstraction on top of the hypervisor.
I see what you mean but I think it is not totally correct to attribute this to a closed world assumption, after all state machines can have inputs and outputs. I would say the important thing is that in most of those scenarios there is an external feedback loop, the output affects future inputs and this makes the behavior unpredictable as you do not know the sequence of inputs unless you can accurately model the effect of the output on the input.
On the other hand that is not really different from a scenario without external feedback where you just do not know the input - if you do not know the sensor input, you can not predict the movement of the actuator but it does not really make a difference whether you just do not know the sensor input for arbitrary reasons or because of unknown effects of the outputs via the actuator on the sensor inputs.
Thermal throttling is a similar example, there is a feedback loop between the computations you perform, the heat this generates, and how the processor reacts to the resulting temperature sensor inputs. The unknown variable is again the sensor input, whether due to heat from the die are me removing the cooling fins.
Row Hammer is an example where the physical implementation has additional state changes not intended by the designer and which are even subject to variation in the production process. If you are just modelling the intended behavior than the model we obviously not be correct in cases were the unintended behavior is relevant.
In the end I would say that a computer is just a state machine as long as you stay in a regime where the physical implementation is not relevant but at some point this will break. But I also think that this is pretty academic, modern computers are so complex that thinking about it as a state machine will almost always not be useful at all, even in the most well behaved scenarios without the physical implementation becoming relevant or complex external feedback loops.
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.
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.)
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.
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
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.
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