Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

  1. 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}$?
  2. 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}$.
  3. 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:

  1. 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?
  2. 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.
  3. 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.)

share|improve this question
3  
You need to be careful when you talk about complexity of a single problem. Perhaps it is not running time of a program but something like the length of a shortest formal proof (e.g. from ZFC). So if you write a program that just prints the answer, you must accompany it with a proof that the answer is correct, and the length of the proof counts in. –  Sergei Ivanov Apr 8 '10 at 18:40
add comment

5 Answers

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?]

share|improve this answer
2  
It is also 1 in base 2 and in base b with $Graham/2<b\leq Graham$. Yes, I was mostly interested in the case with 10 ;), but I think the answer would be interesting for any b, $3<b<\log(graham)$ not a power of 3. (I just choose $\log(graham)$ because it is a huge number much smaller than grahams numbers. You could probably have chosen a larger number) –  Sune Jakobsen Apr 8 '10 at 20:01
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
3  
I go to OSU, so if I see him around I will run it by him. –  Steven Gubkin Apr 8 '10 at 18:33
    
@Steven: I just sent him an email. It seems that OSUs math homepage is down. Do you know if the math.ohio-state.edu mails work? –  Sune Jakobsen Apr 11 '10 at 17:07
add comment

In base nine it's 3.

share|improve this answer
    
Citation, or details? –  David Roberts Jun 26 '13 at 22:09
add comment

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.

share|improve this answer
    
Less than $\log_3 G,$ surely? –  Charles May 8 '12 at 14:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.