by Leroy on May 7th, 2023.
I've recently learned that calling your computer a Turing Machine is a controversial statement. There seems to be a belief that Alan Turing created a machine with tape and some symbols on it and then wrote down findings about that machine. There also seems to be a belief that our physical machines somehow fundamentally differ from that of the Turing Machine. I want to illustrate some ideas, with the help of some arguments, so we can better understand that our computers really are computing machines, just as Turing has envisioned, and we can call them Turing Machines comfortably.
I created the above image and placed it here on purpose. It may make more sense if you know it is an imitation of a famous work named The Treachery of Images.
When Alan Turing wrote his paper, "On Computable Numbers" [1], he used the words "tape", "symbol", "scanned", "machine" not to create the above mental image in your head, but to illustrate ideas of computing machines in general. I didn't put those words in quotes accidentally, the first time Turing defines these words in his paper, he uses quotes because they are not literal definitions. Here is some visual proof, but you can confirm in his paper (pg. 231).
In his paper, Turing wasn't interested in designing a machine with tape and
symbols, he was interested in the formal description of computing machines and
their capabilites. His formal description assumes an infinite "tape", but he
used "tape" because it was convenient, not because he thought of using a literal
tape. He compares the "tape" to paper several times throughout. Why paper?
Because Turing was building a computing machine and the term "computing" at the
time meant calculating math, by hand, on paper, with the goal of getting
a concrete answer. So, by calculating 2 + 12 / 3 by hand, on paper, you are
computing. Turing was creating a machine to compute math instead of having
teams of literal people doing
it.
This is why images are treacherous. Turing, a great mind, used some images to illustrate that a computing machine could even be possible because, before him, we did not have computers -- not in the way we think of the term "computer" today. Now, his illustration has become the definition of a Turing Machine, with a tape and symbols, when what he really described was a mathematical framework.
Turing defined a mathematical framework for literally writing down the individual states of what he defined as "automatic machines", machines where each and every motion, or mechanical operation, of them is completely determined by its configuration. Turing goes into great detail about the configurations which look something like this (pg. 235):
This methodology he created is the foundation for our binary computers. There is the insistence that Turing created a machine which reads symbols like the words you are reading right now -- symbols like "A", "B", "α", and "cat". Again, he used the word "symbol" as a mere illustration and also because he was speaking directly to other mathematicians who understood that "α" could be a variable.
Here is Turing in his own words: "A machine can be constructed to compute the sequence 010101...." (pg. 233). And once more, "As a slightly more difficult example we can construct a machine to compute the sequence 001011011101111011111..." (pg. 234).
Your computer is a Turing Machine, with the definition of a Turing Machine being a machine that can compute any function that Turing's automatic machine can compute. I had to dance around some specific wording there because of the treachery of images -- I cannot talk about the Turing Machine complexity class without the visual image of a tape-machine coming into view.
Your computer really is a Turing Machine because it reads "symbols" from
a "tape". We have built actual tape-machines, but we understand they are slow
and obtuse and not really practical. But the "tape" was just an illustration of
an idea. Just as Turing formalized his machine descriptions in binary, ones
and zeroes, so too have we created a "tape" from ones and zeroes. We have
RAM, and
SRAM, and hard
drives, and solid-state disks which our computers, our machines, use to read
"symbols". Our symbols are in ones and zeroes too. Your computer is capable of
reading up to 2^64 symbols, which is the number of possible values a 64-bit
CPU is capable of handling.
When Turing used the words "tape" and "symbol" and "machine", he did so because computers, in our modern sense, had not been created. We barely think of our computers as a machine, but they are. Your computers are machines capable of executing other machines. This may seem crazy, but realize that if you are writing a program in a Turing-complete language, like the C programming language, then you are writing the definition of a machine. Your computer can then read in that definition and execute it. Our computers are machines which can read in the configuration of a machine, be configured by it, and then execute in that configuration -- a machine of the same description that Turing formulated, a Turing Machine.