Re: Why? [was Re: Cantor`s powerset theorem is false?]


"Patricia Shanahan" <pats@xxxxxxx> wrote in message
news:%VRcg.6017$x4.3730@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
david petry wrote:
Patricia Shanahan wrote:


Rather trivially, we could design a Turing machine to take any natural
number as its input, and return the next natural number.


Such a TM will have a finite input tape and a finite output tape.

You may be able to design it, but you cannot build it so you cannot do
any experiments on it. Every TM, by definition, incorporates at least
one infinite tape.



A TM operates on symbols, not on natural numbers.
We assume there is a mapping of finite symbols to the natural numbers.
For example, we can use a unary numbering system that represents
each natural number by a string of 1's followed by a blank.
The number three would be represented by the symbol 111b.

111b is just a symbol to the TM which has no idea what
a natural number is. We interpret the output of the TM
using what is essentially an infinite translation table.

As I've stated before, we can talk about the infinite if we can talk
about approximations to the infinite, and in this case, we can do that.

A TM has no clue what infinite means.
"Infinite" is undefinable as far as a TM is concerned,
unless you define infinite to mean the TM does not Halt.

The "approximation" idea is a non-starter, because the property under
discussion is different between any real machine, including any
finite-tape subset of a TM, and a true TM with its infinite tape. In any
realizable computer, there is a largest storable integer. Given that
number as input, the computer cannot calculate the next number, because
it doesn't have a long enough tape, or large enough disk, to store it.

The TM's ability to calculate the next natural number given any natural
number as input is a consequence of it having an infinite tape.

The successor function can be implicated using only finite input and output.
The translation table that maps symbols to natural numbers
must be infinite.

However, given the fact that you are willing to count thought
experiments about unrealizable concepts, such as Turing machines, how do
you draw the line?

What is the qualitative difference between thinking about what would
happen if we had an infinite tape, and so could build a TM, and thinking
about the set of sets of memory locations in a TM?

Even if we assume that a TM can perform an infinite number of computations
in a finite amount of time and that we have an infinitely long tape,
no TM can write an infinitely long string to a tape.
See my post on hypercomputers.

Even if we assume the TM can write an infinitely long string,
the TM will always tell us that it has only written a finite number of
symbols.

I really question some of the definitions of computability.
For example, I don't consider PI to be a computable number.
It is true that we can compute any digit of PI.
That is not the same as saying we can compute all of the digits of PI.


Russell
- 2 many 2 count


.

Relevant Pages

  • Re: Cardinality of Set of Computable Numbers?
    ... the INITIAL input tape WAS ... it follows that x is an infinitely long string. ... Saying x has an infinite number of 1's is overkill. ...
    (comp.theory)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... and there is no last digit of Pi ever computed which one would think ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... down or erasing binary digits one-at-a-time in the cells on a linear ...
    (sci.logic)
  • Re: turing completeness
    ... claim that the tape *must* be infinite. ... >>The Turing Machine just needs to be able at will to drive to CompUsa ... computer runs out of memory its operating system aborts the TM ...
    (comp.programming)
  • Re: Computable functions/reals.
    ... can't read every position of an infinite tape. ... Then a Zeno machine becomes a machine that "accelerates ... halted, otherwise, the normal TM never halts. ...
    (sci.logic)