Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)

tchow_at_lsa.umich.edu
Date: 11/19/04 

Date: 19 Nov 2004 18:02:28 GMT

In article <320e992a.0411190852.7ce02e6c@posting.google.com>,
>I have had such a discussion with an extremely intelligent and
>experienced mathematician. He told me that PCs are not Turing
>Machines, because they have "an infinite tape". I think he did not
>know anything about descriptive complexity. This infinite portion of
>the tape consists entirely of blank symbols, and therefore has
>descriptive complexity O(1), which is easily realized by a physical
>system.

I think you mean "descriptional complexity" or "Kolmogorov complexity";
the term "descriptive complexity" nowadays is reserved for a different
subject. But in any case, Kolmogorov complexity is irrelevant to the
argument that PCs are not Turing machines. PCs do not have unbounded
memory; they have a fixed finite memory, and hence can be modeled as
finite-state automata. To build something that "is" a Turing machine in
some defensible sense (as opposed to something that is *usefully modeled*
or *approximated* by a Turing machine), one should at least build it so
that it has no a priori memory bound, and continues eating up whatever
resources are available in the universe as needed. 

-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

Relevant Pages

  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... He told me that PCs are not Turing ... >know anything about descriptive complexity. ... memory; they have a fixed finite memory, and hence can be modeled as ...
    (sci.math)
  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... He told me that PCs are not Turing ... >>know anything about descriptive complexity. ... > memory; they have a fixed finite memory, and hence can be modeled as ...
    (sci.math)
  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... He told me that PCs are not Turing ... >>know anything about descriptive complexity. ... > memory; they have a fixed finite memory, and hence can be modeled as ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... >>(potentially infinite) and actually infinite. ... Turing said the TM ... physical memory in the universe, if every subatomic particle could be ... It doesn't matter if you consider the tape to be only hugely finitely large. ...
    (comp.theory)
  • Re: Lambda Calculus and Turing Equivalence
    ... >>(potentially infinite) and actually infinite. ... Turing said the TM ... physical memory in the universe, if every subatomic particle could be ... It doesn't matter if you consider the tape to be only hugely finitely large. ...
    (sci.math)
Loading