Re: "Collatz 3n+1 conjecture is unprovable" paper

On 9 May 2006 09:57:45 -0700, "Craig Feinstein" <cafeinst@xxxxxxx>
wrote:

I'll address Ullrich's points one by one.

"Ok. The first hint that it must be wrong is that it's too easy,
and in fact the proof by contradiction that it's impossible to
prove CC seems to have very little to do with the assumption that
it _is_ possible to prove it!"

"It's not hard to find a specific error. First we should note
that the definition of "random" is woefully imprecise; we need
to specify the formal language we're going to use for the
specification."

The language is English. The proof also translates into Spanish or any
sophisticated human language you can think of. If the proof were in
Spanish, then random would be defined in terms of the Spanish language.
My point is that specifying the formal language is irrelevant to my
proof. What is important is the lemma that in any language there are
always "random" vectors. See Chaitin's work to understand this, which I
cited in my paper.

" And the statement of Theorem 2 is also a little
vague.

But never mind that. Essentially the same argument shows that
it's impossible to prove the Fundamental Theorem of Arithmetic:
Ever positive integer has a unique factorization as a product
of powers of primes:"

It's not the same argument and Ullrich never proved that it is the same
argument.

The basic problem is the same: You say that this proof would
specify something in L bits that cannot be specified in fewer
than L bits. But you overlook the fact that the specification
in question uses not just the proof, but the proof _plus_
a specification of the _value_ of the bad integer n. When
you add the bits needed to specify n the contradiction vanishes.

"Lemma: There is a constructive 1-1 correspondence between
positive integers and finite sequences of non-negative
integers not ending in 0.


Pf: Map the sequence (n_1, ... n_k) to the integer
p_1^n_1 p_2^n_2 ... p_k^n_k. QED."

This is correct; however, if one were to use the same standards of
rigor that Ullrich uses to judge my paper, I would say his proof is
wrong, because it doesn't define what p_1, p_2,....p_k are.

No, you'd call that an unimportant detail and move on to
the big problem, as I did.

(The proof of the lemma uses FTA, but never mind that,
we do know how to prove FTA.)


"Theorem" There is no proof of FTA.
"Proof": Suppose that there is a proof of FTA using L bits.
Let s be a sequence of non-negative integers such that
it's impossible to describe s using fewer than L+1 bits.
Choose n corresponding to s as in the lemma. Then the
proof gives a description of s in fewer than L+1 bits,
contradiction. QED.

There _must_ be an error there, because there _is_ a
proof of FTA. At least on error is this: A proof of
a statement of the form "for all n, ..." does not
necessarily include a description of every natural
number n. If s is as in the "proof" above, the
supposed proof of the non-provability of FTA does
not give a description of s. For that we need the
L-bit proof, _plus_ a description of n! The description
of n includes as many bits as are needed to give
a description of s."

Obviously, Ullrich is giving a false theorem and using it as a
straw-man attack on my proof.

"You're right, that was easy."

To this, I'll quote Ullrich's statement that he made at the beginning
of his post: "The first hint that it must be wrong is that it's too
easy."

I'll try to respond to any thoughtful responses within the week.

Craig


************************

David C. Ullrich
.

Relevant Pages

  • Re: Bounds checked arrays
    ... > more at each array access will not make any ... > this problem in the C language to do their dirty ... > When the state of this toggle is ON, the compiler ... > We have just to allow him/her to specify what to do ...
    (comp.lang.c)
  • Re: String filtering
    ... >>> language like Ada. ... You should specify what you wish to abstract away as unimportant ... If the language allows to do this in a consistent way, ... Purity requirement makes sense as an ...
    (comp.lang.ada)
  • Re: static class inheritance, generalized
    ... name search scope. ... As the language and framework are OO, the routines have to ... specify in which class they're in. ... header/namespace with solely routines and no classes, ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Test first as specification
    ... >>non-trivial programming language entirely through tests. ... > a mapping of tests to specs, ... Consider a language like Algol 68 which defines types real, ... many tests are needed to specify the above? ...
    (comp.object)
  • Re: Proving Lemmas about uncountable subsets of R
    ... specify it more clearly. ... is a countable union of countable sets, ... follows /\ S must be countable, which is a contradiction. ... When I started to enjoy Math, I used to deal with integers and loved ...
    (sci.math)