Re: turing completeness

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

  • Next message: Edward G. Nilges: "Re: turing completeness" 
    Date: 2 Feb 2004 18:03:44 -0800

    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.

    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.

    I suggest that in place of long discussions, members of this group
    might actually crack a book and access an original source, including
    one about the intellectual context in which Alan Turing worked. In
    this context, a backlash against Bertrand Russell's "platonist"
    philosophy of mathematics, which hypostatized "real" infinities and as
    it turned out nonexistent sets, had created the "intuitionist" and
    "formalist" philsophies of mathematics.

    Formalism was David Hilbert's movement, that claimed that programming,
    like video game programming in the outdated language C, was a game
    with symbols without special meaning.

    Intuitionism denied actual infinities and in a related gesture, it
    rejected the axiom or law of the excluded middle. It was able to show
    in the case of infinity that one could use instead the just-in-time
    idea to get the same effect.

    Arrogant programming, prior to Dijsktra's March 1968 letter to CACM
    about structured programming, was Russellian and Platonist in the
    sense that it refused to look very hard at the set of assumptions and
    the constructs in a real program.

    As Professor Knuth pointed out in the 1970s, structured and OO
    programming styles are more intuitionistic in that they stress the
    need to rebuild and reconstruct based on the limitations of our minds.
    This shot of intuitionism caused a software productivity jump in the
    1980s, but a return to arrogance during the dot.com boom put paid to
    that.

  • Next message: Edward G. Nilges: "Re: turing completeness"

    Relevant Pages

    • Re: Turing machines, quantum computers, and alephs
      ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
      (comp.programming)
    • Re: Turing machines, quantum computers, and alephs
      ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
      (sci.math)
    • Re: Turing machines, quantum computers, and alephs
      ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
      (sci.math)
    • Re: Turing machines, quantum computers, and alephs
      ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
      (comp.programming)
    • Re: The Modified Halting Problem, Take ??? .
      ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... and there is no last digit of Pi ever computed which one would think ...
      (sci.logic)