Non-Computability of Thought

I just skimmed through a rebuttal of Penrose's argument, and I thought that I should bring to attention a novel and simple way of reaching non-computable states with computer networks. This technique provides a simple way of adding "physical" processes to computational systems without requiring (screwball) micro-tubule quantum gravity crap in explanations of consciousness.

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:

  1. 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.

  2. 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?

  3. 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 (1) because it gets rid of this quantum gravity crap. Of course, it may be something like quantum whiz-bang that is needed to "prove" that non-computable real numbers do, in fact, occur in nature. But that is a different story.

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 [email protected]
8 December 1996

Rebuttal

An obvious problem with the above musings is that, for a computing machine that must perform it's work in a finite amount of time, the introduction of "non-computable" noise is indistinguishable from the introduction of pseudo-random noise. The addition of non-computable elements is useful in considering only computations that take an infinite amount of time. The theoretical question is then: "If I know a fact about a computational problem that takes an infinite amount of time to complete, can I use this knowledge in a productive way to alter some finite-time algorithm?"


later in December, 1996
Linas Vepstas [email protected]
8 December 1996
Go back to Linas' Home Page