2 ms·
> In other words, the Busy Beaver Game is noncomputable because of the Halting Problem, and the Halting Problem is noncomputable because it lacks an upper bound
by eru 2y ago
> In other words, the Busy Beaver Game is noncomputable because of the Halting Problem, and the Halting Problem is noncomputable because it lacks an upper bound in time.
Not completely. The halting problem is computable for some more limited forms of computation, even if they have no upper bound in time.
In an alternative formulation: for some Turing machines we can prove in finite time that they run forever. Thus your 'lack of an upper bound in time' is not enough.
- Borealid 2y agoI believe there exist some subset of turing machines that can be proven to run forever. But providing an oracle for the halting problem - of which an upper bound is one form - makes the Busy Beaver Game computable. To get back to the original topic... a finite brain in finite time can only produce finite output. Both the brain and its output are, like all fully bounded sets, computable.