User talk:Sligocki/Beating Graham's number

Σ(87) > G

You wrote ...

"I have proposed in the past that ... Σ(100) > G. In fact, I believe that the index could be much smaller, say Σ(12) > G. However, as far as I know, nobody has placed such an upper bound on G. ... My starting point for assaulting Graham's number, will be to create a Turing machine which computes Goodstein's function"

Are you close enough to actually constructing such a TM so that you can estimate roughly how many states it will have? I'm interested in how that compares to the following more-modest (successful!) approach to the problem.
I've written a 2-symbol 87-state TM (in the Busy Beaver class of machines) that halts with more than f_ω2(f_ω2(6)) 1s remaining on an initially-all-0 tape, where the functions f_ω2 are those in the fast-growing hierarchy. This machine is basically a direct coding of a simple algorithm to compute a slightly-accelerated fast-growing hierarchy g_α for 0 ≤ α < ω². More effort could possibly reduce this coding to significantly fewer states (≥ 70?). I haven't yet posted this machine anywhere (where would I?), but of course I'll make details available upon request. — r.e.s. (talk) 16:34, 6 September 2010 (UTC)[reply]

Hi r.e.s., very cool, it seems we are working on similar things all over. I'd love to see your construction of an 87-state machine. My suggestions of 100 and 12 were pure guesses based on intuition and how much was possible with 6 states. Looking into constructions I now think it is pretty unlikely that I could construct a 12-state machine that would outrun Graham using traditional construction techniques, but I'm still hopeful for computer-aided searches combined with human analysis. As for where to post such a machine, I believe there are several google groups that might be interested and Heiner, Pascal, Brady and other BB hunters would certainly also be interested. Send me an email if you'd like me to forward their addresses! Cheers, — sligocki (talk) 17:37, 6 September 2010 (UTC)[reply]

I think my TM can be revised to decrease the size much further, so I'll post back here after trying that. — r.e.s. (talk) 18:02, 7 September 2010 (UTC)[reply]

Sounds good, but if you don't mind, I would like to see some of your earlier constructions as well. I feel like the process of constructing a machine (or a proof) can be as interesting as (or even more interesting than) the final result. But I understand that you would like to take a moment to tidy up your work before presenting it. I wait with much anticipation :) — sligocki (talk) 03:00, 8 September 2010 (UTC)[reply]

I've created a blog posting that describes the TM and the algorithm it simulates. I call this machine GTM86 — it's the original 87-state TM after removing a superfluous state that I hadn't noticed earlier. (I haven't yet managed to coax that page into displaying everything in the proper format, e.g. some symbols are missing or wrongly-displayed, but I'll try to fix it soon.) Looking more closely at the revision I had in mind, the reduction in states appears to be more modest than I first thought; in any case, I'm putting that aside for now. — r.e.s. (talk) 15:45, 9 September 2010 (UTC)[reply]

PS: I've updated the blog posting (corrected typographical errors in a couple of the 5-tuples, and added listings of the transition table with state-labels in both alphanumerical and more-standard numerical form). I've tested GTM86 both as-is, which initialises the tape to <n><i><j> = <0><2><1>, and also when the initialisation is modified to various cases that lead to termination in a feasible timeframe. Example cases:

<n><0><0> ↓ (n+1) + 1

<n><0><1> ↓ (2n+6) + 1

<n><0><2> ↓ (2ⁿ⁺²(n+10)-6) + 1

<0><0><2> ↓ 34 + 1

<1><0><2> ↓ 82 + 1

<0><1><0> ↓ 410 + 1

Let me know if you need any further details. — r.e.s. (talk) 13:53, 11 September 2010 (UTC)[reply]

This is great. I love it! I'm wrapping my head around it right now, but so far it looks good. This is an ideal chance for me to flesh out a Turing machine proof language I've been thinking about. I'll post more when I have more to say (hopefully in the next few days). Thanks again, this is quite exciting! Cheers, — sligocki (talk) 04:38, 13 September 2010 (UTC)[reply]