CSci 301 Lecture Notes

Week Nine, Tuesday: The Recursion Theorem

That machines cannot self-reproduce is a false paradox. Machines can reproduce. The tape that gives the Turing machine its power is the key.

A computer's RAM corresponds to a Turing machine's tape. Suppose you wanted to make a program that among other things, could write a new copy of itself. When the operating system launches a program, it reads it off the disk and writes it into memory. A pointer to the memory location can be passed to the program as it is launched. Then the program can reference itself in memory and easily create as many new copies as it wants. It can write copies to memory or to disk.

Self Reference

SELF is a turing machine that prints its own description.

Terminology for the Recursion Theorem

Applications

Artificial life, computer viruses, and reproducing robots with intelligent design improvement.

Email: Richard dot J dot Wagner at gmail dot com