David Berlinski, The Devil's Delusion: Turing machine and abacus
Posted on September 18, 2010
by Tommy McGuire
David Berlinski, The Devil's Delusion, page 173If the brain is a computer, then the very same thesis about the human mind should be in force whether we describe the human mind as a digital computer or whether we describe the human mind in terms of a device that is logically identical to a digital computer---an abacus, say. The thing is a trifle. Made of wood, it consists of a number of wires suspended in a frame and a finite number of beads strung along the wires. Nevertheless, an idealized abacus has precisely the power of a Turing machine, and so both the abacus and the Turing machine serve as models for a working digital computer. By parity of reasoning, they also both serve as models of the human mind. [Emphasis mine.]Um, no. (What the heck is an "idealized" abacus, anyway?)
I originally posted this quote in haste, and did not take time to consider exactly what the difference between an abacus (even an "idealized" one) and a Turing machine is. After thinking about it for a bit, I would like to take some time to expand on that difference.
I have no real clue what Berlinski means by an "idealized abacus", but I will be what I believe to be generous and grant that it includes the usual abacus manipulations (for example, see the Abacus Tutorial), which means addition, subtraction, multiplication, and (why not?) division. As a result, the question, "What is the computational power of an abacus?" can be reduced to, "What is the computational power of modular arithmetic?"
Why modular arithmetic? Because an abacus only has a finite "number of wires suspended in a frame and finite number of beads strung along the wires". Now, assuming the abacus and the rules of its use do not involve overflow exceptions, what happens when you add one to the maximum number that an abacus with a finite number of beads can represent? That number will be something along the lines of 999....999; adding one results in [1]000...000, or a represented zero.
As a result, I believe it turns out that the primary, the key, difference between an idealized abacus and a Turing machine is precisely the same as the difference between modular arithmetic and full-on, hard-core, all-out, normal arithmetic. A Turing machine has unlimited storage; in fact, unlimited, effectively random-access storage. An abacus does not. A Turing machine includes an unbounded tape on which it is capable of manipulating any number. An abacus can only manipulate numbers with fewer than a given number of digits.
The reason that is the key difference is named Kurt Gödel. Gödel numbering allows any well-formed formula of a formal language to be represented by a number, and any inference rule of the language to be represented by a function on those numbers. As a result, if I am not mangling things too much, normal arithmetic is capable of expressing a formal system strong enough to encounter Gödel's incompleteness theorems; is potentially as powerful as Turing machines.
Unfortunately for Berlinski, modular arithmetic is not that powerful. Unfortunately for me, I do not know exactly how powerful it is. My intuition says it is somewhere along the lines of finite state machines. But don't put too much stock in that.
