Re: Computable functions/reals.
- From: Keith Ramsay <kramsay@xxxxxxx>
- Date: Fri, 22 Aug 2008 23:59:27 -0700 (PDT)
On Aug 12, 9:21 pm, Bill Taylor <w.tay...@xxxxxxxxxxxxxxxxxxxxx>
wrote:
|There are (I think) various ways of defining computable
|functions of reals, and they are not all equivalent,
|and none seems to have an accepted pride of place
|or even primus inter pares.
|
|Is this in fact the case?
I think the situation is much tidier than you seem to
think. I think the definition that others here seem to
like best is at least close to being standard. One of
various equivalent ways of formulating it is to say
that a computable function is given by a Turing machine
with an oracle that provides it with rational approximations
of its input x to within 1/n for any given positive integer
n, and which in turn provides an rational approximation
to within 1/m of f(x) for any given m>0.
Getting from the definition on Wikipedia to this one is
not especially tricky. We can enumerate the rationals by
a computable sequence r1,r2,..., and by the Wikipedia
definition f(r1),f(r2),... is required to be a computable
sequence of reals. The Wikipedia definition also requires
that there is a modulus of uniform continuity for f. I
think it is just a mistake that it's defined as uniform
on all of R and not just bounded intervals of R, but it
doesn't matter for the implication in this direction.
With an oracle to approximations to r, and an algorithm
giving an effective modulus of uniform continuity for f
in an interval containing r, and given an n>0, we find
a rational approximation to f(r) to within 1/n as follows.
Use the modulus of uniform continuity to find an m>0
such that if |r'-r|<1/m, then |f(r')-f(r)|<1/2n. Use the
oracle to get a rational q such that |q-r|<1/m. With the
algorithm computing f(q), get a rational approximation
s, where |s-f(q)|<1/2n, hence |s-f(r)|<1/n.
To go from our definition to the Wikipedia one is trickier.
Given n>0, for each r, the fact that an approximation q to
within 1/n of f(r) can be computed by querying the oracle
to approximations to r finitely many times means that the
same approximation works for all r' within some open
interval containing r, hence differences in valus of the
function are bounded by 2/n. Moreover we an algorithm that
computes such an interval from r.
Any closed interval with r in its interior is compact, and
by the Heine-Borel property any open cover has a finite
subcover. This means that in principle, for any given
n, we can compute a finite covering of the interval by
intervals on which function varies by at most 1/n. This
gives us a way of computing modulus of uniform continuity
on the interval. So as long as we adjust the Wikipedia
definition to require uniform continuity only on intervals
everything works out okay, nonconstructively.
The invocation of Heine-Borel is what makes this interesting.
The covering property fails in a strong way for computable
reals. Given epsilon>0, there is a computable sequence of
intervals with rational endpoints that covers the computable
reals, and such that the total length of any finite subset
of them is <epsilon. Clearly if I is an interval of length
epsilon, no finite subset of these intervals will cover I.
Let me sketch how the sequence can be constructed. Allocate
to each Turing machine M_i some length bound L_i, such that
the bounds total to less than epsilon. Then start running
the machines, giving M_i an n such that 1/n<L_i/2. One can
simultaneously simulate increasing numbers of machines as
one goes. If M_i gives us a rational q_i, then we know that
if M_i is a machine that computes a real r_i, then
|q_i-r_i|<1/n. Hence r_i has to be within [q_i-1/n,q_i+1/n].
Of course, we are not necessarily guaranteed that M_i does
compute a real at all. But that's okay. All we need is an
interval that contains the real that it would compute, if
it does compute one.
There is no computable limit to how long it might take for
M_i to compute an approximation to its real, for all i. But
this also is okay. We can let the machines we are simulating
run until they do output an approximation, and then put the
interval into the sequence.
So the corresponding definition of "computable function of
computable reals" fails to imply uniform continuity on
intervals. In fact, using the above construction we can cook
up a computable function on the computable reals in [0,1]
that is unbounded. By a famous theorem discovered both by
Kreisel, and by Lacombe and Shoefeld, such a function has
to be pointwise continuous at the computable reals. But it
can run off to infinity at uncomputable reals.
There is a perhaps even more famous result by Brouwer, on
the other hand, in which he claimed that every real function
on [0,1] is uniformly continuous. Of course, he was not
using the assumptions that are usual in mathematics. He
had a theory of free-choice sequences, of which one could
only know a finite number of terms at any given time. For
the value of a function on a free-choice sequence to be
defined, it would have to be the case that each approximation
to f(r) can be inferred from only finitely many approximations
to r. This is analogous to the way we've defined computability.
He also had an argument for the needed covering property.
I can only think of a few different ways that one might be
tempted to use a different notion of computability than this
main one. We can see why dealing in decimal expansions instead
of rational approximations doesn't work very well. The
function f(r) = r+1/3 winds up being uncomputable in those
terms, since if r=0.6666... there's no finite number of
decimal places that allows us to determine whether r+1/3 is
=1 or <1, so we can't get the first digit of r+1/3.
One might be tempted to restrict the domain to computable
reals. It's coherent to talk about computable functions on
the computable reals, but there's no reason to identify
this with the concept of computable functions on all the
reals. The assumption that the real being computed with is
computable is just unnecessary.
Keith Ramsay
.
- References:
- Computable functions/reals.
- From: Bill Taylor
- Computable functions/reals.
- Prev by Date: Re: The Eighteenth solution drawn from “Set A belongs to Set B” and “Set C belongs to Set D”
- Next by Date: Re: Definability problem
- Previous by thread: Re: Computable functions/reals.
- Next by thread: Re: Computable functions/reals.
- Index(es):
Relevant Pages
|
