Problem Detail: It is said that “The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.” [Wikipedia] So on which model current machines are built?
Asked By : user5507
Answered By : Raphael
The one closest to typical CPUs is probably the register machine or random access machine (RAM). A RAM has
- an infinite number of registers, each of which stores an arbitrarily large number,
- a set of operations on these registers (typically ${+ 1, = 0}$),
- a programming language including these operations as well as control structures for looping/branching (until/if some register holds $0$) and
- a program counter pointing to the next operation (in some program).
Real CPUs are quite similar, with some changes:
- There are only finitely many registers (which may exist only virtually), and each stores only numbers of bounded size.
- There are more operations.
Apart from that, it’s very close indeed. It is common to extend the RAM model to account for memory hierarchy, which makes results a lot more applicable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6528 Ask a Question Download Related Notes/Documents
