Every Computer System Is a State Machine
blog.the-pans.com
blog.the-pans.com
"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
/update she actually says the word memoization in 22:15, so much for original thought.
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.
But, those particles have, as good as we can measure, infinitesimal volume
so i believe that everything is a state machine. everything
Wolfram isn't a crank but his graph idea is interesting and not much else at the moment.
How so? Have you done enough quantum mechanics to comment? I don't think I have
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...
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.
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
Are you sure there is such a thing in reality?
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.
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.
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
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.
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.
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
This is the technique http://faculty.etsu.edu/tarnoff/ntes2150/statemac/statemac.h...
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.
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.
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.
This also has nothing to do with P vs NP
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.
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.)
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.
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.
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.