1. Church’s thesis and Turing machines
Church s thesis emerged in reaction to the work done by various mathematicians in the 1930 s. In trying to develop a reliable method to solve mathematical problems, individuals such as Church, Gôdel, Kleene and Turing, which respectively proposed the lambda calculus, the Recursive functions, the Formal systems and the Turing machines, proposed decidable methods to compute functions [Immerman 2008, 1]. A function f : X → Y is an abstract relation between two sets X and Y (where X is the domain and Y the image of f) which associates at most one member of Y to a member of X. Put differently, a function f is a set of ordered pairs < xi,yj >, with Xi ∈ X and yj e Y, and can be represented as such: f = {< xi,yj >: xi ∈ X ᐱ yj ∈ Y}. A function can be total, meaning that each member of f s domain will be paired with a member of its image, or it can be partial, meaning that only members of a proper subset of f s domain will be associated with a member of...
