From: hrubin@odds.stat.purdue.edu (Herman Rubin)
Subject: Re: Real Analysis limited to Computable Functions
Date: 12 Aug 2000 20:32:08 -0500
Newsgroups: sci.math
Summary: [missing]

In article <20000812153335.01142.00000118@ng-cq1.aol.com>,
Richard Batchelor <dbatchelo1@aol.com> wrote:
>What happens if one restricts oneself to COMPUTABLE functions, and investigates
>their properties? (Of course, every number used is computable, every sequence
>considered is computable and so on.) What results of classical real analysis
>are still true?

>  As far as I can tell, they ALL are. I think that in fact the computable
>numbers satisfy the axioms for real numbers, and so the collection of all
>computable numbers is a model of the reals. Is this correct?

> Is there any theorem of classical real analysis that is not true for the
>computables?

I believe that there is a constructive function of a real
number, which is constructively continuous, such that the
location of the maximum is not constructive.  The value of
the maximum is necessarily constructive.
-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558
==============================================================================

From: kramsay@aol.commangled (Keith Ramsay)
Subject: Re: Real Analysis limited to Computable Functions
Date: 14 Aug 2000 01:33:02 GMT
Newsgroups: sci.math

In article <20000812153335.01142.00000118@ng-cq1.aol.com>,
dbatchelo1@aol.com (Richard Batchelor) writes:
|  As far as I can tell, they ALL are. I think that in fact the computable
|numbers satisfy the axioms for real numbers, and so the collection of all
|computable numbers is a model of the reals. Is this correct?

Someone recently asked the same question, but I suppose it's worth
answering again.

It's consistent with constructive mathematics that every real number
is recursive (computable), and every function on the reals is
recursive. Certain nonconstructive theorems of analysis fail to hold
for the recursive reals-- a lot of them actually. They all have
constructive counterparts, although they sometimes look uglier in that
form.

As someone pointed out, the least upper bound property fails for the
recursive reals. There exists a recursive increasing sequence of
recursive reals which is bounded above, but without a recursive least
upper bound. The least upper bound lemma is woven into classical
analysis in a fairly pervasive way.

Every recursive function on the recursive reals is pointwise
continuous, a theorem discovered independently by Ceitin and
Kreisel-Lacome-Shoenfeld. Standard examples of functions defined
everywhere but discontinuous at a point fail to be recursive: there is
no algorithm for determining whether a recursive real number is
positive, negative, or zero, for example.

The following construction is the starting point for a number of the
others. You can read about it, if you are interested enough, in
Beeson's book, _The Foundations of Constructive Mathematics_. For any
epsilon>0, there exists a recursive sequence (a1,b1), (a2,b2),
(a3,b3),... of open intervals which cover the recursive reals, but
where |b1-a1|+|b2-a2|+...+|b_N-a_N|<epsilon for each N. One can use
that to construct a recursive function on the recursive reals of [0,1]
which is positive at each point, but which isn't bounded below by any
epsilon>0. The reciprocal of that function is a recursive, pointwise
continuous function on the recursive reals which is unbounded. If we
take the arctan of that, we get a function with a least upper bound,
i.e. pi/2, but which doesn't attain the least upper bound at any
recursive points.

That unusual cover of the recursive reals shows also that measure
theory in its usual formulation is fairly far from true for recursive
analysis.

Another source of counterexamples in recursive mathematics is the
construction of a binary tree with infinitely many nodes, but without
any recursive infinite branch. A hypothetical being with the ability
to look ahead and see whether either the left or the right branch is
a dead end (eventually!) can climb the tree on an infinite branch, but
we can arrange so that there is no computable way to do it.

There is a constructive theorem that the reals are uncountable. On
the other hand, it's also constructive that there is a subset of the
integers with a recursive map from it onto the recursive reals. If
it were true that every real was recursive, this would contradict the
nonconstructive theorem that every infinite subset of a countable set
is countable.

The subject strikes me as somewhat awkward because of the mixture of
different assumptions which ordinarily gets drawn into it. We consider
a set S, with some of the following assumptions made:

  1. S is the reals
  2. S is the recursive reals.
  3. The reals are all recursive.
  4. The law of excluded middle holds.

4 is the standard nonconstructive axiom. You are taught about the
consequences of assuming 1 and 4 in school. A constructive
mathematician will happily tell you the consequences which follow
from  just 1 by itself-- the constructive theorems of analysis. The
ones I know of tend not to care all that much about recursive
analysis, however the theorems they know of (and the ones which they
know aren't constructive) also shed some light on the consequences of
assuming 1-3 (each of which follows from the other two), which sort
of helps to answer your question.

But then assuming you really want to know what is classically true
of the recursive reals, you want to know the consequences of 2 and 4
together. While it's a parallel story, it's also a contradictory one,
since 3 and 4 are incompatible. It seems to me that having the two
similar but contradictory stories in mind at the same time tends to
make things confusing.

Keith Ramsay
==============================================================================

From: kramsay@aol.commangled (Keith Ramsay)
Subject: Re: Real Analysis limited to Computable Functions
Date: 17 Aug 2000 02:27:18 GMT
Newsgroups: sci.math

In article <20000814112938.20856.00000165@ng-fq1.aol.com>,
dbatchelo1@aol.com (Richard Batchelor) writes:
|I had convinced myself that the opposite was true; that the LUB was
|necessarily
|computable, because it could be computed by evaluating the sequence and so
|getting closer and closer to the LUB. Could you give me more details?

The number 0<r<1 whose n-th bit is 1 if the n-th Turing machine halts
starting on a blank tape is the limit of a computable, increasing,
bounded above sequence: let r_n have 1 bits for k such that the k-th
Turing machine halts within n steps starting from a blank tape, and
k<=n. We can compute each r_n by running the first n Turing machines
for n steps each. But in order to find an N such that the r_n for
n>N are within 2^{-M}, we have to be sure that the Turing machines
from  among the first M which haven't halted by step N don't halt ever.

It's an example of what Bishop called in his textbook "fickle
convergence". For each epsilon>0, there exists N such that for any
indexes i_1<i_2<...<i_N, there is some j for which r_{i_j} is within
epsilon of r_{i_{j+1}}. Roughly speaking, we have a bound on how many
times the sequence can move by epsilon.

This holds for any increasing sequence bounded above. We know a bound
on how many times it can move upward by a certain step size. It cannot
do it infinitely many times. But we lack a way of finding the supposed
last time that such a step occurs in this sequence. It may look like
the sequence is approaching a certain value, but it holds in reserve
the option to surprise you by jumping over that point, as it were. And
since the halting problem isn't solvable by computation, this r isn't
computable.

|>For any
|>epsilon>0, there exists a recursive sequence (a1,b1), (a2,b2),
|>(a3,b3),... of open intervals which cover the recursive reals, but
|>where |b1-a1|+|b2-a2|+...+|b_N-a_N|<epsilon for each N.
|
| Could you outline how this is done? I had convinced myself that any
|recursive cover of the recursive reals in (0,1) would have measure >=1.

Take an infinite sequence epsilon_1, epsilon_2,... of positive numbers
which sums to epsilon. Run a batch of Turing machines in parallel,
which are candidates for machines computing real numbers. Run the n-th
Turing machine until it responds to a request for an approximation to
within epsilon_n/2 of the real it computes. If machine n should happen
to stop with a rational number q on its output, insert (q-epsilon_n/2,
q+epsilon_n/2) into the enumeration of rational intervals.

There is no way, of course, to arrange to get the intervals in order
by the index n. Some of the machines run forever, and we just keep
running them in parallel with the others, occasionally adding another
Turing machine to the batch. It may be that machine n gives us an
answer despite not being a machine which computes a real number--
maybe it generates an inconsistent sequence, or fails to halt for some
other input. This is okay. What we're relying upon is the fact that
every machine which does compute a real number will eventually manage
to compute an epsilon_n/2 approximation of its number, on the slies of
time we give it, and thus the associated interval will get included in
the list and cover the associated real number.

The sequence of lengths of intervals converges only in the weak sense
like the previous example.

Keith Ramsay