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