# Re: Complexity Theory for Simpletons (Collatz)

*From*: tchow@xxxxxxxxxxxxx*Date*: 07 Apr 2006 21:53:39 GMT

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

.

**Follow-Ups**:**Re: Complexity Theory for Simpletons (Collatz)***From:*Craig Feinstein

**References**:**Re: Complexity Theory for Simpletons (Collatz)***From:*Craig Feinstein

**Re: Complexity Theory for Simpletons (Collatz)***From:*tchow

**Re: Complexity Theory for Simpletons (Collatz)***From:*Craig Feinstein

- Prev by Date:
**Re: Complexity Theory for Simpletons (Collatz)** - Next by Date:
**Re: N -ROOM LIGHTS PROBLEM** - Previous by thread:
**Re: Complexity Theory for Simpletons (Collatz)** - Next by thread:
**Re: Complexity Theory for Simpletons (Collatz)** - Index(es):