Subnostr

Tetration is definitely computable. It’s TREE(3) that is not. Also I’m not sure about this, it’s not recursive, but not as fast as TREE(3) or Busy Beaver.

https://www.numberphile.com/videos/the-goodstein-sequence

YODL 6mo ago

Ah ok, must have misremembered and wanted to correct.

Not sure about what? That it's recursive? I believe recursive functions = Turing computable (one of many instances of Church's Thesis type of thing), but correct me if I'm wrong. What was mostly new to me is idea of primitive recursive vs (fully) recursive, which has to do with allowing unbounded search instead of bounded only (I'm phrasing this sloppily but should convey meaning), and the overall connection to halting (still not totally crystal clear to me, but seems like a deep thing)

Reply to this note

Please Login to reply.

Discussion

YODL 6mo ago

Oh, the linked thing, which appears to be Goodstein Sequence. Will have a look soon

YODL 6mo ago

Google search says GSeq is computable, which makes sense since there's a recipe to follow for computing it. However, the calc of how long process takes to terminate is not

From Google AI search result:

Yes, the Goodstein sequence is computable, but the function that maps a starting number to the number of steps it takes for the sequence to reach zero is not provably total in Peano Arithmetic (PA). While a Turing machine can enumerate the sequence and determine when it reaches zero, the proof of termination relies on principles beyond PA

Chris Liss 6mo ago

The number of steps to reach zero of GS(12) > Graham’s Number, and if you were to do GS(GS(12)), you’re off the scale. Basically it’s not simply recursive like GN, but grows at a faster level (Epsilon0 on the fast growing hierarchy). But yeah I guess it’s computable because it follows basic rules unlike TREE(3).

YODL 6mo ago

Have a few things I'll need to learn up on. Thanks