lpetrich
Contributor
Automata theory has an nice diagram showing which of its models of computation ( Model of computation) are subsets of which others. Combinational logic describes a memoryless system.Output = f(input)
Finite-state machine or finite-state automaton is a system with an internal state register, a writable memory that contains a symbol.New state = f(input, old state)
Pushdown automaton has an internal state register, and also a pushdown stack, a memory whose contents are symbols that are manipulated in Last In, First Out (LIFO) fashion.(New state, stack action) = f(input, old state, symbol of top of stack)
where (stack action) is any of (do nothing), (add symbol to top of stack), (write symbol at top of stack), and (remove symbol from top of stack)
Turing machine has an internal state register, and an infinitely-long tape memory, a memory whose contents are a string of memory cells, each one containing a symbol, and a read/write head.(New state, tape action) = f(input, old state, symbol in tape at head's location)
where (tape action) is any of (do nothing), (write symbol value at head's location), (move head forward one cell), and (move head backward one cell)
A pushdown automaton is a subset of a Turing machine.
A sufficiently-capable Turing machine can simulate any other Turing machine, something called Turing universality. A Turing-complete system is equivalent to a universal Turing machine, though when assessing Turing completeness, finiteness is usually ignored. That aside, Turing completeness is having (1) arbitrary array accessing (random access over an array's entire length) and (2) conditional branching (change control to a different location only if some condition is satisfied).
Essentially every computer CPU has been Turing-complete, though some computing hardware, like FPGA's, are not, in general, Turing-complete. Most common programming languages are also Turing-complete, though there are some exceptions like HTML.
It looks as if a resource-limited Turing machine is as far as one can go in physically realizable models of computation.