Comment by tromp

Comment by tromp 8 hours ago

1 reply

> it is a function about Turing machines, which is how the BBF gets the special properties/results that it does.

The properties of the Busy Beaver function carry over to any other computational model you could base it on. E.g. the lambda calculus based BBλ[1] shares most of its properties.

> Which immediately reminds me of Chaitin's constant which also tries to encode/talk about the properties of Turing machines,

Chaitin's work on Algorithmic Information Theory (aka Kolmogorov Complexity) was actually focussed on custom Lisp languages of his own design rather than Turing Machines. One could be confused though by some of his articles on LISP program-size complexity like [2] where he calls his LISP interpreter a UTM (Universal Turing Machine).

[1] https://oeis.org/A33347

[2] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...

calf 6 hours ago

That carryover is because Turing machines and Lambda calculi are equivalent models of computation, and not because "busy beaver" is some special concept. It's a function whose definition is about computational phenomena, so there's a version of it for any Turing-equivalent concept (like lambda, or Post Correspondence, or the Recursive Functions)

So there should be no confusion there, the "big four models of computation" are all equivalent and we first encounter/learn this in undergrad TCS class.