[Wolfram's interpretation of Godel's theorem?] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Wolfram's interpretation of Godel's theorem?
(Click here to view the original thread with full colors/images)
Posted by: Michael Kreutzjans
Excuse my for my ignorance, but I could not really understand Wolfram's abstraction of godels's theorem on every mathematical system having a certain amount of unprovable statements.
Posted by: Jason Cawley
Wolfram regards the key feature of Godel's proof as the universality of arithmetic - that is what he thinks lets it work. As he put in on page 784 "The basis for Godel's theorem is the result that the standard axioms for basic integer arithmetic support universality".
Meaning, any computable question can be formulated as a statement in arithmetic, with the truth value of the arithmetical statement tracking the original, encoded question. On page 786, Wolfram gives an example of a single (exponential, for purists) diophantine equation that already supports universality, since it encodes the evolution of cellular automaton 110 from any initial condition, as a question about the solutions to the equation, for different values of its variables.
Essentially what Wolfram believes is going on, is there are some systems that have enough internal complexity or "resources" to support any constructible calculation. They are "past the threshold of universality". They can encode any determinate algorithm - perhaps in a very complicated manner, but without going outside their own rules and fixed set up. Universal computers work on this principle. You do not need to change the fixed rules of the system to emulate a new computation, you just change the encoded "instructions" or "program".
The ability to encode any algorithm and evolve according to its behavior puts definite limits on statements that can be made about the types of behavor the "programmable" system can exhibit. You can't exclude anything that any finite (or more accurately, "computable") algorithm might do. And one thing a computable algorithm can do, is fail to halt, never arriving at an answer - Turing's "halting problem". Asking for the answers to every problem in a class that is programmable, is asking for every possible programmable behavior. There are going to be ones were you cannot tell what the answer is in any finite time.
From this perspective it should not be surprising that there are many outstanding mathematical problems, even problems with very simple statements, that are arbitrarily hard to solve, or that there are classes of problems can be proved to be formally undecidedable. Whether an arbitrary Diophantine equation has integer solutions is an example. You can check solutions with a systematic procedure. Some you find, yes there is a solution. Some you can prove, no there isn't any possible solution. But others, the systematic procedure will simply fail to halt - you find no "yes" answer in a billion billion integers but can't exclude the possibility there is another out there in the next billion billion billion integers that does satisfy the equation, or whatever.
An axiom system is a formal system with rules of deduction. The expectation that the behavior of that system will always be predictable, is based on the old intuition simple rules will lead only to simple behaviors. But this old intuition is not even close to correct. Very simple formal systems can do arbitrarily complicated things, things complicated enough that any other formally specified procedure can be encoded in its terms. And asking what any formally specified procedure can do, the answer is, anything you can clearly conceive and constructively state.
Arithmetic being programmable, you can reduce any hard question to an arithmetical one - does this Turing machine halt when started from this tape? - for instance. And we know that in general you can't answer all such questions. The fact that you've reduce the problem to a matter of adding and subtracting does not mean you have solved it. Purely formal questions (in simple formal systems) can be as hard as you like, so "reducing" a question to simple formal terms does not mean solving it.
To see the connection of all of this to practical computing, consider what we mean when we speak of a computer's memory as consisting of 1s and 0s. The internal state at any one time is some big number. It evolves according to some instructions. It arrives at some other big number. Anything the computer might do, is a sequence of number to number according to some order of operations. Each of the primitive, basic operations can be fixed, and you can get from anywhere to anywhere by just changing which of them you do, how many times, in what order. We think of this as some definite instruction portion of the initial number and some memory portion - the von Neumann architecture for carving up what parts of the number do. But at root, it is all a slightly complexified piece of arithmetic.
Anything you can program a computer to do, arithmetic can do, because there are straightforward "translations" ("encodings") from one to the other. Anything hard to say about what an arbitrary computer program might eventually do (e.g. ever halt?), has a corresponding math problem that is just as hard to solve.
You might also look at the note on page 1158. I hope this helps.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings