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
