On Tue, Mar 5, 2019 at 8:03 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
> *The expression "Non computable numbers” appears only in intuitionist > logic,* If so then just by reading the title of Turing's famous 1936 paper where he first described a device that we now call a Turing Machine you'd have to conclude that Turing was a intuitionist, it was called "On Computable Numbers, with an Application to the Entscheidungsproblem". John K Clark > On 4 Mar 2019, at 23:31, John Clark <johnkcl...@gmail.com> wrote: > > On Mon, Mar 4, 2019 at 11:04 AM Bruno Marchal <marc...@ulb.ac.be> wrote: > > >> I don't follow you. If the 8000th BB number is unknowable then it is >>> certainly uncomputable >> >> >> *> That is not true. All natural number n are computable. The program is >> “output n”.* >> > > I think you're being silly. You're saying if you already know that the > answer to a problem is n then you can write a program that will "compute" > the answer with just a "print n" command. But that's not computing that's > just printing. > > > I am even more silly. I claim that I need only to know that there is an > answer to say that BB(n), unlike [n]BB(n), is computable, trivially and non > interestingly, perhaps, but that follows from the classical definition of > Turing, Church, Markov, Hebrand-Gödel, etc. > > > > > > Incidentally very recently Stefan O’Rear has reduced Aaronson' s 7918 > number so now we know that BB(1919) is not computable. > > > Nice!!! > > Of course, we know only that BB(1919) = k, for k any enough big number is > undeciadbale in ZF. > > Perhaps tomorrow, we will know that BB(1919) = k is decidable in ZFC + > kappa. > > > > > So we know that: > • BB(1)=1 > • BB(2)=6 > • BB(3)=21 > • BB(4)=107 > > and that's all we know for sure, but we do know some lower bounds: > > • BB(5) ≥ 47,176,870 > • BB(6) ≥ 7.4 *10^36534 > • BB(7) >10^((10^10)^(10^10)^7) > > > *BB(n) is not computable means that there is no algorithm, which given >> n, will give BB(n).* >> > > Yes, so what are we arguing about? > > > > That we should not confuse the many possible notions of computable > functions from R to R, for which there is no standard definition on which > everyone would agree, and no corresponding Church-Turing notion, with the > notion of computable function from N to N (or any set of finitely > describable objects, always trivially computable). > > Mechanism use the Church-Turing notion. A digital brain has no real > numbers as input; nor real numbers as output. > > In the classical theory of computability, a real number is seen as an > infinite objects, and is modelled by total computable functions; or by > recursive operator, not by the usual partial recursive functions (phi_i). > > > > > > >> > *what Aaronson has shown, is that above 7918, we loss any hope to find >> it by using the theory ZF. But may be someone will find it by using ZF + >> kappa, which is much more powerful that ZF,* >> > > It's easy to find a system of axioms more powerful than ZF, the problem is > it may be so powerful it can even prove things that aren't true. > > > That is always the risk. It cannot been avoided. Provability is a relative > notion. No provers can prove its own consistency. > > > > Would you really trust a system that claimed to be able to solve the > Halting Problem? I certainly wouldn't! And if you can't solve the Halting > Problem then there is absolutely no way to calculate BB(7918) or BB(1919) > and I wouldn't be surprised if even BB(5) is out of reach. > > > > You are right on this. The BB function computability is equivalent with > computability with the halting oracle. > With an oracle for BB, you can solve the halting problem and vice versa. > > You can’t solve the totality/partiality problem though (named TOT). Even > with the BB oracle (or the halting oracle) you need to do an infinite task > to solve the TOT problem. There is a transfinite set of set of numbers > which are more and more unsolvable in that sense. > > > > > > > There are only 2 possibilities, a program will halt after a finite >>> number of steps or it won’t. >> >> >> > Yes. But the program which computes BB(n) always stop. >> > > if it stops then it is successful but if n is 1919 then it never stops so > BB(1919) is never computed. > > > AAronson’s paper is not on the computability of BB, but of the > undecidability of equation of the type BB(n) = k, in ZF. It is not about > us, but about the particular Löbian machine ZF. > > > > > >>I would maintain that you haven't solved a problem if you can't give >>> the right answer more often than random guessing would. >> >> >> *> You are restricting computability to a string notion of intutionistic >> computability. * >> > > What grade would you give a student who couldn't answer your questions > better than you'd expect from random guessing? > > > Random guessing has nothing to so with what we are talking about. > > My point is just that the notion of computability used is the classical > one, and in that case, despite [n]BBn is not a computable function, each > BB(n) is trivially, and non interestingly computable. That is why we use > natural numbers: to have a set of trivially computable primitive elements. > To compute any natural numbers, you need only to apply the successor > function s a finite number of time on 0. > > The expression "Non computable numbers” appears only in intuitionist > logic, or it means non computable real numbers. But real numbers are > (total) functions in disguise, and the notion of computability on real > numbers, or on more complex objects, admits many non equivalent > definitions. > > 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. > 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. > > > -- > 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. > -- 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.
