nostr:npub1dtf79g6grzc48jqlfrzc7389rx08kn7gm03hsy9qqrww8jgtwaqq64hgu0 I can't find the post, but I recall you mentioned Tetration function a little while back, and I THINK you claimed it's not computable.
Turns out it is not PRIMITIVE recursive, but it is recursive (equivalently, computable). Interesting distinction connected to non-halting Turing machines, if you wanna read on that.
Just thought I'd share in case you didn't know
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.
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)
Oh, the linked thing, which appears to be Goodstein Sequence. Will have a look soon
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
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).
Have a few things I'll need to learn up on. Thanks
