Re:A number that can't be calculated
by dvt on Tuesday October 25, 2022 @04:32PM
(#33335755)
> it is always possible to compute BB(k) for a specific and arbitrary k.
It is not. There are a few proofs, most notably the fact that you'd have to solve the halting problem to find BB(k) for an arbitrary k. But the more interesting proof is when looking at the growth of the number of states required for larger BB(k)'s. You end up with a pretty cool contradiction[1] by constructing a very special Turing machine.
It is not. There are a few proofs, most notably the fact that you'd have to solve the halting problem to find BB(k) for an arbitrary k. But the more interesting proof is when looking at the growth of the number of states required for larger BB(k)'s. You end up with a pretty cool contradiction[1] by constructing a very special Turing machine.
[1] http://www.coopersnotes.net/docs/langmach/CHAP10%20Busy%20Be... (pg. 403)