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

## 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.