Re: Lambda Calculus and Turing Equivalence

From: peter_douglass (baisly_at_gis.net)
Date: 12/02/04 

Date: Thu, 02 Dec 2004 02:57:42 GMT

"Eray Ozkural exa" <examachine@gmail.com> wrote in message
news:320e992a.0412011215.199e31a3@posting.google.com...

> And what am I saying in my post that is different from this or
> contradicts it? What does "arbitrary growth of computational space"
> mean, which you failed to quote?

prd > Once again, you have made a very silly argument.

> I did not make a very silly argument at all. (And I don't think I ever
> did) You failed to read and understand my post. Look at the other
> replies.

> My "silly" argument is that TMs do *not* have an infinite tape, only
> an unbounded tape (that is finite at ALL times), and this entails that
> PCs are Turing Machines, unlike what the infinitely wise Robin Chapman
> seems to think.

OK, let's look at the part I snipped.

Eray > Since the imagined "actually infinite" tape of TM does
Eray > not exist in this other equivalent model of computation,
Eray > we conclude that it is not part of a TM to start with. Only
Eray > a "potentially infinite" tape can be part of a TM, because
Eray > see above, there are only a finite number of non-blank
Eray > symbols on a TM tape, and the Turing Machine has no
Eray > dealing with the infinite remainder of the tape, which
Eray > does nothing except to symbolize the arbitrary growth
Eray > of computational space.

A Turing machine, like a Klein bottle is a mathematical
construct. As such, it can be defined with whatever properties
the definer choses to give it. That no physical thing can have these
properties is not relevant. For example, I can talk about a Klein
bottle as a mathematical object, but I almost certainly will never
experience a real Klein bottle.

If the tape of a Turing Machine is defined to be infinite,
or even "actually infinite", then it is "actually infinite", even
though we are unlikely to experience real infinite tapes.
This is just as much true as if I define the set of integers to
be "actually infinite". Perhaps you would also argue that
the set of integers is only "potentially infinite", that it is only
a "imagined" to be an "actually infinite" set. That's fine. Go
off and converse with whatever community accepts your
terminology. But by now you should understand that you
are not speaking the language of the mathematics community.

--PeterD

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (sci.math)
  • Re: turing completeness
    ... The tape doesn't have to be "infinite", ... Turing machine on a physical computer" you are wrong. ... Formalism was David Hilbert's movement, that claimed that programming, ...
    (comp.programming)