Here we are in Lesson 7 and have not yet talked about complexity per se. I felt it important to give some background on computability theory not only for the importance of the results but also to introduce the basic concepts of Turing machines, diagonalization and reducibility. We will start complexity in the next lesson.

Let me end the discussion
of computability by one of my favorite theorems. Suppose you wanted to
create the ultimate computer virus that attacked any program and made
it change its behavior. The *recursion theorem* states that no
matter how powerful the virus, some program will remain unscathed. At
first this seems impossible just by considering the function that
simulates a program and then adds one to the answer. But this process
will not affect the machine that never halts.

**Theorem:** Let f be any computable function. There is some Turing
machine M such that

The recursion theorem, sometimes called the fixed-point theorem, has one of the most unintuitive proofs where I cannot explain why it works, only that it does.

**Proof:** Fix a computable function
f. For each machine N, construct a Turing machine <R> that on input x,
simulates N(<N>) to produce the description of a machine and
simulates that machine on x. Let g(<N>) be the function that
outputs <R>. Note that if N(<N>) halts then the programs
described by g(<N>) and N(<N>) accept the same language.

Note that g is computable even if N(<N>) does not halt. Let T(x)
be the machine that computes f(g(x)). We will let M be the machine
described by g(<T>). Then we have that

M accepts input x
if and only if

the machine described by g(<T>) accepts input
x if and only if

the machine described by T(<T>) accepts
input x if and only if

the machine described by f(g(<T>))
accepts input x (since T(x)=f(g(x))) if and only if

the machine
described by f(<M>) accepts input x. QED

As an application, consider the function f(x) that outputs the description of a machine that accepts {x}. By the recursion theorem must be some M such that L(M) accepts exactly <M>. As an experiment, pick your favorite programming language and find a program that outputs its own code. By an argument based on the recursion theorem, such a task is always possible but it is trickier than it seems.

This ends the section on computability theory which is an exciting area of research in and of itself. For further reading the book of Homer and Selman goes into these ideas with some more detail and examples. For more advanced concepts I recommend the books of Soare, Odifreddi or Schoenfield.

## No comments:

## Post a Comment