Re: Set Theory: Should You Believe

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.

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: Computable functions/reals.
    ... and also to a standard idea of computable reals. ... given a decimal expansion of x on the input. ... infinitely long tape of course). ...
    (sci.logic)
  • Re: Set Theory: Should You Believe
    ... Besides a handful of basic vocabulary, Wildberger knows nothing about ... characterize and clarify the notion of computability, ... there is such a thing as an infinite tape, ... Turing Machines do not exist. ...
    (sci.logic)
  • Re: No-op microprocessors
    ... Allan Turing proposed a machine, now referred to as the "Turing ... A tape reader that could only do 3 things: ... Read the bit at the current position of the tape. ... Turing used this conceptual model in his work on computability. ...
    (sci.electronics.design)
  • Re: Set Theory: Should You Believe
    ... existence of an infinite tape is no different from assuming that people ... Computability is not determined by a definition on a piece of paper. ... for many purposes infinite memory models are a more useful ... Most real computers have far too many states for it ...
    (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)
Quantcast