Languages and Computation

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?

• Instance of the problem

  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 meaningful problem, there exists a well-defined encoding that maps each instance to a finite string consisting of 0 or 1.

For example, consider the integer addition problem. Can you think of an encoding that maps every instance of the problem to a binary string?

Function over strings

• Some notations:

  1. Let $\mathbf{P}$ be the set of all instances of a problem.
  2. Let $\mathrm{sol}(\mathbf{P})$ be all possible solutions of the instances of $P$.

• Algorithm

  An algorithm is a function $\mathcal{A}: \mathbf{P}\to\mathrm{sol}(P)$

• A language based definition:

  Alan Turing had a brilliant realization that we only need to work with (binary) strings to reason about computation

  box

  For any problem, we have the following functions:

  • $\mathbf{Encode} : \mathbf{P}\to \Sigma^*$
  • $\mathbf{Decode} : \Sigma^* \to \mathrm{sol}(\mathbf{P})$

• Language implementation of algorithms

  A function $f:2^*\to 2^*$ is an implementation of a given algorithm $\mathcal{A}$ if:

  $$\forall x\in\mathbf{P}: \mathbf{Decode}(f(\mathbf{Encode}(x))) = \mathcal{A}(x)$$

What's to come?

split

Turing Machine

• Encodes instances of problems on a tape.
• Performs stateful memory manipulations.

$\lambda$-Calculus

• Encodes instances into mathematical expressions.
• Performs expression transformations.