Re: Complexity Theory for Simpletons (Collatz)



In article <1144432922.787807.65410@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Craig Feinstein <cafeinst@xxxxxxx> wrote:
"How about 2^(2^1000)? Do you think one needs on the order of 2^1000
symbols to write down a rigorous proof for it? "

No, of course you don't need 2^1000 bits, but you still need to
describe what the algorithm does at each iteration in a rigorous proof.

So, you agree that to prove that T^(2^1000)(2^(2^1000)) = 1, the 2^1000
quantities T(2^(2^1000)), T^(2)(2^(2^1000)), ..., don't need to appear
explicitly in the text file of a rigorous proof, and in particular the
text file need not be 2^1000 symbols long?

Would you further agree that one can prove that T^(2^n)(2^(2^n)) = 1
for *all* n rigorously in a finite text file? That such a proof would
refer to infinitely many finite sequences of T's using a finite amount
of space?

In that case, you should agree there's no a priori reason that you
couldn't prove the Collatz conjecture for all integers, because one
can prove facts about infinitely many finite sequences of integers in
a finite amount of space without having to include those finite sequences
explicitly.

In order to make arguments about the complexity of the proof of the kind
you want to make, one needs to show why the *proof itself* has to have
arbitrarily high complexity, and it's not enough to say that the proof
refers to, or talks about, or describes, things of arbitrarily high
complexity. Chaitin proves things about Omega, for example, and his
proofs are finite in length and yet describe Omega rigorously.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.