A New Kind of Science: The NKS Forum > NKS Way of Thinking > What does Wolfram's PCE imply for the philosophy of mathematics?
Author
David Brown

Registered: May 2009
Posts: 180

What does Wolfram's PCE imply for the philosophy of mathematics?

According to “quick_takes” by Wolfram:
(1) “Systems with exceptionally simple rules can be universal computers.”
(2) “The Principle of Computational Equivalence provides a broad synthesis.”
(3) “The difficulty of doing mathematics reflects computational irreducibility.”
(4) “Existing mathematics covers only a tiny fraction of existing possibilities.”
http://wolframscience.com/reference/quick_takes.html
Does Wolfram’s NKS suggest that mathematical proof is a tiny archipelago of logical islands in a vast sea of logically overwhelming computational irreducibility?
Consider the following:
Meta-thesis. According to Wolfram’s Principle of Computational Equivalence (PCE), almost all mathematical statements that are both true and profoundly interesting are unprovable within Zermelo-Fraenkel set theory.
Does Wolfram’s PCE have implications for the Clay Prize in mathematics?
http://www.claymath.org/prizeproblems
http://en.wikipedia.org/wiki/Millenium_Prize_Problems
Consider 4 hypotheses in formal proof theory.
Hypothesis 1. Ordering by multiplicity and modulus, for the first M critical zeroes of the Riemann zeta function, any formal proof within Peano Arithmentic (PA) that all of these M zeroes lie on the critical line has length at least log (log M).
Hypothesis 2. Ordering by multiplicity and modulus, for the first M zeroes of almost every random entire function f of the form f(z) = ∑ a(n) (z**n) / n! , where each a(n) is an element of the set {0,1}, within Peano Arithmetic (PA) it takes a formal proof of length at least log (log M) to constructively estimate, in the form (rational number + i rational number), the moduli of all the M zeroes to within 1/M. Assume that {a(n)} n = 1,2, … is a sequence of independent and identically distributed random variables with mean ½ and variance 1. Assume that the rational numbers in question all have numerator and denominator in the range from – (M times MAX) to (M times MAX), where MAX is the smallest positive integer greater than or equal to the maximum modulus of the first M zeroes.
Hypothesis 3. Assume consis(PA). Within PA, for any positive integer M, there is some false alleged proof FP that P = NP with length(FP) = M, and it takes a formal refutation of length at least log(log M) to ensure that the false alleged proof FP really is false.
Hypothesis 4. Assume consis(PA). Suppose that we form a new theory (NT) by adding to PA some axioms A(1), …, A(m) such that consis (PA + A(1) + … + A(m)), where m is a fixed positive integer. Then in this new theory NT, there is some hypothesis H such that H is true but unprovable in NT, and within theory NT, for every positive integer M, there is some false alleged proof FP of H with length(FP) = M and it takes a formal refutation of length at least log(log M) to ensure that the false alleged proof FP really is false.
Why might Hypothesis 3 be true? I might be able to concoct a false alleged proof (FAP) that the Traveling Salesman Problem has a solution in polynomial time, for time t —> (t**M). If you try to show that my FAP is wrong by running a length-M counterexample in time exceeding M**M, then you would find that, within my FAP, I have disguised table look-up that works for all counterexamples of length less than M+1. My point is that, in general, it takes a considerable amount of work to refute a cleverly faked example of a false alleged proof. In the same way, a clever fraud can conceal a battery within an alleged perpetual machine — the more clever and elaborate the fraud, the more time and effort it might take to expose the fraud.

Report this post to a moderator | IP: Logged

05-16-2010 02:09 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us