Re: Turing Machines and Physical Computation

From: Kent Paul Dolan (xanthian_at_well.com)
Date: 12/07/04 

Date: Tue, 7 Dec 2004 10:33:55 +0000 (UTC)

"Albert van der Horst" <albert@spenarnc.xs4all.nl> wrote:

> The wording is a bit metaphysical. This problem
> is such that for each N there is an instance of a
> language item wherefore a dedicated TM will need a
> tape that is larger than N. Actual infinity
> doesn't enter the picture.

Well, no and that's a common error, like getting the
order of an epsilon-delta proof backwards.

The way the game is played is this: you make an
assertion that a Turing machine with a finite tape
size suffices for all problems; _then_ I say, "oh?
how big?", _then_ you give me an N for a number of
tape cells you think will suffice, and then lastly
I, to refute your claim, need merely give you a
problem that can be solved on a tape larger than N,
but not on a tape of size N. The argument doesn't
make sense in the order you want it presented.

The issue isn't "does a finite tape suffice for a
predefined list of problems known in advance to
halt", that's not controversial.

The issue is, "does any tape of a predefined size
suffice for _all_ problems".

If you cannot predefine the size of the tape, then
that tape is _not_ finite, because to be finite it
must have a finite size, and yet any finite size you
claim for it can be proved to be insufficient,
smaller than it really needs to be to handle the set
of problems you claim it can handle.

So it must be bigger than any such size, and a tape
that is bigger than every finite size you can name
even in concept is an infinite tape.

HTH

xanthian. 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

Relevant Pages

  • Re: Turing Machines and Physical Computation
    ... assertion that a Turing machine with a finite tape ... tape cells you think will suffice, ... So it must be bigger than any such size, ... even in concept is an infinite tape. ...
    (sci.math)
  • Re: Set Theory: Should You Believe
    ... there is such a thing as an infinite tape, ... Turing Machines do not exist. ... Infinite tape is only needed for problems which can't be solved, ... So computability theory is basically an achievement in fiction writing, ...
    (sci.logic)
  • Re: Set Theory: Should You Believe
    ... there is such a thing as an infinite tape, ... Turing Machines do not exist. ... Infinite tape is only needed for problems which can't be solved, ... and how to structure computer languages ...
    (sci.logic)
  • Re: A case for HTML as a programming language
    ... but a Turing machine without an infinite tape is not a Turing ... I think it could be doable with modern HTML; ...
    (comp.programming)
  • Re: What is complexity?
    ... >> necessary to have an infinite tape in a physical Turing machine, ... >> long as the tape can grow. ... the head reaches the end of the finite tape: ... Since a true Turing machine always only uses a finite amount ...
    (talk.origins)