Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: