Self modifying code, lambda calculus - Re: ENIAC programming

[Jecel Assumpcao Jr.]

Rich Alderson on Thu, 17 Sep 2015 23:49:59 +0000 wrote:
> From: Paul Koning
> Sent: Thursday, September 17, 2015 9:02 AM
> 
> > In any case, I do not believe the original statement.  First of all, it is
> > well known that no computer can solve "all problems" (see Gödel).  For those
> > it *can* solve, as far as I know, a Turing machine can solve a superset of
> > what a stored program computer can handle,
> 
> All right so far.

Actually, this is a very common misconception. A Turing Machine has no
input and so can do anything a practical batch computer can do and more,
but it can't do some things that real computers with inputs can. Try to
implement Spacewar! on a Turing Machine, for example. Note that this
important detail is actually discussed in the 1936 paper, which few have
read even though it is available freely online.

> > and a Turing machine does NOT have self-modifying code.
> 
> <choke><spit><soda on keyboard>
> 
> Excuse me????
> 
> A Turing machine is the very essence of self-modifying code, by its very
> definition!  You have the infinite memory tape, divided into cells, a reader,
> and a writer.  The reader looks at a cell and performs the action required by
> the symbol read there.  Possible actions include erasing the symbol already
> present and writing a new symbol; once that is done, the reader looks at the
> new symbol and performs the action required by *that* symbol.
> 
> Lather, rinse, repeat.  (Interrupt when out of shampoo.)

The tape is merely the data. The program is in the state table, which
can't be changed. So a given TM is very special purpose and can solve a
single problem. One of the problems that you can solve is the emulation
of another TM: that is the Universal Turing Machine and probably what
you were thinking of. The UTM also has an immutable code, but the
description of the TM it will emulate is stored on tape along with an
image of the emulated TM's own tape. So the UTM can solve different
problems even though its code is fixed. But neither the UTM nor the TMs
it simulates can have self-modifying code.

Just like we can create a TM to emulate other TMs, we can create a TM to
emulate a PDP-8 (for example). Like I mentioned above, real input and
output is a problem but we can certainly emulate them as well, which is
interesting enough. Though the code for this TM is also immutable, the
emulated PDP-8 can change its own code while it is running. This means
that machines capable of self-modifying code are no more powerful than
machines without this capability since the latter can simulate the
former (given enough resources, not considering performance, etc).

This conclusion should have been obvious to anyone thinking about
general purpose computers implemented with microcode in ROM.

-- Jecel