68

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

  1. Is there any relation between these two models? Was the Von Neuman model based on or inspired by the Turing model?

  2. Can we say that Turing model is a superset of Von Newman model?

  3. Does functional Programming fit into Turing model? If so, how? I assume functional programing does not lend itself nicely to the Von Neuman model.

nbro
  • 15,395
  • 32
  • 113
  • 196
Santhosh
  • 6,547
  • 15
  • 56
  • 63

6 Answers6

58

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.

Jonik
  • 80,077
  • 70
  • 264
  • 372
Dario
  • 48,658
  • 8
  • 97
  • 130
  • Crisp Expanation. However, can a Von Neuman architecture implement everything that a Turing machine can describe? – Santhosh May 06 '10 at 15:21
  • 4
    @Santosh: Theoretically, no actual real computer can do that and none ever will - because a Turing machine requires an *infinite* amount of storage. – Michael Borgwardt May 06 '10 at 15:33
  • 6
    Any Turing computable function is necessarily described by a Turing machine *which halts*. A Turing machine which halts cannot require infinite storage (how could it read or write infinitely much data in finite time?). Therefore, anything computable by a theoretical Turing machine can be computed by a practical computer with sufficient storage. The storage required may be arbitrarily large, but it will not be infinite. – Tyler McHenry May 06 '10 at 16:45
  • @Tyler: Isn't an infinite loop turing-computable too? And of course it doesn't halt ... – Dario May 06 '10 at 17:01
  • @Dario: Not in the formal sense of "computable" it isn't. A Turing computable function is *defined* as a function `f` for which for every input `n` there exists a Turing machine that halts and outputs `f(n)`. It's pretty much synonymous with "algorithm", and one of the parts of the definition of an algorithm is that it must have finitely many steps, which an infinite loop does not. – Tyler McHenry May 06 '10 at 18:34
  • 1
    @Tyler: shouldn't that be "there exists a Turing machine that, for every `n` in the domain of `f`, halts and outputs `f(n)`"? I don't think that `f` is allowed to have a separate Turing machine for each input. – Michael Ekstrand May 06 '10 at 21:34
  • @Michael Yes, you're correct; I got my wording mixed up. Good catch. – Tyler McHenry May 06 '10 at 21:37
  • @Dario Are modern computers based on Von-Neumann architecture? If the answer to the last question is yes: You also say that the Von-Neumann architecture implements the Turing machine model, but I thought modern computers are [RAM](https://en.wikipedia.org/wiki/Random-access_machine) based on and not Turing machine model based? – Honinbo Shusaku Jul 20 '15 at 14:26
  • @HoninboShusaku RAM is quite literally a limited model of Turing System, the whole point about a Turing system is you have a tap columns per bit that is exactly what ram is just digital instead of tape, E.G an address of 0xFFF0 is column 65520 if it were on a tape, @Micheal `f()` is allows to have a separate Turing machine it was required for the proof that published the Turing machine quite literally the halting problem was `f( f( n ) )` would it run forever or halt, read the paper it's a good read and well published now. – Barkermn01 Jul 08 '23 at 19:15
17

Generally one refers to the Von Neumann architecture, as contrasted with the Harvard architecture. The former has code and data stored in the same way, whereas the latter has separate memory and bus pathways for code and data. All modern desktop PCs are Von Neumann, most microcontrollers are Harvard. Both are examples of real-world designs that attempt to emulate a theoretical Turing machine (which is impossible because a true Turing machine requires infinite memory).

rmeador
  • 25,504
  • 18
  • 62
  • 103
  • 1
    Thanks for bringing up the contrast w.r.t Harvard Architecture as opposed to Turing Machines – Santhosh May 06 '10 at 19:04
  • 5
    @Santhosh: perhaps it was just a typo, but I did _not_ bring up any such contrast. As I said in my answer, both Von Neumann and Hardvard architectures are Turing machines. The contrast between them is their memory layout. – rmeador May 06 '10 at 19:18
5

Turing model defines computational capabilities without getting deep into implementation, no one will ever create computer that will look like Turing Machine literally. (Except enthusiasts http://www.youtube.com/watch?v=E3keLeMwfHY ).

Turing model is not architecture.

Von Neuman is guidance how to build computers. It says nothing about the computation capabilities. Depending on instruction set the produced computer may or may not be Turing complete (means can solve same tasks as Turing Machine)

Functional programming (lambda calculus) is another computational model that is Turing complete but can't be natively fit into Von Neumann architecture.

Andrey
  • 59,039
  • 12
  • 119
  • 163
4

I do not know what historical relationship there is between Turing machines and von Neuman architectures. I am sure, however, that von Neuman was aware of Turing machines when he developed the von Neuman architecture.

As far as computational capability, however, Turing machines and von Neuman machines are equivalent. Either one can emulate the other (IIRC, emulating a von Neuman program on a Turing machine is an O(n^6) operation). Functional programming, in the form of the lambda calculus, is also equivalent. In fact, all known computational frameworks at least as powerful as Turing machines are equivalent:

  • Turing machines
  • Lambda calculus (functional programming)
  • von Neuman machines
  • Partial recursive functions

There is no difference in the set of functions that can be computed with any of these models.

Functional programming is derived from the lambda calculus, so it doesn't map directly to either Turing or von Nemuan machines. Either of them can run functional programs, hoewver, via emulation. I think that the mapping for Turing machines is likely more tedious than the mapping for von Neuman machines, so my answer to the 3rd question would be "no, in fact it's worse."

Michael Ekstrand
  • 28,379
  • 9
  • 61
  • 93
0

The Turing "model" is not an architectural model at all. It was just a non-existent machine that Turing hypothesized to serve as the vehicle for his proof of the decision problem.

Dinah
  • 52,922
  • 30
  • 133
  • 149
0

The easy way to understand the difference is... von Neumann stretched Turing's alpha-machine concept to support more than one algorithm in shared, centralized, unprotected memory. This led away from Alonzo Church's Lambda Calculus and functional programming to RISC instructions, dangerously shared static addressing, the dictatorial superuser, central operating systems, virtual memory, virtual machine, and endless cybercrime. Instead, the Turing Machine was intended as the Lambda engine of the Lambda Calculus, creating virtual functions (instead of virtual machines). Remember, Alan Turing was Alonzo Church's doctoral student in 1936 and 1937. They intended Alonzo Church's symbolic, functional modularity to encapsulate and protect the single algorithm as a simple binary computer to implement their Church-Turing Thesis. Lambda machine code enforces functional programming as a better and more powerful computer using immutable names, object-oriented programs, and Capability-Based Addressing. The binary computer (either Turing's or von Neumann's), when encapsulated this way, creates a Church-Turing Machine with six additional Church Instructions to programmatically control an application namespace, a thread of execution, secure call and return to subroutine abstractions, programmed functions, and binary objects, as explained in Civilizing Cyberspace: The Fight For Digital Democracy

Kenneth J Hamer-Hodges
  • 1
  • 1