Re: Arthur O'Dwyer on the feasibility of simulating a Turing Machine

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 02/29/04 

Date: 28 Feb 2004 17:40:07 -0800

gerryq@indigo.ie (Gerry Quinn) wrote in message news:<tT%%b.4979$rb.63004@news.indigo.ie>...
> In article <f5dda427.0402271924.2448d0b1@posting.google.com>, spinoza1111@yahoo.com (Edward G. Nilges) wrote:
> >gerryq@indigo.ie (Gerry Quinn) wrote in message
> > news:<rHM%b.4882$rb.62736@news.indigo.ie>...
> >> In article <f5dda427.0402270154.2be3a401@posting.google.com>,
> spinoza1111@yahoo.com (Edward G. Nilges) wrote:
> >> >
> >> >What everyone knows appears to be wrong for everybunny is assuming
> >> >that the "infinite" tape must pre-exist for the Turing Machine to
> >> >start out.
> >> >
> >> >THIS IS WRONG.
> >>
> >> We can certainly allow the machine to add tape as needed. However, it
> >> is not a Turing machine unless it has the ability to add an unbounded
> >> amount of tape.
> >
> >Cudgel thy brains. Unbounded != infinite.
>
> I never said it was. There must be no limit to the amount of tape it
> can add - that is a better way to say it.
>
> >> Certainly this can be done, although it would be simpler to have a
> >> factory churning out extra lengths of magnetic or otherwise rewritable
> >> tape that can be added as required to a length of tape floating in
> >> intergalactic space.
> >>
> >> Whether this is possible or not depends somewhat on cosmological
> >> factors, but current theories of cosmology suggest strongly that it is
> >> not. We would need a space in which the tape, unwound to an appropriate
> >> density, will remain stable with respect to gravitational collapse or
> >> indeed a long distance repulsive counterpart to gravity. And
> >> unbounded amounts of matter would have to be available for creating the
> >> tape. But as far as we know now, the amount of matter accessible to the
> >> human race is finite and decreasing.
> >>
> >This discussion is confused and confusing because we shift what we're
> >talking about, but the TM could always pack (using TM-Zip let us say)
> >its information before it needed "more" tape.
>
> You don't seem to understand the most fundamental concept of information
> theory, from which all else flows. A binary string of length n can
> describe exactly 2^n different strings, which is precisely the number of
> binary strings of length n. So if a packing method can successfully
> identify some long strings using short strings, a corresponding number
> of short strings must be identifiable only by long strings! [Using
> multiple packing methods doesn't help, because the choice of the packing
> method becomes part of the description. And if you want to do something
> fancy with strings that know their own length, remember to include the
> terminator or length in the string description.]
>
> In short, you CANNOT in general release space by packing data.

Of course I've been familiar with info theory for some time. And I
agree that the entropy of packing is that rare short strings are
encoded as long strings.

But this has precisely nothing to do with your inability to see that a
computer can simulate a TM and that unless Church's thesis is false,
a computer is Turing equivalent to a TM.
>
> >You can always replace a long integer by its floating point
> >representation, added to a SMALLER integer to get to the precise
> >value. Generalize this to "hyper floating point" with multiple
> >exponents such that the value of the HFP number is the mantissa times
> >the product of MORE THAN ONE power of the base, and this packs the
> >large number into smaller space.
>
> See above - you can't.
>
> >IF the Turing machine were assigned the mission "simulate any TM as a
> >UTM while making sure you use a bounded amount of tape" it MIGHT be
> >able to accomplish this mission by a complex set of quintuples which
> >included a sort of "operating system" for packing information in the
> >bounded tape.
>
> See above - it can't.
>
> Also, if the tape is to be bounded at length googolplex, how do you
> simulate the Turing machne that answers the question: "Is
> <random googolplex-length string> prime?"? You can't even fit the data
> in.
>
> Gerry Quinn

Relevant Pages