Re: functions that halt

From: Jón Fairbairn (jon.fairbairn_at_cl.cam.ac.uk)
Date: 04/17/04 

Date: 17 Apr 2004 15:30:46 +0100

Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de> writes:

> I think the problem is that you can't distinguish a
> computable real from an uncomputable one.

I'm not sure what you mean here. If you can describe a
number and prove that it's not computable, that counts as
distinguishing it in my book. If it's one of the uncountable
number of reals that we can't even describe, you'd probably
best appeal to Wittgenstein.

> You can write down some specifications (for reals) that
> are uncomputable, but I think you can't decide whether the
> real that fulfills that spec just might happen to be a
> fraction of square roots or some such (precisely because
> you can't compute it and so check). At least all the
> examples I have seen were of that kind.

No: all the proofs of uncomputability I can think of prove
that a number really isn't computable. For example theš real
B defined as 0.bbbbb... where the n'th bit is 1 iff the
programme with Gödel number n halts is not computable. If it
were, then one could use another programme that took
programmes as argument, Gödel encoded them and indexed B as
a solution to the halting problem. Note that the proof says
nothing to specify the reason behind computing B; the
contradiction would arise if /any/ programme could compute B
in any fashion. So B isn't a fraction of the square root of
anything computable.

> So if someone does not accept the proof that the
> cardinality of reals is larger than the cardinality of
> computable numbers (which can be listed by listing all
> programs), what can you use to convince him?

It depends on why they don't accept it. If they are arguing
that numbers such as B above have no meaning in nature, or
that the universe we inhabit is constructed entirely on a
countable basis there is no way to refute that. I don't
think we know a single physical constant to more than a few
billion digits˛. Besides, every axiomatisation of the reals
has a countable model; in a sense we cannot really escape
from our discrete means of expressing mathematics.

Also, from a practical point of view, if the someone is too
obtuse there may be nothing that will convince him.

[1] FSVO "the". We have to pick a particular notion of
computation and a particular Gödel encoding -- so in fact
there's a (countable) infinity of Bs...

[2] I'm allowing for a certain amount of future scientific
effort here. 

-- 
Jón Fairbairn                                 Jon.Fairbairn@cl.cam.ac.uk

Relevant Pages

  • Re: Error in Turings paper On computable numbers, with an application to th..
    ... Bishop doesn't describe the sequence numerically; ... but I assume he means that there's a Turing machine ... that when given an index of a Turing machine computing x, ... If the reals are all given as binary expansions, ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... sequence of reals. ... a rational approximation to fto within 1/n as follows. ... gives us a way of computing modulus of uniform continuity ...
    (sci.logic)
  • Re: etc
    ... to integer constraints) process that would allow the construction, ... between the two subsets of the reals - you can't specify a computational ... An algorithm for generating the successive digits of e.g. pi, ... Coin tossing is computing a number. ...
    (sci.math)
  • Re: functions that halt
    ... all the proofs of uncomputability I can think of prove ... > programme with Gödel number n halts is not computable. ... > nothing to specify the reason behind computing B; ... computed computed a number that fulfills the definition of B. ...
    (comp.theory)
  • Re: Cantor Confusion
    ... there is no list of all reals. ... given by a Turing machine. ... Computing ... any sequence of decimal numbers is *by the very ...
    (sci.math)