Turing machine vs Von Neuman machine
Background
The Von-Neumann architecture describes the stored-program computer where instructions and data are stored in memory and the machine works by changing its internal state, i.e an instruction operates on some data and modifies the data. So inherently, there is state maintained in the system.
The Turing machine architecture works by manipulating symbols on a tape. i.e A tape with infinite number of slots exists, and at any one point in time, the Turing machine is in a particular slot. Based on the symbol read at that slot, the machine can change the symbol and move to a different slot. All of this is deterministic.
Questions
Is there any relation between these two models? Was the Von Neuman model based on or inspired by the Turing model?
Can we say that Turing model is a superset of Von Newman model?
Does functional Programming fit into Turing model? If so, how? I assume functional programing does not lend itself nicely to the Von Neuman model.
Answer
Turing machines are theoretical concepts invented to explore the domain of computable problems mathematically and to obtain ways of describing these computations.
The Von-Neumann architecture is an architecture for constructing actual computers (which implement what the Turing machine describes theoretically).
Functional programming is based on the lambda-calculus, which is a another method of describing computations or - more precisely - computable functions. Though it uses a completely different approach, it is equally powerful to Turing machine (it's said to be turing complete).
Every lambda-calculus program (term) T is written just using a combination of
- variables like
x - anonymous functions like
λx. T - function applications
T T
Despite being stateless, this is sufficient for every computation a computer can do. Turing machines and lambda terms can emulate each other, and a Von-Neumann computer can execute both (apart from technical restrictions like providing infinite storage, which a turing machine could require).
But due to their stateless and more abstract nature, functional programs might be less efficient and less "intuitive" on Von-Neumann computers compared to imperative programs which follow it's style of binary, memory and update.