Re: turing completeness
From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 02/04/04
- Next message: Richard Heathfield: "Re: PLEASE READ (was Re: recursive proofs)"
- Previous message: Richard Heathfield: "Re: PLEASE READ (was Re: recursive proofs)"
- In reply to: Kenneth Chiu: "Re: turing completeness"
- Next in thread: Programmer Dude: "Re: turing completeness"
- Reply: Programmer Dude: "Re: turing completeness"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 3 Feb 2004 17:03:49 -0800
chiuk@cs.indiana.edu (Kenneth Chiu) wrote in message news:<bvosnm$t5s$1@hood.uits.indiana.edu>...
> In article <f5dda427.0402030924.4dfaf831@posting.google.com>,
> Edward G. Nilges <spinoza1111@yahoo.com> wrote:
> >chiuk@cs.indiana.edu (Kenneth Chiu) wrote in message
> >news:<bvn9gp$bqu$1@hood.uits.indiana.edu>...
> >> In article <f5dda427.0402021803.66bdea6@posting.google.com>,
> >> Edward G. Nilges <spinoza1111@yahoo.com> wrote:
> >> >Programmer Dude <Chris@Sonnack.com> wrote in message
> news:<401EC86C.B9AAD0C3@Sonnack.com>...
> >> >> "Edward G. Nilges" wrote:
> >> >>
> >> >> > For example, you can simulate a Turing Machine in any one of Fortran,
> >> >> > Cobol, Basic, PL/I, perl, python, etc. You can even simulate a TM in
> >> >> > C, despite the fact that C is outdated.
> >> >>
> >> >> We had a long discussion about this a while back. A TM requires an
> >> >> infinite "tape". Any language whose specification provides limits
> >> >> cannot provide an infinite tape. Some of the languages above do
> >> >> specify limits. The bottom line appears to be that a language must
> >> >> be defined somewhat abstractly to be truly, mathematically TC.
> >> >
> >> >The tape doesn't have to be "infinite", only unbounded in the sense
> >> >that in the formalism, the tape may be either "infinite" or
> >> >expandable, such that when space runs out new space is allocated in an
> >> >unspecified way. Turing was influenced by mathematical "intuitionism"
> >> >which would probably deny that you can posit an "infinite" tape but
> >> >can posit an unbounded tape, that would expand, in modern parlance,
> >> >just in time by adding squares when space runs out.
> >>
> >> Yes, more or less.
> >
> >No, just yes. The tape doesn't have to be "infinite" once and for all.
>
> I never said it does.
I am aware of that, Kenneth. I was answering another poster's apparent
claim that the tape *must* be infinite.
>
> >The Turing Machine just needs to be able at will to drive to CompUsa
> >:-) and buy more tape.
> >
> >And many mathematicians would balk at saying "the tape is infinite"
> >because they deny that using an actual infinity in a mathematical
> >argument.
>
> That's why I said "more or less". Because _you_ used
> "infinite" in your informal definion of unbounded.
We're saying the same thing. It's "infinite" if you believe the
infinite exists as a mathematical construct. It's "unbounded" if you
don't.
>
> >
> >
> >
> >>
> >> >And this can be simulated in the pragmatic sense because you can
> >> >allocate a small array for the infinite tape but expand the
> >> >array...just in time. The ultimate bound of the simulation is physical
> >> >reality which makes perfect sense because a program is not an abstract
> >> >mathematical object. Instead, it's a trace of social labor which
> >> >executes on a physical machine...something Dijkstra (despite his
> >> >reputation as an "ivory tower" theorist) never forgot, but that the
> >> >nonprogramming computing Establishment would like us to forget, so
> >> >that we accept machine decisions quietly.
> >> >
> >> >Therefore, if you are claiming that "it is impossible to simulate a
> >> >Turing machine on a physical computer" you are wrong.
> >>
> >> Perhaps, but that's not what he's claiming. He's claiming
> >> that if the language specifies a limit, then it may not be
> >> TC. For example, if a language says that no more than 4 GB
> >> of memory may be used, then the language is clearly not TC
> >> in the formal sense.
> >
> >Ordinarily I would not object to saying "the language says" but here I
> >must make a slight correction. The language doesn't "say"; the
> >language standard makes this declaration. And note that few language
> >standards make this declaration.
> >
> >If the language standard says that "the length of a string shall be in
> >a 32-bit word" then I suppose that this "says" that "a string" (not
> >total memory) is bounded and this implies that a string cannot emulate
> >a TM tape.
> >
> >But even this doesn't prevent an accurate simulation from using a
> >string array.
>
> Look, the original claim was about languages. You
> misinterpreted this as a claim about physical machines.
>
> That's really all I wanted to point out. Note that _my_
> only claim is that:
>
> If a programming language limits the amount of "memory"
> that can be used, it cannot be TC.
>
> Or, more formally:
>
> Given appropriate mappings of a TM to programming
> language (PL) constructs, it is possible for a PL
> to exist where:
>
> There exists an integer N such that for all
> recursive languages that can be recognized by a TM
> using N tape cells or fewer, there also exists a
> computer program that can recognize the same
> recursive language.
>
> AND
>
> For some recursive language L which requires more
> than N tape cells to recognize, there does not exist
> a computer program in that PL that can recognize L.
>
> I could probably replace recursive with RE, but I'm too lazy
> to think about it, and I don't think it changes anything.
> This is really a very weak claim, and pretty boring.
>
> Also note that I'm not disputing your claim that you can
> simulate a TM on a physical computer. That depends on how
> you define physical computer, and it's clear you are trying
> to define it in such a way that it _can_ simulate a TM.
I think we're converging on a solution. I think it is that a TM cannot
be simulated in all cases by a single computer because when a single
computer runs out of memory its operating system aborts the TM
simulator.
But a program running on a multi-processor can simulate a Turing
Machine as long as it "notices" in some way that the allocated tape
memory is "large", and starts a process on another machine to manage
extra squares.
When it needs to refer to the extra squares, it swaps out the least
recently used squares and swaps in the extra squares.
Of course, this could be done on a single computer's disk memory but
eventually that disk memory would be bounded by the total size of
"real" virtual memory.
Whereas if the multiprocessor solution were a worm, capable of seeking
and enslaving any computer in the world, it would...run out of memory.
Oops. Which wasn't what I'd hope to prove.
OK. It would then take over a Norad computer and threaten (like
Colossus in the old science fiction story) to destroy the world unless
we started fabricating more disk storage.
Oops. We would then exhaust the earth's resources, assuming that the
Turing Monster was working on a "tape" with an expanding memory.
OK. It would command us to conquer the universe and the original
question is answered. IF the universe is infinite, then a physical
computer running on an intergalactic network could simulate any Turing
Machine.
If the universe is not infinite then there is a Turing machine that
cannot be simulated by a physical computer.
The only other solution is to replace tape squares systematically by
pulses in time such that instead of printing a symbol when no paper is
left in the universe, the Turing machine enters a series of special
states. But strictly speaking this changes the TM's definition.
- Next message: Richard Heathfield: "Re: PLEASE READ (was Re: recursive proofs)"
- Previous message: Richard Heathfield: "Re: PLEASE READ (was Re: recursive proofs)"
- In reply to: Kenneth Chiu: "Re: turing completeness"
- Next in thread: Programmer Dude: "Re: turing completeness"
- Reply: Programmer Dude: "Re: turing completeness"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
