Introduction

In order to build up to topics, such as zero knowledge we must first cover the foundations. We will cover enough of it to understand how modern cryptography works.

Motivation

We want to capture the notion of what it means for a problem to be computable or solvable.

We first note that any problem that is solvable, must have an algorithm to solve it.

But what exactly is an algorithm? Intuitively, an algorithm is a set of instructions or is a step by step process to solve a problem.

The answer given is not formal because the term algorithm is an intuitive notion, not a formal one. We therefore cannot directly use the term algorithm to reason mathematically in proofs. We need a formal construct that is equivalent to our intuitive notion of an algorithm. This formal notion is called a Turing Machine.

Note: Even our intuitive notion of an algorithm implicitly assumes that an algorithm needs to stop. It stops exactly when the problem is solved.

Purpose of Turing Machine

The purpose of a Turing Machine as mentioned above, is to define a mathematical construction that is equivalent to our intuitive notion of what we call an algorithm

Turing’s famous paper defines an abstract machine, to which we now call a Turing machine. There were many others who also gave differing formal constructs, it was later proved that they were all equivalent in power; ie the set of problems that each formal construction could solve was exactly the same. The most notable example being that lambda calculus was equivalent to Turing machines; therefore, the set of problems that a Turing machine could solve was equal to the set of problems solvable by lambda calculus.

How do you prove that an intuitive notion such as an algorithm is equal to a formal construct such as a Turing machine?

Intuitively, if I defined two objects formally in maths, I could use reason and logic to prove that they were equal. However, since our notion of an algorithm is informal. No proof can be supplied. We instead have a thesis, the thesis that Turing stated is as follows:

Every problem that can be solved with an algorithm, can be implemented on a Turing Machine

It’s inconsequential but important to stress that this is a thesis and has not been proven or dis-proven. Most people take this thesis as their world view and believe that it will never be proven.There have been proofs brought forward to prove or disprove, but as of writing, none have withstood academy scrutiny. We will assume this thesis to be true, and use Turing machine’s as our model of computation.

A model of computation is a general method or construct that allows us to distinguish between problems that have algorithms and problems which do not.