<p>You certainly are right that if someone says &quot;a physical computer is just a Turing machine&quot; then they are telling a bit of a stretcher.  More accurate would be something like &quot;anything that can be computed on a physical computer can be computed on a Turing machine.&quot;  Still more accurate would be &quot;A Turing machine is an idealization of physical computing device. It is an idealization in that we don't limit ourselves to any particular fixed scratch memory limits, etc. Anything that can be computed on a general purpose computer can be computed on a Turing machine, and the converse holds if we don't bind ourselves to the limits of the general purpose device, such as address spaces of RAM, etc.&quot;</p>
<p>The sense in which &quot;a physical computer is just a Turing machine&quot; is if when you are programming you think, &quot;I am going to write a program to compute this, and I am just not going to worry about what happens if the input is too long to fit on the hard disk.&quot;  My experience with introduction to programming courses is that they do take that model, so perhaps that is what the people meant in those lectures.</p>

CC BY-SA 4.0
2023-01-21T22:14:37.883Z
2023-01-21T22:14:37.883Z
Jim Hefferon
<p>In several talks and lectures, I've heard people saying that a <strong>physical computer</strong> is just a <strong>Turing machine</strong> but I'm unable to justify this analogy.</p>
<p>My apprehension is the following: Without loss of generality, I can consider physical computer as a machine that follows instructions of a code written in C / assembly language with its unit operations being carried out in the transistors in its hardware. But the inner workings of a computer in no way seems to emulate the instructions of the user code in terms of the 7-tuple <span class="math-container">$Q, \tau, b, \Sigma, q_0, F, \delta$</span> that performs Turing machine-type operations.</p>

CC BY-SA 4.0
2023-01-21T02:15:34.720Z
[https://en.wikipedia.org/wiki/Church–Turing_thesis](https://en.wikipedia.org/wiki/Church–Turing_thesis)
Neal Young
CC BY-SA 4.0
2023-01-22T17:48:34.590Z
Physical computer is just FSA since it has finite memory.
Mohammad Al-Turkistany
<turing-machines><universal-turing-machines><church-turing-thesis>
Equivalence of a physical computer and Turing machine
Akshay Bansal
# Equivalence of a physical computer and Turing machine

(Asked by: username_0 on 2023-01-20)

In several talks and lectures, I've heard people saying that a **physical computer** is just a **Turing machine** but I'm unable to justify this analogy.

My apprehension is the following: Without loss of generality, I can consider physical computer as a machine that follows instructions of a code written in C / assembly language with its unit operations being carried out in the transistors in its hardware. But the inner workings of a computer in no way seems to emulate the instructions of the user code in terms of the 7-tuple $Q, \tau, b, \Sigma, q\_0, F, \delta$ that performs Turing machine-type operations.

**Tags:** turing-machines, universal-turing-machines, church-turing-thesis

> **Comments:**
> **username_1**: [https://en.wikipedia.org/wiki/Church–Turing_thesis](https://en.wikipedia.org/wiki/Church–Turing_thesis)  
> **username_2**: Physical computer is just FSA since it has finite memory.  

---

## 1 answers

### Answer by username_3 on 2023-01-21. Score: 5 | Accepted answer

You certainly are right that if someone says "a physical computer is just a Turing machine" then they are telling a bit of a stretcher. More accurate would be something like "anything that can be computed on a physical computer can be computed on a Turing machine." Still more accurate would be "A Turing machine is an idealization of physical computing device. It is an idealization in that we don't limit ourselves to any particular fixed scratch memory limits, etc. Anything that can be computed on a general purpose computer can be computed on a Turing machine, and the converse holds if we don't bind ourselves to the limits of the general purpose device, such as address spaces of RAM, etc."

The sense in which "a physical computer is just a Turing machine" is if when you are programming you think, "I am going to write a program to compute this, and I am just not going to worry about what happens if the input is too long to fit on the hard disk." My experience with introduction to programming courses is that they do take that model, so perhaps that is what the people meant in those lectures.


---

