Dr A. Alvi Ch.
6 Recursion
Ch6 Advanced Topics in Computability Theory
6.1 Recursion Theorem
In this chapter we discuss three deeper aspects of computability theory:
o Recursion theorem
o Turing reducibility
o Descriptive complexity
The topic covered in each section is mainly independent of the others. Part Three of
the textbook doesn't depend on any material from this chapter.
Recursion Theorem:
o Has important applications in logic, self-reproducing systems, and even
computer viruses.
o To introduce the Recursion Theorem, we start with a paradox, stated in
these 3 statements:
1. Living things are machines.
2. Living things can self-reproduce.
3. Machines cannot self-reproduce.
o Statement 1 is now known from modern biology. Organisms are believed
to operate in a mechanistic way (do they?).
o Reproduction is a characteristic of all living things.
o For statement 3, consider the example of a car factory. Our claim is that
the design of the factory is more complex than the design of the cars it
makes, because the car’s design is contained within the factory’s design.
Hence, a machine A that constructs a machine B, must be more
complex than B.
But a machine cannot be more complex than itself.
Hence, a machine cannot self-reproduce.
Remember the Terminator movie series?
How to resolve the paradox that says that machines reproduce and then says that they
can’t?
Machines can actually replicate. Statement 3 is false. Recursion Theorem shows how.
-1-
Dr A. Alvi Ch.6 Recursion
-2-
Dr A. Alvi Ch.6 Recursion
Now to get back to making SELF.
-3-
Dr A. Alvi Ch.6 Recursion
-4-
Dr A. Alvi Ch.6 Recursion
Quine Programs are those in any programming language that reproduce their source
code as their only output. Try writing one in the language you fancy. It’s possible!
http://www.nyx.net/~gthompso/quine.htm
http://en.wikipedia.org/wiki/Quine_(computing)
The recursion theorem provides the ability to implement the self-referential this into
any programming language.
We now state the recursion theorem. It extends the technique we used in constructing
SELF so that a program can obtain its own description and then go on to compute
with it, instead of merely printing it out.
-5-
Dr A. Alvi Ch.6 Recursion
To make a Turing machine R that can obtain its own description and then compute
with it, we need only make a machine—called T in the statement—that receives the
description of the machine R as an extra input.
Then the recursion theorem produces a new machine R, which operates exactly as T
does but with R's description filled in automatically.
Now T will do the desired computation on w. Overall result is that R has obtained its
own description and then done some computation on it with w.
-6-
Dr A. Alvi Ch.6 Recursion
Recursion theorem states that Turing machines can obtain their own description and
then go on to compute with it. At first glance, this may seem useful for only
frivolous tasks as making a machine that prints a copy of itself. But not so.
Having the ability to self-replicate has important applications in algorithmic theory.
E.g. it can be used in designing algorithms for Turing machines in the following way.
While designing a TM M, you can include following statement in M’s algorithm:
o “Obtain own description <M>”
Upon having obtained its own description, M can then go on to use it as it would use
any other computed value.
For example,
o M might simply print out <M> as happens in the TM SELF
o Or it might count the number of states in <M>
o Or possibly even simulate <M>
To illustrate this method, we use the recursion theorem to describe the machine SELF.
-7-
Dr A. Alvi Ch.6 Recursion
We’ll consider theorems that use recursion theorem in their proofs.
We’ll now again prove Theorem 4.11, the Acceptane Problem, in an easier way with
the help of the recursion theorem. (Recall that previously we used Cantor’s
diagonalisation.)
-8-
Dr A. Alvi Ch.6 Recursion
Fixed Point Theorem
Final application example of recursion theorem is a type of fixed point theorem.
A fixed point of a function is a value that is not changed by the application of the
function i.e. f (x) = x.
E.g. if we consider the squaring function, (1) 2 =1. Therefore 1 is the fixed point for the
squaring function.
-9-
