Introduction

Haskell is a lazy, strongly typed, purely functional programming language.

• Purely functional - A program consists of functions and recursion. Functions are pure, meaning the output of a function depends solely on it's inputs and they have no side effects.

• Lazy - Expressions in Haskell are not evaluated until they need to be.

• Strongly typed - Types are checked before the program runs.

Church-Turing Thesis

Gödel introduced the model of recursive functions in 1932. Recursive functions are those that can refer to themselves. Then in 1936 Church introduced lambda calculus which is a way of describing algorithms. Church proved recursive functions and lambda calculus had the same expressive power, meaning any program written in one can be expressed in the other.

In the same year Turing invented the concept of the Turing machine. A Turing machine has a hardcoded procedure and an infinite tape of memory. The machine moves up and down the tape reading and writing values.

The Church-Turing thesis states that any algorithm that can be implemented by a Turing machine can also be expressed in lambda calculus and any lambda calculus algorithm can be implemented by a Turing machine. This means all three models have the same expressive power and this is referred to as Turing-completeness.