Dave Selke, an electrical engineer with a computer background, has made a number of interesting comments concerning this page, spurring me to redo the argument in another form. The new essay is entitled "On Hilbert's sixth problem" and may be found at
http://paulpages.blogspot.com/2011/11/first-published-tuesday-june-26-2007-on.html
Draft 3 (Includes discussion of Wolfram cellular automata)
Comments and suggestions welcome
Note: The word "or" is usually used in the following discussion in the inclusive sense.
Many subscribe to the view that the cosmos is essentially a big machine which can be analyzed and understood in terms of other machines.
A well-known machine is the general Turing machine, which is a logic system that can be modified to obtain any discrete-input computation. Richard Feynman, the brilliant physicist, is said to have been fascinated by the question of whether the cosmos is a computer -- originally saying no but later insisting the opposite. As a quantum physicist, Feynmen would have realized that the question was difficult. If the cosmos is a computer, it certainly must be a quantum computer. But what does that certainty mean? Feynmen, one assumes, would also have concluded that the cosmos cannot be modeled as a classical computer, or Turing machine [see footnote below].
Let's entertain the idea that the cosmos can be represented as a Turing machine or Turing computation. This notion is equivalent to the idea that neo-classical science (including relativity theory) can explain the cosmos. That is, we could conceive of every "neo-classical action" in the cosmos to date -- using absolute cosmic time, if such exists -- as being represented by a huge logic circuit, which in turn can be reduced to some instance (computation) of a Turing algorithm. God wouldn't be playing dice.
A logic circuit always follows if-then rules, which we interpret as causation. But, as we know, at the quantum level, if-then rules only work (with respect to the observer) within constraints, so we might very well argue that QM rules out the cosmos being a "classical" computer.
On the other hand, some would respond by arguing that quantum fuzziness is so miniscule on a macroscopic (human) scale, that the cosmos can be quite well represented as a classical machine. That is, the fuzziness cancels out on average. They might also note that quantum fluctuations in electrons do not have any significant effect on the accuracy of computers -- though this may not be true as computer parts head toward the nanometer scale. (My personal position is that there are numerous examples of the scaling up or amplification of quantum effects. "Schrodinger's cat" is the archetypal example.)
Of course, another issue is that the cosmos should itself have a wave function that is a superposition of all possible states -- until observed by someone (who?). (I will not proceed any further on the measurement problem of quantum physics, despite its many fascinating aspects.)
Before going any further on the subject at hand, we note that a Turing machine is finite (although the set of such machines is denumerably infinite). So if one takes the position that the cosmos -- or specifically, the cosmic initial conditions (or "singularity") -- are effectively infinite, then no Turing algorithm can model the cosmos.
So let us consider a mechanical computer-robot, A, whose program is a general Turing machine. A is given a program that instructs the robotic part of A to select a specific Turing machine, and to select the finite set of initial values (perhaps the "constants of nature"), that models the cosmos.
What algorithm is used to instruct A to choose a specific cosmos-outcome algorithm and computation? This is a typical chicken-or-the-egg self-referencing question and as such is related to Turing's halting problem, Godel's incompleteness theorem and Russell's paradox.
If there is an algorithm B to select an algorithm A, what algorithm selected B? -- leading us to an infinite regression.
Well, suppose that A has the specific cosmic algorithm, with a set of discrete initial input numbers, a priori? That algorithm, call it Tc, and its instance (the finite set of initial input numbers and the computation, which we regard as still running), imply the general Turing algorithm Tg. We know this from the fact that, by assumption, a formalistic description of Alan Turing and his mathematical logic result were implied by Tc. On the other hand, we know that every computable result is programable by modifying Tg. All computable results can be cast in the form of "if-then" logic circuits, as is evident from Turing's result.
So we have
Tc <--> Tg
Though this result isn't clearly paradoxical, it is a bit disquieting in that we have no way of explaining why Turing's result didn't "cause" the universe. That is, why didn't it happen that Tg implied Turing who (which) in turn implied the Big Bang? That is, wouldn't it be just as probable that the universe kicked off as Alan Turing's result, with the Big Bang to follow? (This is not a philisophical question so much as a question of logic.)
Be that as it may, the point is that we have not succeeded in fully modeling the universe as a Turing machine.
The issue in a nutshell: how did the cosmos instruct itself to unfold? Since the universe contains everything, it must contain the instructions for its unfoldment. Hence, we have the Tc instructing its program to be formed.
Another way to say this: If the universe can be modeled as a Turing computation, can it also be modeled as a program? If it can be modeled as a program, can it then be modeled as a robot forming a program and then carrying it out?
In fact, by Godel's incompleteness theorem, we know that the issue of Tc "choosing" itself to run implies that the Tc is a model (mathematically formal theory) that is inconsistent or incomplete. This assertion follows from the fact that the Tc requires a set of axioms in order to exist (and hence "run"). That is, there must be a set of instructions that orders the layout of the logic circuit. However, by Godel's result, the Turing machine is unable to determine a truth value for some statements relating to the axioms without extending the theory ("rewiring the logic circuit") to include a new axiom.
This holds even if Tc = Tg (though such an equality implies a continuity between the program and the computation which perforce bars an accurate model using any Turing machines).
So then, any model of the cosmos as a Boolean logic circuit is inconsistent or incomplete. In other words, a Turing machine cannot fully describe the cosmos.
If by "Theory of Everything" is meant a formal logico-mathematical system built from a finite set of axioms [though, in fact, Zermelo-Frankel set theory includes an infinite subset of axioms], then that TOE is either incomplete or inconsistent. Previously, one might have argued that no one has formally established that a TOE is necessarily rich enough for Godel's incompleteness theorem to be known to apply. Or, as is common, the self-referencing issue is brushed aside as a minor technicality.
Of course, the Church thesis essentially tells us that any logico-mathematical system can be represented as a Turing machine or set of machines and that any logico-mathematical value that can be expressed from such a system can be expressed as a Turing machine output. (Again, Godel puts limits on what a Turing machine can do.)
So, if we accept the Church thesis -- as most logicians do -- then our result says that there is always "something" about the cosmos that Boolean logic -- and hence the standard "scientific method" -- cannot explain.
Even if we try representing "parallel" universes as a denumerable family of computations of one or more Turing algorithms, with the computational instance varying by input values, we face the issue of what would be used to model the master programer.
Similarly, one might imagine a larger "container" universe in which a full model of "our" universe is embedded. Then it might seem that "our" universe could be modeled in principle, even if not modeled by a machine or computation modeled in "our" universe. Of course, then we apply our argument to the container universe, reminding us of the necessity of an infinity of extensions of every sufficiently rich theory in order to incorporate the next stage of axioms and also reminding us that in order to avoid the paradox inherent in the set of all universes, we would have to resort to a Zermelo-Frankel-type axiomatic ban on such a set.
Now we arrive at another point: If the universe is modeled as a quantum computation, would not such a framework possibly resolve our difficulty?
If we use a quantum computer and computation to model the universe, we will not be able to use a formal logical system to answer all questions about it, including what we loosely call the "frame" question -- unless we come up with new methods and standards of mathematical proof that go beyond traditional Boolean analysis.
Let us examine the hope expressed in Stephen Wolfram's New Kind of Science that the cosmos can be summarized in some basic rule of the type found in his cellular automata graphs.
We have no reason to dispute Wolfram's claim that his cellular automata rules can be tweaked to mimic any Turing machine. (And it is of considerable interest that he finds specific CA/TM that can be used for a universal machine.)
So if the cosmos can be modeled as a Turing machine then it can be modeled as a cellular automaton. However, a CA always has a first row, where the algorithm starts. So the algorithm's design -- the Turing machine -- must be axiomatic. In that case, the TM has not modeled the design of the TM nor the specific initial conditions, which are both parts of a universe (with that word used in the sense of totality of material existence).
We could of course think of a CA in which the first row is attached to the last row and a cylinder formed. There would be no specific start row. Still, we would need a CA whereby the rule applied with aribitrary row n as a start yields the same total output as the rule applied at arbitrary row m. This might resolve the time problem, but it is yet to be demonstrated that such a CA -- with an extraordinarily complex output -- exists. (Forgive the qualitative term extraordinarily complex. I hope to address this matter elsewhere soon.)
However, even with time out of the way, we still have the problem of the specific rule to be used. What mechanism selects that? Obviously it cannot be something from within the universe. (Shades of Russell's paradox.)
Footnote
Informally, one can think of a general Turing machine as a set of logic gates that can compose any Boolean network. That is, we have a set of gates such as "not", "and," "or," "exclusive or," "copy," and so forth. If-then is set up as "not-P or Q," where P and Q themselves are networks constructed from such gates. A specific Turing machine will then yield the same computation as a specific logic circuit composed of the sequence of gates.
By this, we can number any computable output by its gates. Assuming we have less than 10 gates (which is more than necessary), we can assign a base-10 digit to each gate. In that case, the code number of the circuit is simply the digit string representing the sequence of gates.
Note that circuit A and circuit B may yield the same computation. Still, there is a countable infinity of such programs, though, if we use any real for an input value, we would have an uncountable infinity of outputs. But this cannot be, because an algorithm for producing a real number in a finite number of steps can only produce a rational approximation of an irrational. Hence, there is only a countable number of outputs.
*************************
Thanks to Josh Mitteldorf, a mathematician and physicist, for his incisive and helpful comments. Based upon a previous draft, Dr. Mitteldorf said he believes I have shown that, if the universe is finite, it cannot be modeled by a subset of itself but he expressed wariness over the merit of this point.
No comments:
Post a Comment