> On 3 Mar 2019, at 18:28, John Clark <johnkcl...@gmail.com> wrote: > > > > On Sun, Mar 3, 2019 at 9:26 AM Bruno Marchal <marc...@ulb.ac.be > <mailto: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.
Why? You confuse computable with “provably computable”. BB is not computable, but BB+<any specific input> is computable. BB(7918) is just a number, say k, and the program “print k” will do. Similarly, the function F defined by F (x) = 0 if the twin prime conjecture is true, and equal 1 if not. Is a computable function; because it is the same function as y=0, or the same function as y = 1. Both are computable. F is computable, despite its definition is a not a code for computing it. > 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. I doubt Scaott Aaronson makes such a big mistake. B(7918), is computable. It is BB which is not computable. It means that there is no algorithmic to compute BB on each numbers. But on each number, BB, and all total functions, are computable. > > The 7918th Busy Beaver Number <https://www.scottaaronson.com/busybeaver.pdf> > Let me see. Indeed, what they show is that B(7918) = k might be unprovable in ZFC. That is not equivalent with B(7918) is not computable. It is a natural number. All constant function are computable. > > 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. In ZF, we cannot prove that. But provable is not computable. In lambda notation [n]BB(n) is not computable, but all BB(n), for each individual n is trivially computable. Aaronson takes a problem of provability and independence, not of computability. Of course BB(n) is not feasible for large n. > > 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. No problem with this. But the never know is made precise in term of “provable in ZF, or not”, and that is what Aaronson wrote about. BB(n), as function of n, is not computable, but all BB(n) is trivially computable for each n, as it is only a number. We just don’t know the algorithm, but we know that algorithm exists, as BB(n) is just a number, and the algorithm will just be “print that numbers”. Bruno > > 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 > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- 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.
