In the last post I talked about software models for a full-adder logic circuit. I broke them into two broad categories: models of an abstraction, and models of a physical instance. Because the post was long, I was able to mention the code implementations only in passing (but there are links).
I want to talk a little more about those two categories, especially the latter, and in particular an implementation that bridges between the categories. It’s here that ideas about simulating the brain or mind become important. Most approaches involve some kind of simulation.
One type of simulation involves the states of a system.
Imagine the watershed for a river. Every drop of water that falls in that area, if it doesn’t evaporate or sink into the ground, eventually makes its way, through creeks, streams, and rivers, to the lake or ocean that is the shed’s final destination. The visual image is somewhat like the veins in a leaf. Or the branches of the leaf’s tree.
In all cases, there is a natural flow through channels sculpted over time by physical forces. Water always flows downhill, and it erodes what it flows past, so gravity, time, and the resistance of rock and dirt, sculpt the watershed.
The question is whether the water “computes.”
No, sorry, I don’t mean the Bletchey Bombe machine that cracked the Enigma cipher. I mean his theoretical machine; the one I’ve been referring to repeatedly the past few weeks. (It wasn’t mentioned at the time, but it’s the secret star of the Halt! (or not) post.)
The Turing Machine (TM) is one of our fundamental definitions of calculation. The Church-Turing thesis says that all algorithms have a TM that implements them. On this view, any two actual programs implementing the same algorithm do the same thing.
Essentially, a Turing Machine is an algorithm!
Is that you, HAL?
Last time, in Calculated Math, I described how information — data — can have special characteristics that allow it to be interpreted as code, as instructions in some special language known to some “engine” that executes — runs — the code.
In some cases the code language has characteristics that make it Turing Complete (TC). One cornerstone of computer science is the Church-Turing thesis, which says that all TC languages are equivalent. What one can do, so can all the others.
That is where we pick up this time…
The previous post, Halt! (or not), described the Turing Halting Problem, a fundamental limit on what computers can do, on what can be calculated by a program. Kurt Gödel showed that a very similar limit exists for any (sufficiently powerful) mathematical system.
This raises some obvious questions: What is calculation, exactly? What do we mean when we talk about a program or algorithm? (And how does all of this connect with the world of mathematics?)
Today we’re going to start exploring that.