Every Computer System Is a State Machine

Margo Seltzer and folks wrote a fun paper about this a few years back at ASPLOS:<p>&quot;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.&quot;<p><a href="https:&#x2F;&#x2F;collaborate.princeton.edu&#x2F;en&#x2F;publications&#x2F;asc-automatically-scalable-computation" rel="nofollow">https:&#x2F;&#x2F;collaborate.princeton.edu&#x2F;en&#x2F;publications&#x2F;asc-automa...</a> and a talk: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=MHZDXC4zJ0c" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=MHZDXC4zJ0c</a>

This is using the terminology a bit strangely. Usually a Turing machine is something that&#x27;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&#x27;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.<p>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.

&quot;A Computer is a state machine. Threads are for people who can&#x27;t program state machines&quot; (Alan Cox)

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

More like a composition of interacting, state machines. Far as computers, one model applied well to many things is Abstract, State Machines. They&#x27;re like Turing Machines for structures vs tape or whatever. They&#x27;ve been used in verification of hardware and software, too. Asmeta is an example tool.

A <i>real</i> computer is not a state machine nor a Turing machine nor an abstract closed discrete model. It isn&#x27;t a closed system. It is connected to the rest of the universe through IO, noise sources, and time has meaning there

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