Stack OverflowWhat is the relationship between Turing Machine & Modern Computer?
[+6] [7] smwikipedia
[2010-03-31 06:22:52]
[ c computer-science computer-architecture turing-machines ]

Possible Duplicate:
What is the relationship between Turing Machine & Modern Computer ? [1]

I heard a lot that modern computers are based on Turing machine. I just cannot build a bridge from a conceptual Turing Machine to a real modern computer. Could someone help me build this bridge?

Below is my current understanding.

I think the computer is a big general-purpose Turing machine. Each program we write is a small specific-purpose Turing machine. The classical Turing machine do its job based on the input and its current state inside and so do our programs.

Let's take a running program (a process) as an example. We know that in the process's address space, there's areas for stack, heap, and code. A classical Turing machine doesn't have the ability to remember many things, so we borrow the concept of stack from the push-down automaton. The heap and stack areas contains the state of our specific-purpose Turing machine (our program). The code area represents the logic of this small Turing machine. And various I/O devices supply input to this Turing machine.

(2) "A classical Turing machine doesn't have the ability to remember many things" is plain wrong. The tape of the Turing machine is unlimited. - ammoQ
Thanks, ammoQ, It seems I mistake it for Finite Automaton. - smwikipedia
[+8] [2010-03-31 06:58:00] Charles E. Grant [ACCEPTED]

Turing wasn't trying to come up with any sort of practical computer architecture. He was trying to answer the question "What can be computed?". The Turing machine is an abstraction designed to make it relatively easy to reason about what can be computed. Real computers are in no way implementations of Turing machines. However, because we can use real computers to simulate Turing machines we know that any problem a Turing Machine can solve, a real computer can solve as well (modulo issues of finite memory).

The first half of XX century saw many mathematicians working on philosophical questions concerning maths: what can be computed? what does a calculation mean? what's the relationship between mathematics and physical reality? what's the source of truth in mathematics? - Tadeusz A. Kadłubowski
But the Turing machine isn't even really good for reasoning about that. Computability theory works by implementing X in Y, which the original question is addressing. The Turing Machine was probably intended to be analogous to a real computer, with the state machine as a CPU and tape as permanent storage. Turing worked with early implementations. Lambda Calculus predates the Turing Machine, and computers go back to Babbage's designs. The Turing Machine just wasn't as important as those other two breakthroughs. - Potatoswatter
No, the Turing machine was not intended to be analogous to a real computer, at least in the modern sense of the word. The Turing machine was intended to be analogous to a real human. That's why it uses paper tape, for example: an infinitely long one-dimensional strip of paper is equivalent to the two-dimensional sheets of paper we use (just cut them into stripes and glue them together and you get paper tape). That's why it uses symbols (or sometimes colors) instead of zeroes and ones. - Jörg W Mittag
It's no coincidence that he published his results in a philosophical journal, not a mathematical, technical, engineering or computer science one. - Jörg W Mittag
(1) @Jorg: there were few computer science journals back in mid-30's. ;) - Tadeusz A. Kadłubowski
@Jorg: Paper tape was the computer storage storage medium of choice at the time. There's no analogy about it, read up on history. Also read about Alonzo Church and Charles Babbage… Turing did not invent computer science, and the discipline was already well-connected with math. - Potatoswatter
@Potatoswatter: the reference to the use of paper tape as it was used in the 1910's-1980's is a red herring. It was a write-once/read-many media. A key attribute of the notional Turing 'paper tape' was that it could be erased. I am, by the way, old enough to have actually used paper tape to store programs. Your point about Church is well taken, Babbage less so. Babbage came up with an almost-practical scheme for a real computer, but never dealt with the theoretical issues of the limits of computation. - Charles E. Grant
[+3] [2010-03-31 06:51:31] Stephen Canon

Saying that actual computers are "based on Turing machines" is misleading at best.

The Turing machine is a useful abstraction for studying the theory of computation and complexity, but it bears little resemblance to actual computing hardware, current or historical.

[+2] [2010-03-31 06:52:48] zoul

There are many parallels to be found in the modern hardware and software and the Turing machine, but I think the main point is that the TM is a simple mathematical model that can be used to reason about our machines and software. There are things in modern computers that wouldn’t fit quite well in a Turing machine, but that’s an implementation detail. The basic bond is that both machines are functionally equivalent and therefore you can use the TM to explore the possibilities of computers using a much more simple and therefore usable model.

P.S. I cannot resist posting [1] :)


Thanks, zoul. That TM show is incredible! - smwikipedia
[+1] [2010-03-31 06:40:56] Nick Dandoulakis

The hardware is close to the turing machine model, not the software.
Memory array plays the role of the Tape, registers, like ip (instruction pointer) usually play
the role of the Head.

Of course you can emulate turing machines with software, but software generally deals
with higher level, more abstract, concepts.

[+1] [2010-03-31 06:47:33] Potatoswatter

The Turing Machine isn't a particularly good analogy. It's extremely hard to program directly.

The stack and heap constructs come from C. They aren't fundamental to computation. What really matters is that

  • The machine has some kind of state: the contents of the tape, the position of the head, and the current finite-state automaton state.
  • There is a rule that tells it how to modify that state: cross-reference the automaton state and data under the head and perform the appropriate actions in the table.

There are a quite a few problems here: too many different components, three different kinds of state plus the automaton table, no obvious way to model concurrency or self-modifying code. But given that the machine has state and it has rules for performing transformations upon it, you can theoretically build arithmetic, a stack, a heap, etc.

It's easier to write a program in Lambda Calculus [1]; I'd recommend that for a fundamental view of computation.

Alternately there are one-instruction set computers [2], real-world assembly language, and elegant real-world machine models like Forth [3], which is easy to program and to translate into a physical computer.

You don't get anywhere by learning a mathematical construct except to understand the specific math it models. And the easier a computer is to program, the easier it is to understand that it's universal.


[0] [2010-03-31 07:35:03] Nick Lewis

The Turing model is merely a theoretical way to analyze computability. It is one of the simplest known forms of the most powerful known machine. It's misleading to attempt to say that one is similar to the other in anything but computing power. They are equivalent, but they don't have corresponding parts.

[0] [2010-12-13 07:50:55] Avinash

As far as I understand,modern OS environment could be thought of as T-machine with following differences : 1.We have actually three tapes: input tapes that are read only; output tapes that are write-only and memory where both operations are allowed. In theoretical T-machine there is just one tape that combines all the functions. 2.Random access memory in contrast to sequential access memory as in hypothetical T-machines. 3.OS can execute multiple programs simultaneously. 3.Memory is finite in the case of real-world computers.