37
$\begingroup$

I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. I was wondering if that's the case because of technological limitations, or whether there is another reason we cannot find a floor of this number.

$\endgroup$
  • 2
    $\begingroup$ "I was wondering if that's the case because of technological limitations, or whether there is another reason we cannot find a floor of this number." - The first one I believe; it certainly overflows on most computing environments. $\endgroup$ – J. M. is a poor mathematician Dec 5 '10 at 2:23
  • 20
    $\begingroup$ I am not sure what they mean by not computable. Different numbers have different representations. If you pick the base exp(exp(exp(79))) then the floor is 10. $\endgroup$ – John Smith Dec 5 '10 at 2:28
  • 3
    $\begingroup$ That's not my question Ross, it was asked by Carl Mummert. $\endgroup$ – InterestedGuest Dec 5 '10 at 5:11
  • 8
    $\begingroup$ @John: I don't understand your comment. The floor of a number is defined as the greatest integer not greater than the number, and it is independent of the base. The floor of $\pi$ is always 3; it doesn't become 1 just because you choose base $\pi$. $\endgroup$ – ShreevatsaR Jun 15 '11 at 13:17
  • 3
    $\begingroup$ @John: Further, computable is usually defined with respect to a fixed base (say, base $2$). If you want to say "the number is $10$ in base $\lfloor e^{e^{e^{79}}} \rfloor$", that is fine as long as you can properly specify the latter number — the base. Now you're back to your original problem. $\endgroup$ – ShreevatsaR Jun 15 '11 at 13:23
45
$\begingroup$

In the formal meaning of "computable" the floor of that number is indeed computable. This is to say that a patient immortal human with access to unlimited paper and pencil could, in principle, work out the answer. (Here I assume, for technical reasons, that the number in question is not an integer - I assume someone who knows enough number theory will be able to cite a result that implies this.)

The article linked makes the weaker claim that the value has not yet been calculated, which seems likely to me. The issue they are concerned about is that humans are not immortal and that our supply of paper is very limited. If the number of decimal digits in the value is too large, it would be impossible to actually represent it in any physical way within our universe.

In general, I think it is more accurate to say that ultrafinitists don't accept that the set of all natural numbers is a coherent entity - not that they think it is finite. However, as the article you linked alludes, it is very difficult to find a coherent but non-arbitrary way to say what natural numbers are without accepting that there are an infinite number of them.

Addendum Here is why I am worried whether $e^{e^{e^{79}}}$ is an integer. It's certainly correct that no matter what, the floor of that number is an integer and is therefore computable. That part of my argument is fine.

On the other hand, if $e^{e^{e^{79}}}$ is not an integer, then I can tell you a specific algorithm to use to compute it. Namely, compute better and better upper and lower bounds until they fall strictly between two consecutive integers (which they must, since their limit is not an integer) and then pick the smaller of those two integers.

If $e^{e^{e^{79}}}$ is an integer, then that algorithm won't work, because it will never stop. But if we knew that $e^{e^{e^{79}}}$ was an integer then we could take better and better upper and lower approximations until they straddle a single integer, and then pick that.

So the reason that I am interested whether the number is an integer is that, beyond merely knowing that the floor is an integer, I'd like to know which algorithm could be used to compute it.

In any case, I don't think that the point of the example was to pick a number that is not known to be integer or known to not be an integer. The point of the example should be to pick a number which is simply too large to represent physically. I was hoping that someone would have a quick answer that confirms $e^{e^{e^{79}}}$ is not an integer, so I could edit my response with that info. But the non-integer property seems more difficult than I thought.

$\endgroup$
  • 3
    $\begingroup$ Why do you need that assumption? If the number in question were an integer, its floor (i.e. itself) would still be computable. So it remains compatible with the argument you're making. $\endgroup$ – Rahul Dec 5 '10 at 5:35
  • 1
    $\begingroup$ Thanks, your addendum makes a lot of sense. The crux of the matter seems to be that a discontinuous function of a computable number is not necessarily computable (I think?). So you can in principle compute $\lfloor e^{e^{e^{79}}} \rfloor$ because it is an integer and therefore trivially computable, but you can't necessarily compute it by computing $e^{e^{e^{79}}}$ and taking the floor of the result. $\endgroup$ – Rahul Dec 5 '10 at 19:54
  • 1
    $\begingroup$ Yes, that's the issue. The floor function would be computable if you already had a decimal expansion for the real number, but if all you have are arbitrarily good rational approximations of a real then you also can't compute the decimal expansion in any uniform way. It's a matter of what representation you use for computing real numbers. $\endgroup$ – Carl Mummert Dec 5 '10 at 22:54
  • 1
    $\begingroup$ nitpicking: "ultrafinitists don't accept that the set of all natural numbers is a coherent entity". The finitists do not accept this also. The ultrafinitistic positions are more conservative than this. $\endgroup$ – Kaveh Dec 12 '10 at 23:11
  • 1
    $\begingroup$ @Carl: You don't know the floor of "0.999..." unless you either find a digit that's not 9, or you have a proof that your source of decimal approximations will give a 9 in every digit. Decimals make a bad model for computable reals; e.g. how do you output even the first digit of "0.000... + 0.999..."? $\endgroup$ – Hurkyl Feb 8 '13 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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