7 ms·
Every Computer System Is a State Machine
- diegocg 6y ago"A Computer is a state machine. Threads are for people who can't program state machines" (Alan Cox)
- rantwasp 6y agonot 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.
- barbegal 6y agoWhat 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
- aphextron 6y agoWouldn'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 agoUh.. non deterministic state machines can all be expressed as deterministic state machines. This also has nothing to do with P vs NP
- frabert 6y agoDo 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 agoA 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 agoYou'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 agoWell 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]
- 6y ago
- epaulson 6y agoMargo 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-automatically-scalable-computation https://collaborate.princeton.edu/en/publications/asc-automa... and a talk: https://www.youtube.com/watch?v=MHZDXC4zJ0c https://www.youtube.com/watch?v=MHZDXC4zJ0c
- lachlan-sneff 6y agoWow, that is fascinating. This should absolutely be pursued further.
- hbogert 6y agospeculative 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.
- rantwasp 6y agoi 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.
- aptxkid 6y agoI don't think this is true. Continuous transition can't be modeled as a state machine as far as I know.
- rantwasp 6y agoi know it to be truth. if you go down deep enough (talking elementary particle deep) everything is discrete.
- ImprobableTruth 6y agoSo, what do you know that physicists don't? Planck time & length is just the limit of what we can measure.
- fenwick67 6y agoCan something exist at 0.5 Planck lengths from another thing?
- AnimalMuppet 6y agoThat is currently unknown. We suspect that the answer is "no", but we don't know.
- SketchySeaBeast 6y agoIsn't the answer yes, but we wouldn't be able to measure it?
- nickpsecurity 6y agoMore 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.
- PeterStuer 6y agoA 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
- danbruc 6y agoState 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.
- PeterStuer 6y agoI'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.
- pedrocr 6y agoThis 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.
- deleted 6y ago[deleted]
- noodlesUK 6y agoSurely 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
- esmi 6y agoA 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.htm http://faculty.etsu.edu/tarnoff/ntes2150/statemac/statemac.h...
- froh 6y agoIt 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.