Re: Set Theory: Should You Believe

Peter Webb wrote:
The theory of computability begins with a false premise, i.e. that
there is such a thing as an infinite tape, or (equivalently) a tape to
which you can always add one more cell. There is no such machine, and
no such tape. In short, Turing Machines (as defined) do not exist.

*** Not true in one essential regard. All problems that can be solved -
produce a valid output - do so after a finite number of steps, and hence
only use a finite amount of tape. The problems you can't solve are those
that require an infinite number of steps to compute - ie they never halt.
Infinite tape is only needed for problems which can't be solved, and that is
basically why they can't be. You can't write 1/3 in base 10, because a
Turing Machine which pumped out 0.333... would require an infintely long
tape for the answer. Therefore it is impossible. No Turing machine that
solves a problem could actually ever use an infintely long tape, because it
would never halt. The infintely long tape is only needed for things you
can't do.


I would think an infinite tape is required because, for
any tape with finite length L, there is going to be a solvable problem
that requires a tape with length > L.

So it doesn't seem to me to be [only] the unsolvable problems that
require an infinite tape.

I suppose one way around this is, if you have a machine with tape
length L and the problem barfs because the tape isn't long enuf,
you keep adding to the tape until its long enuf.

Thanks.

Ken

So computability theory is basically an achievement in fiction writing,
different in no essential way from a Harry Potter novel. Assuming the
existence of an infinite tape is no different from assuming that people
can levitate, or that pigs can talk, or that you can feed a million
people with one fish. It may be entertaining to explore the
consequences of such false assumptions, but those consequences are not
true (except vacuously), and they are not useful. In short, it's a form
of idle speculation which deserves to be ridiculed, not admired. No
different really from great achievements of the 13th century, like
Aquinas' elegantly reasoned demonstration that we won't have to crap in
the afterlife.

*** That's simply not true, for very important practical and economic
reasons. Having "bugs" in computer programs so that they do strange things
(like go into infinite loops) is a huge economic problem. Computer languages
are Turing Machines; the theory of computability tells us exactly how far we
can in automated program checking, and how to structure computer languages
and systems to minimise this cost.


The reality is that even computable functions are not computable.
Computability is not determined by a definition on a piece of paper.
It's determined by the ability to mobilize physical resources in the
real world.

*** Well, yes if you are interested only in the real world.

.

Relevant Pages

  • 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: 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: Ask an atheist a question
    ... its tape, and it can rewrite those programs as it runs. ... A Turing machine can have an infinite tape (for the ... incarnation and there's not an infinite amount of matter in the ... So the amount of information that the Turing Machine is aware of increases ...
    (uk.religion.christian)
  • 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)
  • Re: Notions of computation
    ... > formalizing the same notion of computation: Turing machines, ... > recursive functions, lambda calculus, combinatory logic, etc. ... Step 1: Representation of tape. ...
    (comp.theory)