Newsgroups: sci.math
Subject: re: Puzzles
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: 13 Aug 92 13:08:16 +1200
Distribution: world
Organization: Department of Mathematics, University of Canterbury

Firstly, thanks to John Baez for his excellent and intriguing post (as always).

I personally thought it was fascinating to see how EVERY FINITE STRING of
digits can appear at the beginning of a number of the form 2^n. I fully
approve of John Baez's polite but dismissive rebuttal of the suggestion
that it was *merely* a trivial consequence of a density-of-reals result,
(though this observation was also interesting).

Puzzle # 1, "SMOOTH SHARP CORNERS?", was a lot of fun, and I have already
posted my solution to that.

Puzzle # 2, "THE COMPLEXITY BARRIER", was fascinating too, and interesting to
see in this form. [ I dimly recall seeing this result before, but can't think
how the proof goes now. I haven't checked my references before posting; of
course I should've, but why be different from 90% of all posters  :-) ]

Anyway, I thought I'd send in a few idle musings on this subject, though
they'll mainly come under the heading of SILLY REMARKS. Still, they might amuse.
---

John presents the Almost-Paradox

[A-P] (1) it is provable that "for almost all n, P(n)".
      (2) for any particular N, it is not provable that "P(N)".

In this case, P(n) is the statement that n cannot be produced by a program
of length <= E.  E is unspecified, but a value can be calculated (in principle).

Now my first reaction to this meta-theorem is that it's clearly not true
unless the "any particular N" in (2) is a bit more closely specified.
For instance, it follows from (1) that we can define a unique number M, by
M = smallest positive integer requiring a program of length > E.

Now this (unambiguously defined) M  satisfies P, (by definition).
Shades of "the smallest uninteresting number" !
However most people would rightly consider this to be a bit of a cheat.
So it looks like the N in (2) should be restricted by e.g. the requirement that
it be presented in numeral form.  Of course to actually *make* this presentation
is going to require a huge amount of paper (or whatever), so the meta-theorem
is already starting to look a little less startling; unless.....

[Question 1] ....can any less restrictive condition than "N in numeral form"
~~~~~~~~~~~  be used in (2), that will preserve the truth of [A-P] ?

This relates to the whole grisly matter of when is an integer "properly
specified", which continues to bedevil metamathematics (for instance, the
number F which = 9 if FLT is false, and 8 if true). Though many people would
probably say F is not "really" defined properly (yet), at least we know it
a lot more accurately than the "better"-defined M above !

Anyway, I would also like to see an answer to

[Question 2] What is a good value for E ?
~~~~~~~~~~~ (I don't recall seeing an answer posted; I can't even guess at it.)

[Question 3] Are there any "more natural" properties P, to which [A-P] applies ?
~~~~~~~~~~~  i.e. more traditionally mathematical than the logico-computing
                  property P given above.


As a final bit of nonsensical musing on [A-P] as given; I got into the
following grand wild goose chase.                     I was trying to
imagine finding a number G, such that we could be reasonably sure (short of
a proof), that *all* numbers greater than G would need programs of length > E.

Clearly it would have to be at least as large as 10^n, where n also had
this property (or nearly had it). This means in turn it would have to be
larger than 10^10^...^10, with 10^n exponentiations. This in turn would
mean that it would have to be........ (getting well into Ackerman's function)

Indeed, there's no end to the quest, seemingly, short of irreparable brain
damage. It would be nice to see a reasonable answer to Question 2, though.
It presumably would have some bearing on this wild goose chase.

----
Thanks again John, for a fun post.

---------------------------------------------------------------------
      Bill Taylor              wft@math.canterbury.ac.nz
---------------------------------------------------------------------
Well, I believe in solipsism, but that's just one man's opinion.
---------------------------------------------------------------------

Xref: sparky sci.math:10409 sci.psychology:3518