# ✓ 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¶

Problem

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

Instances

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

## Algorithm¶

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¶

### Notation¶

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.