I am a high school student in the twelfth grade. I study high-level programming,

Question

I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science.

I have recently started to understand what a Turing Machine is. I wanted to ask:

I understand that a Turing Machine is a hypothetical device used to explain the mechanisms of computing.

But is a Turing Machine conceptually the actual very basis of computers? (In the most basic level). Or do real world computing mechanisms and the Turing Machine mechanism (way of calculating things) have very little in common?

Explanation / Answer

Turing machines were invented by Turing in his 1936 paper on computable numbers and the halting problem. It was one of a few models floating around at that time (like Church's ? calculus, which had been defined earlier). All these models have later been shown equivalent, so if you're only interested in computability, then the Turing machine model is as good as any other model.

Modern computers are not based on the Turing machine model. Turing machines are very slow, and don't represent the capabilities of hardware. From the software side, a modern computer is similar to the RAM machine, which allows indirect addressing and has an unlimited "alphabet" (its registers hold arbitrarily large integers), though actual machines have limited registers, and this sometimes makes a big difference (for example, when doing arithmetic on large numbers). I don't know of a good model for the hardware side; Boolean circuits, popular in theoretical computer science, model neither memory nor iterative computation.

Turing machines are polynomially equivalent to RAM machines with polynomially bounded registers. That means that both machines provide the same notion of efficient computation (polynomial time computation), a theoretical notion whose usefulness in practice is doubtful. In contrast, (bounded) RAM machines form a reasonable model for actual computation, and so complexity results for RAM machines have practical relevance. However, even this model ignores some important complexities of modern computers, such as the speed of access to different kinds of memory (disk, main memory, different caches).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.