The halting problem.

Abstract

The primary purpose of this thesis is to show the unsolvability of the Halting problem. To do this, an introduction of the Turing machine and some basic examples using the Turing machine are given. Primitive recursion, Godel numbering, mu-recursion and recursive enumerability are discussed in relation to Church's thesis and solvability using a Turing machine. Using this information, the solvability of the Halting problem is discussed. Finally, an example of an uncomputable function, Rado's function, (the Busy Beaver problem) is presented.