Re: Computable functions/reals.

On Sun, 17 Aug 2008 21:34:41 -0700 (PDT), reasterly@xxxxxxxxx wrote:

On Aug 16, 6:08 am, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Fri, 15 Aug 2008 21:28:46 -0700 (PDT), reaste...@xxxxxxxxx wrote:

My proof shows even machines like Zeno machines,
which we assume can perform an infinite number
of operations in finite time, can't write an infinitely
long string and halt (or be halted).

Ah. "And halt". Fine. This machine that computes
a computable function from R to R doesn't halt.

How do you know what is on the output tape
if the TM doesn't halt?

You don't ever see _all_ of the output. Which
makes perfect sense - that's the way real numbers
are. Given an N and an x there exists M such that
after the machine has read the first M digits of x
it has output the first N digits of f(x).

You are implicitly assuming the machine halts
when you assume the output tape exists
and has a representation of 2x on it.

I think you are arguing the following:

You can think what you want about what I'm
arguing. In _fact_ I haven't said anything
about infinitely fast machines.

Assuming we have a TM that can perform
an infinite number of operations in finite time,
and assuming this TM can read and write
infinite tapes in finite time, then f(x) = 2x
is a computable function where x is real.

If this is what you think then you are wrong.
Even assuming there exists an infinitely fast TM,
I can prove the output on the tape is always finite.
If your claim is true then 2*PI is a rational number.


Russell
- 2 many 2 count

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

  • Re: Confused, was Re: functions that halt
    ... > complete list in finite time, ... this program doesn't halt. ... infinite number of those steps; ... > countability of the union of countable sets, ...
    (comp.theory)
  • Re: Computable functions/reals.
    ... of operations in finite time, ... a computable function from R to R doesn't halt. ... How do you know what is on the output tape ... an infinite number of operations in finite time, ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... finite time is finite. ... read an infinite tape one character at a time. ... "Understanding Godel isn't about following his formal proof. ...
    (sci.logic)
  • Re: An uncountable countable set
    ... on these infinite numbers works), so those balls are also removed at ... reached" means that "all insertions and removals are before noon"? ... no infinite process can occur in finite time. ...
    (sci.math)
  • Re: Computable functions/reals.
    ... we decide if a string is a natural number ... finite time is finite. ... read an infinite tape one character at a time. ...
    (sci.logic)