# Re: Are there real numbers that cannot be defined?

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