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