Re: Computable functions/reasls: followup.

On Thu, 4 Sep 2008 21:05:56 -0700 (PDT), Bill Taylor
<w.taylor@xxxxxxxxxxxxxxxxxxxxx> wrote:

OK then, the debate seems to have subsided, so maybe I could make
a summary, and perhaps add a few extra words.

The comprehensive and helpful (as usual) articles by Keith Ramsay
seem to cover most points, and suggest...

a) there IS a more-or-less standard meaning to "computable R->R
function";

b) it is not paid much attention to by orthodox mathies because...

c) it is not paid much attention to by constructive mathies because...

d) some extra remarks.
......

(a) A function f:R->R is computable if, for sufficiently closely
specified input there is arbitrarily closely specified output.

Which, curiously, is at this level of imprecision precisely
equivalent to what various "idiots" suggested the definition
"should" be - exactly what the standard definition "must"
be if there _was_ a standard definition, because, given that
a real is just something that can be approximated by rationals,
there's clearly nothing else the definition _could_ be.

Must be very sad, being unable to figure out things that are
clear to idiots.

This is virtually the standard defintion of continuity, and, with
appropriate attention to domains of definition, uniform continuity.

Keith observes that arbitrary closeness is not best defined in terms
of
decimal (or other) expansions, because of the usual irritating trouble
with ...9999... numbers. In fact, I see from the bits and pieces that
(modern constructivist) Douglas Bridges lets fall our way, a *real
number*
is now most usefully defined as: a strictly nested sequence of closed
intervals with rational endpoints, together with a guaranteed rate
of decrease to zero of their lengths; all of these being computable,
(in the case of computable real numbers). This strikes me as being a
very
good definition indeed, useful for either orthodox OR constructive
math,
and combining the best elements of both Cauchy sequences and Dedekind
cuts.
OC, it makes a computable real quite a complicated thing, but if you
view
it dispassionately, not much more so than an orthodox Cauchy sequence!

However, that is a purely technical matter, and not really our primary
concern here. The computable-function definition above still applies,
and the nested closed interval approach deals neatly and automatically
with problems such as what to do with f(x) = 1/x near the origin.

(b) ...it amounts to uniform continuity, as noted, and they already
know all about that, and see little merit in the computability
part.

(c) ...because they also (effectively) know about it from Brouwer's
insistence on "all functions are uniformly coninuous", (UC).

Incidentally, in Bridges' and others' work on reverse constructive
math,
where Bishop-style math is taken as core, and the various other
approaches
to math amount to Bishop plus some extra assumption, this fits in very
neatly, I'm informed. Essentially, orthodox math is BISH + LEM;
Russian-style constructivism is BISH + MP, (Markov's Principle...
that every non-continuing machine halts at some specific time);
and Brouwerian intuitionism is BISH + UC.

Alongside this, one occasionally hears the query, from orthodox
mathies,

"What did Brouwer actually DO, with his alleged proof of UC? We know
he was an excellent mathie, so he must have done SOMETHING
worthwhile,
so just what WAS it?"

My answer to this, which I've mentioned before in various threads, is
that he
proved that "every `uniformly computable' function is uniformly
continuous";
which is a moderately simple but by no means trivial matter,
(especially back when he DID it, before Turing!)

The current thread was intiated by me, partly in order to better pin
down
this idea of `uniformly computable', which I think has been largely
achieved.

(d) Some final remarks.

There is a lingering feeling, among those orthodox or uncommitted
mathies
who are sympathetic to the aims of constructivism, that it OUGHT to be
legal to consider such things as step functions, delta functions,
and even perhaps the rationals-indicator function.

e.g. the basic step function, 0 on the negatives and 1 on the
positives,
is frequently used by engineers and others for very practical
concerns.
Now (I think) the standard constructivist approach is to say it is
simply UNDEFINED on 0, so that it is a perfectly good function on
R+ U R-, and no-one need bother with f(0) at all. Engineers would
no doubt be happy with this, (indeed they often say f(0)=1/2 so as
to take the average of the two values it is "trying to be", in line
with Fourier transforms, but I suspect they are often uneasy with this
all the same). But pure mathematicians WANT to speak of step
functions
with a definite value at 0, and why not?

Once long ago, I read a paper that referred to "wild" numbers,
which were reals that you couldn't tell whether or not were rational.
For a constructivist, perhaps all reals are like this, but the
orthodox
are quite happy to say that pi, root-2 etc are irrational, and that we
may KNOW this absolutely. It's almost as if there were a distinction
between the algebraic root-2 and the real root-2; just as there IS
(intitially) between the rational 1/2 and the real 1/2, with Dedekind
cuts.

So, if we consider our domain as *tame reals*, that is, reals whose
ever-increasingly-accurate rational approximations are known, (as
above),
but also for which it is GIVEN whether or not they are rational,
then we can deal with discontinuous functions happily.

Both orthodox and (semi-)constructivist mathies would be satisfied
with
such a definition, though they would have different ideas on which
part
of it wasn't particularly useful. But on this domain, the nasty
functions
mentioned above, step, delta, rat-ind, are all genuine functions,
and *discontinuous-but-computable* functions can be defined! YAY.

OC, they couldn't perhaps just be given the name "computable", but
perhaps "computable with respect to a rationals-oracle", or more
simply,
"computable w-o the rationals". I think all but the most die-hard
constructivists would allow such a concept. And OC there is nothing
special about the rationals; they could be replaced by the integers,
the dyadic rationals (e.g. for Conway game theory), the algebraic
numbers, or whatever. And all these "oracularly-computable" functions
could maybe merely go under the blanket heading of "computable",
when the context was clear.

IMHO this would cure the lingering doubts expressed above, though it
would hardly be worth the trouble for evryday math. But it might be
a satisfying approach for some types of people.

AFAIK it has never been tackled; but I may be wrong about this.


Well that's my summary. No doubt there will be complaints.

------------------------------------------------------------------
Bill Taylor W.Taylor@xxxxxxxxxxxxxxxxxxxxx
------------------------------------------------------------------
* The intuitionist conflates existence with construction.
* The Platonist conflates existence with consistency.
------------------------------------------------------------------

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

Relevant Pages

  • Computable functions/reasls: followup.
    ... The computable-function definition above still applies, ... Russian-style constructivism is BISH + MP, ... which were reals that you couldn't tell whether or not were rational. ... special about the rationals; they could be replaced by the integers, ...
    (sci.logic)
  • Re: Cantor Confusion
    ... The "number" pi is definitely a merely fictitious element of continuum. ... naturals, integers, rationals, irrationals, or reals. ... intergers and naturals are genuine. ... genuine numbers to the reals is tempting but not justified. ...
    (sci.math)
  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... sequences or Dedekind cuts are useful in defining completeness. ... The constructions mentioned do not succeed in producing a complete ... view of what sort of reasoning about reals, functions of reals, and so ... The motivation for completing the rationals lies mainly in analysis, ...
    (sci.math)
  • Re: PL/I, COBOL, Advantages, Equivalence, et al
    ... The rationals and the integers have the same cardinality - they can be placed in 1-1 correspondence, but that does not make them isomorphic. ... the rationals are also a ring because after all a field is a ring with additional properties. ... There are several methods for constructing the reals from the rationals. ... In other words, all roots of polynomial equations with either real or complex coefficients are complex numbers and every such equation has a complete set of n roots, where n is the degree of the equation (the fundamental theorem of algebra). ...
    (comp.lang.pl1)
  • Re: Does the Calculus rest on Euclid?
    ... axioms I have assumed at the outset. ... Now you define the reals as ... A real number is a set S of rationals with the following properties: ... To say that you can order things implies a concept of a continuum. ...
    (sci.math)