10
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

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 $\lambda$ 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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I admit I got a little confused. I understand from your answer that modern computers are not based on Turing Machines. If so, what I'd like to know is - for the most low-level, calculating stuff part of the computer (correct me if I'm wrong - but I assume that the ability to do mathematical calculations is the most fundamental and 'low-level' ability of any computer, that allows everything else to happen), what theoretical model could explain how this is done? I'd really like to understand a simplified version of the most basic aspect of how computers work. $\endgroup$
    – Aviv Cohn
    Mar 5, 2014 at 20:20
  • 1
    $\begingroup$ You can try reading The elements of computing systems. Modern hardware is implemented using transistors, which implement logic gates, flip-flops and other memory devices. The hardware implements a RAM machine on machine words (typically nowadays 64 bits each). Software is built on many layers, but the lowest level it gets to see is this RAM machine. $\endgroup$
    – Yuval Filmus
    Mar 5, 2014 at 21:02
  • 1
    $\begingroup$ ??? PTime computation "a theorertical notion whose usefulness in practice is doubtful"? huh? $\endgroup$
    – vzn
    Mar 6, 2014 at 3:59
  • $\begingroup$ @vzn For me the P vs. NP question has absolutely no practical relevance. $\endgroup$
    – Yuval Filmus
    Mar 6, 2014 at 6:01
  • $\begingroup$ Random-access stored-program machine may be more similar to the hardware of computer. $\endgroup$
    – hellohawaii
    Oct 18, 2022 at 10:57
1
$\begingroup$

all modern computers are basically built on the Von Neumann architecture which is essentially central processing unit CPU plus memory, and a stored program where CPU also includes arithmetic/logic unit ALU.

notice that the Turing machine basically has the same "architecture," esp the universal computer, which can run programs stored on the tape. the state table and tape head functions somewhat like the CPU (in this analogy the ALU would be a subset of all TM states that control arithmetic logic) and the tape as memory. of course many early real computers even used "tapes" to store data (and this continues in some contexts eg mass storage systems). the analogy can be further strengthened with a binary "symbol alphabet" on the tape. there are also multihead TMs studied just like with real computers.

TCS complexity theory studies physical entities operated on by the abstract TM namely space and time both which have "continuum/divisibility" like properties as in the real physical case. the TM is said to do "work" as it calculates/ moves, also a physical concept. many deep TCS theorems show deep interrelationships between space and time just as there are strong physical concepts eg "velocity". ie overall there are deep connections between TCS and physics. (never forget the TM is literally a machine!)

in short there are various strong conceptual/metaphorical similarities between a TM and the modern computer although depending on the context this may be either emphasized or downplayed (not surprisingly leading to some perplexity by students). a key difference is that the TM has infinite memory on the tape, in computers this is only "approximated" (so to speak) by large memories.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ In the subfield of algorithms, people often study RAM machines, apparently since they form a better model of real-world computation. Although Turing machines p-simulate RAM machines, RAM machines are much more efficient. You (probably) can't sort numbers in $O(n\log n)$ using a Turing machine. Random access is very important in practice. $\endgroup$
    – Yuval Filmus
    Mar 6, 2014 at 5:56
  • $\begingroup$ @YuvalFilmus what does p-simulate mean? $\endgroup$
    – Balázs Börcsök
    Sep 19, 2021 at 10:56
  • $\begingroup$ Simulate with a polynomial overhead (in terms of time complexity). That is, an algorithm running in time $T(n)$ on one model, can be simulated by an algorithm running in time $CT(n)^C$ on the other model, for some fixed constant $C$. $\endgroup$
    – Yuval Filmus
    Sep 19, 2021 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.