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

From: patty (pattyNO_at_SPAMicyberspace.net)
Date: 11/19/04 

Date: Fri, 19 Nov 2004 18:10:20 GMT

tchow@lsa.umich.edu wrote:

> 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.

... which pretty much describes a PC connected to the Internet.

patty

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 ...
    (comp.theory)
  • 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: Guidance sought on how memory is used
    ... Their use of PCs may well be playing simple games or letter writing. ... have been stripped of Hard Drives and Memory (of any larger size - ... to install WinXP. ... decided to give the 256mb chip a try and added that to the ...
    (alt.comp.hardware.pc-homebuilt)
  • Re: A non-switchers take on the Mac
    ... The cost of memory at that time was a different matter. ... The problem with the PCs was not the processor ... IIRC the IT staff at the time pointed out ... applications and neither got on particularly well with Windows. ...
    (uk.comp.sys.mac)
Quantcast