[FOM] CH and mathematics

joeshipman@aol.com joeshipman at aol.com
Sun Jan 20 16:43:24 EST 2008


How about "we'll never know whether busy-beaver(googol), expressed as a 
base=10 integer, has an even or odd number of digits?"

(By this I mean the number of 1's output by the 
longest-running-but-still-halting-on-blank-input TM in a 2-letter 
alphabet and 10^100 states has an even or odd number of digits.)

That's probably unknowable even if 10^100 is replaced by a feasible 
number like 10^5.

-- JS

-----Original Message-----
From: Bill Taylor <W.Taylor at math.canterbury.ac.nz>
To: fom at cs.nyu.edu
Sent: Sat, 19 Jan 2008 11:05 pm
Subject: Re: [FOM] CH and mathematics

JS wrote:

->I don't see why our inability to know something should cast any doubt
->on its definiteness. That's epistemological arrogance.


->We'll very likely never know whether the googolplexth decimal digit 
->pi is even or odd; does that cast doubt on its definiteness?

Peeeep!   Foul!   10 yards please.

That example is very far from similar.  In the digits of pi example,
we may never know the answer, but we already know a simple algorithm
that will find the answer, given sufficient "time".  For most mathies
that is virtually equivalent to knowing the answer.

In the CH example, though, we (at present), haven't the faintest idea
of how to go about finding the answer (if there is one).

This is a far more serious epistemological concern, and is a kind of
evidence that the question *has* no real answer.  (Absence of evidence
being evidence of absence, whatever the law courts may say.)
Of course evidence is a long way from proof or a convincing argument.

So Joe, could you come up with another, perhaps more fittingly analagous
example, I wonder?   I can't think of one off-hand.

Bill Taylor

FOM mailing list
FOM at cs.nyu.edu

More new features than ever.  Check out the new AOL Mail ! - 

More information about the FOM mailing list