On Jun 17, 3:16 am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote: > Virgil <Vir...@home.esc> writes: > > In article > > <995d761a-f70f-4bca-b961-8db8e1663...@d37g2000yqm.googlegroups.com>, > > WM <mueck...@rz.fh-augsburg.de> wrote: > >> On 15 Jun., 22:24, Virgil <Vir...@home.esc> wrote: > >> > Note that it is possible to have an uncomputable number whose > >> > decimal expansion has infinitely many known places, so long as it > >> > has at least one unknown place. > >> That is mathematically wrong. > > It may not match every definition of 'uncomputable', but otherwise it is > > right. > It doesn't really match any definition of 'computable'.
It's a rare day indeed when Aatu and WM actually agree!
They both agree that Virgil's definition of "uncomputable" is wrong. Let's see what's at stake here.
We all agree that Chaitin's omega is uncomputable, so let us define another real number as follows.
Suppose we regard Chaitin's omega in let the number x equal 1 if there exists a natural number N such that for all natural numbers n>N, we have that a majority of the first n digits of omega are 1's, and let x equal 0 othewise. So now we ask, is x a computable real?
By Virgil's definition, it isn't, since there's no Turing machine that can compute whether x=0 or x=1.
But by Aatu and WM, it is computable, since after all, x must be either 0 (which is computable), or 1 (which is also computable), so in either case, x is computable.
We recall that in classical logic, we know that from P->R and Q->R, we conclude (PvQ)->R. So we have:
P <-> "x=0" Q <-> "x=1" R <-> "x is computable"
So P->R is "if x=0, then x is computable" (which is true, since 0 is computable).
So Q->R is "if x=1, then x is computable" (which is true, since 1 is computable).
So we conclude (PvQ)->R, which is "if x=0 or x=1, then x is computable." And we know that x must be 0 or 1. Thus, by Modus Ponens, x is computable. QED
So which definition of computable, Virgil's or Aatu-WM's, should we use? I'm not sure which of the two definitions is more prevalent.
