As you must know, there are real numbers that are not computable by computers: After all, there are at most a countably infinite set of computers, and a countably infinite set of computer programs, whereas there is an uncountably infinite number of real numbers. Therefore, not all real numbers are computable. (I guess this is equivalent to saying, there are more real numbers than there are formal systems F or Godelian sentences G(F), right?). In other words, there exist (uncountably many) real numbers that no computer program can "describe", or no formal system can "reason about".

The novel twist to this game is this: suppose I have two computers, connected with some communications channel. Suppose the two computers run at clock speeds that are independent of each other (they are not synchronized). Lets call the ratio of the clock speeds R, which is a real number. Suppose R is in fact one of these uncomputable numbers. Then these two computers can compute things that are traditionally non-computable. The most trivial of these are R itself (both computers generate the strings of alternating ones and zeros 010101010101... one of the two computers interleaves these. The interleave is R itself (actually, its 4/5th's of R, but lets not quibble)).

Thus, the bald claim is that through this simple mechanism, even if Penrose is right about the non-computability of thought, we have described a system that can obtain non-computable results, and therefore squeaks by any of Penrose's objections.

Lets look at this system a little more carefully:

- We have introduced "physics" into the realm of computability. The
two clocks running the computers are some sort of physical process. One must
"believe" that it is possible to build actual physical devices that
run at such uncomputable ratios. If one does not believe this, one must show
that in nature, somehow only computable reals occur. I admit this is a toss-up
that physicists argue, although the preponderance of current belief is that
*all* real numbers occur in natural processes, and not just some of them.

- How does one "know" that R is uncomputable? Naively, it would
seem that one doesn't, and one can't. Certainly, there is no formal system
that can classify real numbers into computable and uncomputable ones.
(right??). Even if such a classification were possible, we would have to wait
until the end of time to "really know" what the clock frequency
ratio was, right? Or is there some physical process that can identify
non-computable numbers in a finite amount of time?

- Can one do anything "useful" with this setup, beside use it in an
argument about artificial intelligence? I dun-no. There must be something ...

I like (2) because it seems to point out that there are natural processes that lead to unknowable states that are outside of Godelian formalism. That, as it were, the uncomputable whole is far more than the sum of the two computable parts.

Linas Vepstas linas@fc.net

8 December 1996

later in December, 1996

Linas Vepstas linas@fc.net

8 December 1996

Go back to Linas' Home Page