On Sun, Mar 3, 2019 at 9:26 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
> > >> The 8000th Busy Beaver Number can be named but not calculated even >> theoretically, > > > *> The busy beaver function is not computable, but on each individual n, > it is computable theoretically, * > No it is not, not if n= 7918, to compute that the program would have to solve the Halting Problem. The first 4 Busy beaver numbers have been computed and Scott Aaronson proved that the 7918th Busy Beaver Number is not computable, most people think n=5 is not computable either but that has not been proved. The 7918th Busy Beaver Number <https://www.scottaaronson.com/busybeaver.pdf> *> The 8000h BB number is well defined, * > Yes. > *> so it is a (finite) number, * > Yes, *> and so you there exist a finite program computing it* > No. The 8000th Busy Beaver Number is the largest number of FINITE operations a 8000 state Turing Machine will make before it halts. Some programs we can observe halting and with others it's easy to prove will never halt, that's why we know the first 4 Busy Beaver Numbers, but Turing Proved you can't do that in general and Aaronson proved you can't do that for the 7918th; and you probably can't even do it for the 5th. It is entirely possible that the 5th Busy Beaver number is 47,176,870 because a 5 state Turing Machine has been found that halts after 47,176,870 operations, the problem is there are still 5 different 5 state turing machines that are well past 47,176,870 and they have not halted. If none of those 5 machines ever halts then 47,176,870 really and truly is the 5th Busy Beaver Number, but if that is the case we will never know that is the case because we'll never know that none of those 5 machines ever halts. John K Clark > > -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
