✓ Formal Languages

Computations is about entering a problem to an automated system (the computer), and have the computer produce the correct answer to the problem.

Some Terminology


An example of a problem is integer addition as given by: Given two integers a and b, what is the sum a+b?


An instance of a problem is a concrete specification so that there is a well-defined answer. An example of an instance of addition is:

  • a = 10

  • b = 2


An algorithm for a problem is a procedure that can compute the answer of every instance of the problem, for example a function

int add(int a, int b)

Entscheidungsproblem revisited:

Do all mathematical problems have an algorithm?

To answer the question, we must be able to define what an algorithm is.

String Encoding

For every problem, there exists a well-defined encoding that maps each instance to a finite string consisting of 0 or 1.

Functions over strings


Let \(\mathbf{P}\) be the set of all instances of a problem.

Let \(\mathrm{solutions}(\mathbf{P})\) be the solutions to all the instances of the problem \(P\).

Definition of algorithm

An algorithm is a function \(\mathcal{A}:\mathbf{P}\to\mathrm{solutions}(\mathbf{P})\) that maps an instance \(I\in\mathbf{P}\) to its solution \(\mathcal{A}(I)\).

String encoding

Given a finite alphabet \(\Sigma\), and a problem \(\mathbf{P}\), we need an encoding function and a decoding function.

  • \(\mathbf{Enc} : \mathbf{P}\to\Sigma^*\)

  • \(\mathbf{Dec} : \Sigma^* \to \mathbf{solutions}(\mathbf{P})\)

Algorithm as string processing

An implementation of an algorithm is a string based function \(\mathbf{Imp}\) with the property:

\[\forall I\in\mathbf{P},\ \mathbf{Dec}(\mathbf{Imp}(\mathbf{Enc}(I))) = \mathcal{A}(I)\]

Machinaries for encoding and computation

  • Turing Machine

    • Encodes instances of problems on a tape.

    • Performs stateful memory manipulations.

  • Calculus

    • Encodes instances into mathematical expressions.

    • Performs expression transformations.