Re: Computable functions/reals.

On Aug 19, 3:43 am, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Mon, 18 Aug 2008 19:15:46 -0700 (PDT), reaste...@xxxxxxxxx wrote:


Given two tapes, each with a Cauchy sequence written
as pairs of integers (like above), determine if the
two real numbers represented by these tapes differ
by more than 1/10.

In fact there are various details that have been unmentioned,
or mentioned only once or twice, in all this. When people
have said "Cauchy sequence" they actually mean, or
should mean, more than that here, namely a Cauchy
sequence _together with_ information on the rate of
convergence.

I don't know a word for that - the point is instead
of "Cauchy sequence converging to x" we should
really talk about something like "a sequence of
rationals r_j such that |x - r_| < 1/j for all j." Let's
agree to call that an "effective Cauchy sequence"
(there's probably a standard term for it that I
don't know).

I realize that the method of representing real numbers
is not central to your argument about computable
real functions.

You could use the factorial numbering system.
Every rational number has finite representation
in the factorial base. This would give a Cauchy
sequence with a rate of convergence of 1/n!.

I think my objection is more basic.
At this point I am not sure there are computable
functions for the natural numbers.

I can show that no sequential machine can
read or write more than a finite number of
positions from a tape. A sequential machine
is any machine that reads or writes one
character at a time.

Assume I am given an infinitely long tape.
This tape may unary representation of a natural
number (a string of non-blank characters followed
by a blank space) or it may contain no
non-blank characters.

Even an infinitely fast sequential machine can only
read a finite number of positions from this tape.

This means no sequenial machine can always
determine if the tape contains the representation
of a natural number.

I think this is enough to prove there exists
uncomputable natural numbers.


Russell
- Integers are an illusion
.

Relevant Pages

  • Re: get CPU info, RAM info
    ... stored in arrival sequence. ... Initially the computer prime input methods were cards and paper tape, ... the only character at a time i/o ...
    (comp.lang.java.programmer)
  • Re: abundance of irrationals!)
    ... BUT THAT'S JUST A DIVERSION AWAY FROM YOUR FAILURE TO STATE YOUR CLAIMED ALTERNATIVE DEFINITION OF SUM1/2^k AS DISTINCT FROM A LIMIT OF A SEQUENCE OF PARTIAL SUMS. ... >> as a binary representation of unity, ... is not defined by the standard limit of a sequence of partial sums, YOU must state YOUR definition of 0.111... ...
    (sci.math)
  • Re: Sequences of digits
    ... A real number can be represented by an infinite sequence 0.abc... ... path of the complete infinite binary tree (CIBT), ... belong to an additional binary representation. ...
    (sci.logic)
  • Re: Proof 0.999... is not equal to one.
    ... trivial fsct and easy to prove! ... An infinite series, by definition, is a sequence. ... is a representation of a real number. ...
    (sci.math)
  • Re: Proposal for adding symbols within Python
    ... > Symbols are objects whose representation within the code is more ... I believe it would be more useful to have enumerated types in Python, ... Enum type in the language. ... compared with cmpif their sequence was considered important. ...
    (comp.lang.python)