Re: [EGN] turing completeness

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

Date: 9 Feb 2004 12:42:46 -0800

Corey Murtagh <emonk@slingshot.no.uce> wrote in message news:<1076333401.521207@radsrv1.tranzpeer.net>...
> Edward G. Nilges wrote:
> > Programmer Dude <Chris@Sonnack.com> wrote in message news:<40210ACE.1472A1BB@Sonnack.com>...
> >
> >>"Edward G. Nilges" wrote:
> >>
> >>>If the universe is not infinite then there is a Turing machine that
> >>>cannot be simulated by a physical computer.
> >>
> >>Exactly my point.
> >
> > OK, but there is an infinity of Turing Machines that CAN be simulated
> > by a digital computer. I thought your claim was that NO Turing Machine
> > can be simulated by a computer.
>
> There's that word again.
>
> An infinite number of /distinct/ Turing Machines require an equal number
> of representations. Since no machine can be infinite, no machine can
> store /all/ possible Turing Machines, and thus there are not an infinite
> number of Turing machines that can be simulated by a digital computer.
>
> QED.

You assume the highly questionable truth of mathematical Platonism.
This is because you use the word "infinite" carelessly and in a manner
that makes it clear you assume that infinite quantities exist.

Intuitionism only admits that mathematical processes can continue
without bound, and denies that we can know whether infinities
exist...in the very real, practical sense that Brouwer and Heyting
tried to develop mathematical procedures that avoided this assumption.

Furthermore...your expression of your thesis has, as far as I can
tell, a "not" in the wrong place and I THINK you desire to QED that
there IS an infinite number of Turing Machines that CANNOT be
simulated by a digital computer.

Even rephrased this is completely wrong...if that is your claim.

Even a "busy beaver" or "runaway" TM can be simulated. You power up
the damn simulator, watch it chug away grabbing memory, and then give
it the three finger salute: control, alt, delete.

ANY Turing Machine can be simulated by a program, indeed this is a
lemma we get to by developing the code for the universal TM, and
inserting the encoding of any arbitrary TM.

Of course, the quintuple list of some TM might be larger than memory
of any empirical TM, so I suppose if some monster TM has a very large
(but always finite) list of quintuples, then this TM cannot be
simulated as purely a matter of empirical reality. But, if the
universe is infinite, then even these cases can be simulated.

If the universe is not infinite then OK some specific TMs cannot be
simulated...as a proposition in physics and not in math.

In math, ANY TM can by simulated because math doesn't assume physics,
quite the opposite.

I hope I am wrong but I read in your argument, after I fixed the bug
innit, an innocent mathematical Platonism which sociologically
persuades computer programmers (as I indeed loop back to the fully
ontopic as promised, in a Nilges type 1 gesture) that a world of forms
exists and is always "better than" their life-world.

I regard this Platonism as a source of the software productivity
crisis for it causes people to actually scorn applied mathematics, a
scorn Dijkstra did not share, and causes their professional praxis to
be profoundly schizophrenic.

On the one hand, laboring under the delusion of a perfect World of
Forms, they snipe at each other like maiden aunts in comp.programming
over trivial oversights. On the other they create failure systems.

>
> > I think the important question is whether the Universal Turing Machine
> > can be simulated since, as I hope you're aware, the UTM can simulate
> > any other TM by interpreting a suitably encoded representation of the
> > state/symbol transition quintuples of the "other" TM...even if the
> > other TM is the UTM.
>
> If there are an infinite number of Turing Machines, and the Universal
> Turing Machine can simlulate any other Turing Machine, then the
> Universal Turing Machine is an infinite machine and can not be fully
> simulated on anything less than an infinite machine. Since it is
> impossible to create an inifite machine, the Universal Turing Machine is
> a philosophical abstract.

This is complete malarkey.

Please read the available literature and get back to me.

The UTM is NOT an "infinite" machine.

Using a FINITE number of quintuples of the form
(oldState,oldSymbol,motionLR,newState,newSymbol), the UTM accepts a
suitable encoding of a second, FINITE set of quintuples in the same
abstract form.

As such it is mathematically capable, given enuf time and memory
space, of simulating ANY TM whatsover.

Again, you labor under the pernicious delusion that infinite
quantities only "exist", if they exist at all, as finished inventory
in Platonic heaven.

I mean, it's one thing for me to use "sociobabble". I happen to regard
much of pop mathematics books as irresponsibly pushing a ruling class
philosophy of mathematics which presumes the reality of infinity with
no backtalk. It is a silent rejection of Continental European
philosophy in the form of Intuitionism and it is mind control.

>
> > OK, the UTM can be simulated up to the point where you insert the
> > encoding of a TM that writes its tape in the "runaway" fashion I have
> > described.
>
> Since the problem itself contains an explicit infinity, no 'runaway'
> process is required to prove the impossibility of simulating the UTM.

Please bone up on the available literature and get back to me. "The
problem itself contains an explicit infinity" is NOISE.

>
> > OK, IF Turing Machines exist as Platonic mathematical realities in a
> > Platonic Heaven, with unlimited resources in all directions, then SOME
> > of these TMs CANNOT be simulated by earthly TMs UNLESS the universe is
> > infinite.
>
> The actual requirement is that spacetime and matter/energy all be
> infinite. There are various simple proofs to the contrary, and only
> those who believe that there is a real-world validity to the Aleph
> series will argue against those proofs.
>
> Since we observe that there is /not/ infinite matter/energy in the
> universe, therefore the UTM is impossible to construct.

I only agree that a computer program simulating a UTM is NOT a UTM but
a SIMULATION of a UTM but you seem to hold the stronger, and wrong
view, that "you cannot SIMULATE a UTM".

As a proposal in computer science and programming, you CAN simulate a
UTM, and this is because any simulation of an ordinary computer will
also have aporias and flaws where it does not fully simulate the
target!

For example, a Fortran program to simulate an 8080 chip is mostly a
simple series of branches to routines which simulate the effect of
8080 instructions, but it will of course fail to simulate the physical
times of the instructions. In fact, it might run faster if run on a
modern platform.

But it isn't any less of a simulation, and it would be useless in
nearly all applications to insert sleep and wait code merely to
recapture the actual speed of the ancient chip.

Relevant Pages

  • Re: The Demise of Computationalism?
    ... instantiates a mind'. ... not equivalent to a formal Turing Machine. ... No disagreement, I just meant UTM is defined in terms of its capability for universal simulation, not that it isn't a TM. ... I'm not really sure where the 'infinite number of UTMs' ...
    (comp.ai.philosophy)
  • Re: turing completeness
    ... >> If the universe is not infinite then there is a Turing machine that ... I thought your claim was that NO Turing Machine ... other TM is the UTM. ... of these TMs CANNOT be simulated by earthly TMs UNLESS the universe is ...
    (comp.programming)
  • Re: Turing Machines and Physical Computation
    ... >>A Turing machine is a kind of state machine. ... Turing states the ink supply is infinite. ... TMs don't compute with reals, ... the imagination for use by abstract constructs (the meaning of machine ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... >>A Turing machine is a kind of state machine. ... Turing states the ink supply is infinite. ... TMs don't compute with reals, ... the imagination for use by abstract constructs (the meaning of machine ...
    (sci.math)
  • 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)