> 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 
> <mailto: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.


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. 


> 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.

Reply via email to