3 ms·
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 Chomsk
by noodlesUK 6y ago
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
- 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.