[FOM] Regarding PTIME reals

[Harvey Friedman]

One has to be careful about PTIME reals, = Polynomial Time computable reals.

One does NOT have to be careful about RECURSIVE reals.

There are several somewhat reasonable looking definitions, some good,
some bad, for PTIME reals.

There seems to be only one somewhat reasonable looking definition,
which is good, for RECURSIVE reals.

GOOD DEFINITION - PTIME REALS

There is an algorithm A such that for each n, inputted in unary, A
produces a rational number p in binary, such that

|x - p| <= 2^-n

which takes computer time given by a polynomial in n.

BAD DEFINITION - PTIME REALS

Anything like this for digits in base 2 (or any base). E.g., for x in
[0,1] only (general case trivially handled from special case),

There is an algorithm A such that for each n, a bit A(n) in {0,1} is
produced, such that one of the base 2 expansions of x is

.A(1)A(2)A(3) etc.

which takes computer time given by a polynomial in n.

THEOREM 1. Under the Good Definition, the PTIME reals are closed under addition.

Proof: Add properly. QED

THEOREM 2. Under the Good Definition, the PTIME reals form a real closed field.

Proof: This is of course harder, and involves isolation of zeros of
one variable polynomials with PTIME coefficients, and using iterated
differentiation. QED

THEOREM 3. Under the Bad Definition, there are PTIME reals x,y in
[0,1/2] such that x+y is not a PTIME real.

Proof: The basic idea is the following illustration:

.00000000000.....(0 or 1)00000000000.......(0 or 1)etc.
.011111111111......1.........011111111111........1etc

And then we add these two PTIME real numbers. The first digit of the
sum is 0 if the (0 or 1) is 0, and the first digit of the sum is 1 if
the (0 or 1) is 1. The first (0 or 1) is called the "first split".

Let us say that the splits occur at positions f(1),f(2),f(3),..., and
a nicely PTIME algorithm is running in the background in its usual
diagonal way determining the split, 0 or 1, at that position. This
splitting is arranged to fool any given PTIME algorithm from guessing
properly by merely using the correct previous splits. QED

QUESTION: Is there an even more embarrassing counterexample than Theorem 3?

Harvey Friedman