Talk: Yudkowsky's Number

The number I described in the linked sysopmind.com page is just Graham's Number, and indeed, minor add-1s to it are minor; the linked article doesn't say otherwise.

If anything ought to be called Yudkowsky's Number, it's my contribution to the "my number is biggest" XKCD thread here:  http://forums.xkcd.com/viewtopic.php?f=14&t=7469&sid=3b6d016c7172b82d00b7789cf293b232&start=1240#p3254229

-- Eliezer Yudkowsky / 50.240.196.110 23:44, October 14, 2015 (UTC)

Won't this modification work better?

Here's a question that I ("r.e.s.") asked in the above-linked XKCD thread, but apparently no-one responded to it: Wouldn't a significantly larger number result from simplifying your procedure by omitting the program search? Thus ...

Starting with P = 10:

• Search through all Turing machines with at most P states.
• Search through all proofs in T of length at most 2^^P that the some program halts.
• Run all programs such that a halting proof exists, until they halt.
• Add up all the running times of all those programs.
• Set P to this sum.

Repeat 10 times.

This assumes that if X is a proof that some program Y halts, then X is identifiable as such without having specified Y in advance; but isn't that a reasonable assumption? In other words, this vastly larger alternative number is what I called ι(11), where

ι(0) = 10

ι(k+1) = sum of the running times of all TMs (irrespective of the number of states) that halt T-provably using at most 2^^ι(k) symbols.

As I noted there ... If, in the above definition of ι(), we were to use (ZFC, 1000, 2^ι(k), maximum) instead of the respective (T, 10, 2^^ι(k), sum), then ι(1) would be the smallest of what Harvey Friedman calls transcendental integers ("Enormous Integers in Real Life", p. 11). res0001(talk) 14:22, February 5, 2016 (UTC)

Your program does not work. We can have an infinite family of TMs such that the first state is to create a one and halt, and the other states can be anything. All of these are provable to halt in ZFC (in a sufficient amount of symbols), and they each run 1 step, so we have your program return \(\infty\). Maybe called Googology Noob (talk) 15:33, February 5, 2016 (UTC)

Actually, I believe your program does work, if I understand your description properly. The problem with Googology Noob's argument is precisely the parenthetical statement "in a sufficient amount of symbols". If we bound the number of symbols in a proof, then there are certainly finitely many proofs of the form "machine M halts", so we can collect them, run and sum the running times, in a finite time.

Of course, I'm fairly sure this will give a larger number, but I don't think it would be very significant improvement, for the following reason: Because the proof has to have length at most 2^^P, in particular the statement "machine M halts" has to have length at most 2^^P (and probably a lot less). This puts limitation on possible number of states of M, and I think this machine has to have less than 2^^P states. That being said, I believe that ι(11) would be smaller than the result of applying Yudkowsky's procedure 12, instead of 10, times.

A minor issue, which I believe wasn't addressed before and which I'm not going to ask you to resolve here, is the way to express and count number of symbols of a proof in T, and a way of encoding the statement "machine M halts" in the language of set theory. All three of these would have to be agreed-upon before one can claim the procedure is well-defined. LittlePeng9 (talk) 16:17, February 5, 2016 (UTC)

I thought that too originally, but why doesn't my argument work? If we prove that after 1 step the machine terminates, we do not have to regard the other states, right? Maybe called Googology Noob (talk) 17:06, February 5, 2016 (UTC)

We do have to take the other states into account at the very least when the proof culminates with the statement analoguous to "and hence M halts", because at this point, when we write "M halts", we have to include entire description of M. It's a general fact in formal deduction systems (which is proven exactly the same way) that a proof of a statement is at least as long as the statement. LittlePeng9 (talk) 19:14, February 5, 2016 (UTC)

Thanks for your replies. Evidently I should have made it clear in the search description that by "some program" I did indeed mean "some particular program", i.e., the search targets only those proofs of statements of form "machine M halts" (as per LittlePeng9's comments), thus avoiding the problems mentioned by Googology Noob. I intended the same meaning when I referred to halting "T-provably".

Granted, there is some implicit bound "a lot less than 2^^P" on the number of states of any particular TM proved to halt by such a proof using at most 2^^P symbols, but it's difficult to estimate how much less than 2^^P is the attained maximum number of such states. It seems to me that we might expect the growth rate of the resulting sequence to be extremely sensitive to this number of states, which may well vastly exceed even 2^P, compared to only P in Yudkowsky's procedure. (We're in effect looking at a "down-sized" computable analog of the Busy Beaver function.) Res0001 (talk) 20:43, February 7, 2016 (UTC)

After two iterations, we have a number probably way beyond anything humanity has ever recursively defined. It is quite obviously greater than f_w(100) (it is way bigger than that, but we don't need to go so far), so it will be a huge tetration tower. If your function allows one more to the tetration tower, it's not doing anything. Whether you have \(\ f_{\psi(\psi_{X(M^{M})}(I(1,0)))}(10000000)\) states or 2^^\(\ f_{\psi(\psi_{X(M^{M})}(I(1,0)))}(10000000)\) absolutely disappears after one more iteration of the function. Maybe called Googology Noob (talk) 13:48, February 8, 2016 (UTC)

How do you do the fancy X in the ordinal function that collapses Mahlo cardinals to I(a,b,c...)? Maybe called Googology Noob (talk) 13:52, February 8, 2016 (UTC)

The fancy X is actually the Greek letter chi, and you get it in LaTeX using \chi like this: \(\chi\).

By the way, if you see some formula written in MathJax (i.e. using \( \) as opposed to <math> </math>), then you can view its source code by right-clicking it and choosing suitable option. LittlePeng9 (talk) 14:21, February 8, 2016 (UTC)

"ZF + axiom of choice"? So ZFC? 2602:306:80F2:40C0:5DFD:12D2:FEF2:2B72 20:05, October 24, 2017 (UTC)