What is the relationship between Turing Machine & Modern Computer ?

Question

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

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.

Answer 1

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.

Answer 2

http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines

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; I'd recommend that for a fundamental view of computation.

Alternately there are one-instruction set computers, real-world assembly language, and elegant real-world machine models like Forth, 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.

Answer 3

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.

Answer 4

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 aturingmachine.com :)

Answer 5

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).

Answer 6

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.