Turing machine vs Von Neuman machine

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.

Leave a Comment

tech