The problem of finding the first digit in Graham's number - MathOverflow

The problem of finding the first digit in Graham's number

2010-04-08T17:53:14Z

Motivation

In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could it be possible to show that (under some assumptions about the speed of our computers) we can never determine the first digit?

In logic you have independence results like "We cannot decide if AC is true in ZF". But we cannot hope for this kind of result in this case, since we can easily program a computer to give us the answer. The problem is, that we don't have enough time to wait for the answer!

In complexity theory you prove things like "no program can solve all problems in this infinite set of problems, fast". But in this case you only have one problem, and it is easy to write a program, that gives you the answer. Just write a program that prints "1" another that prints "2" ... and a program that prints "9". Now you have a program that gives you the answer! The problem is, that you don't know which of the 9 programs that are correct.

Questions

Edit: I have now stated the questions differently. Before I asked about computer programs instead proofs.

Could it be possible to show that any proof of what the first digit in Grahams numbers is, would have length at least $10^{100}$?
Do there exist similar results? That is, do we know a decidable statement P and a proof that any proof or disproof of P must have length $10^{100}$.
Or can we prove, that any proof that a proof or disproof of P must have length at least $n$, must itself have length at least $n$?

I think the answer to 3) is no, at least if all proofs are in the same system. Such a proof would prove that it should have length all least n for any n.

(Old Questions:

Could it be possible to show that it would take a computer at least say $10^{100}$ steps to determine the first digit in Grahams number?
Do there exist similar results? That is, do we know a decidable statement P and a proof that P cannot be decided in less that say $10^{100}$ steps.
Or can we prove that we need at least $n$ steps to show that a decidable statement cannot be decided in less than $n$ steps?)

(I'm not sure I tagged correctly. Fell free to retag, or suggest better tags.)

Answer by Gerhard Paseman for The problem of finding the first digit in Graham's number

2010-04-08T18:29:39Z

Harvey Friedman has dealt with many large numbers, as well as issues regarding their computability. (Cf. his Enormous Numbers in Real Life.) I suggest emailing him your question. (You can also check other Math Overflow posts on Graham's number.)

Gerhard "Ask Me About System Design" Paseman, 2010.04.08

Answer by Jacques Carette for The problem of finding the first digit in Graham's number

2010-04-08T19:47:23Z

Easy: 1. But you probably meant base 10, not base 3, right ? That's a touch harder...

[Hopefully I don't run afoul of some MO rule by injecting a little humour in an answer?]

Answer by gowers for The problem of finding the first digit in Graham's number

2010-04-09T09:05:57Z

It seems to me that the question is really about the shortest proof that the first digit of Graham's number is what it is, rather than the shortest program that calculates it. Indeed, if you have an efficient program plus a proof that the program is correct (which rules out your nine programs, one of which is correct), then you have a short proof, and if you have a short proof then you have an efficient program that you know is correct (it just prints out the answer).

There are certainly results that are known to be true in PA but only to have very long proofs in PA. For example, the proof that every Goodstein sequence eventually hits zero needs the axiom of infinity. But any particular instance can in principle be shown to hit zero -- it's just that the proof would take an inordinately long time. So the answer to your question 2 is yes if you restrict to PA. I imagine that similar results are known for other axiom systems. As Gerhard says, Harvey Friedman knows a lot about this sort of thing.

Answer by Alexander for The problem of finding the first digit in Graham's number

2012-05-08T03:42:32Z

In base nine it's 3.

Answer by Feldmann Denis for The problem of finding the first digit in Graham's number

2012-05-08T05:21:43Z

Similarly, it is 1 if the base is of the shape $3^n$, with $n$ a power of 3 (less than $\ln G$) ; other cases are easy for small powers of 3. On the other hand, Graham's number is much too large for the question to be really interesting ; the determination of the first digit in base 10 of $A(9,9)$ (where $A$ is the Ackermann function) should already be inaccessible.