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:
Metathesis. According to Wolfram’s Principle of Computational Equivalence (PCE), almost all mathematical statements that are both true and profoundly interesting are unprovable within ZermeloFraenkel 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 lengthM counterexample in time exceeding M**M, then you would find that, within my FAP, I have disguised table lookup 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
