Key distinction: Decision problems (yes/no) vs. Computation problems (function evaluation).
Decision Problems
Definition: Let \(A \subseteq E\), where \(E\) is a set of finitely describable objects.
Decision method: A procedure by which, given \(a \in E\), we can decide in a finite number of steps whether \(a \in A\) or not.
Solvable problem: The decision problem for \(A\) in \(E\) is solvable if such a decision method exists.
Example: Tautology problem for propositional logic (checking if a formula \(\phi\) is a tautology via truth tables).
Computation Problems
Definition: Let \(F: A \to B\) be a mapping, where elements of \(A, B\) are finitely describable objects.
Computation method: A procedure by which, given \(a \in A\), we can obtain \(F(a)\) in a finite number of steps.
Calculable function:\(F\) is calculable if such a computation method exists.
Example: Computing the greatest common divisor \(\gcd(a, b)\) for \(a, b \in \mathbb{N}\).
Representing Functions for Predicates
Let \(P(a_1, \ldots, a_n)\) be an \(n\)-ary number-theoretic predicate.
The representing function\(f\) of \(P\) is defined as:
$$ f(a_1, \ldots, a_n) = \begin{cases} 0 & \text{if } P(a_1, \ldots, a_n) \text{ is true} \ 1 & \text{if } P(a_1, \ldots, a_n) \text{ is false} \end{cases} $$
Key insight: A decision procedure can be handled as a computation procedure by using '0' for 'yes' and '1' for 'no'.
Effective Procedures (Mechanical Computation)
A computation method must be:
Mechanical/Algorthmic: Can be carried out by an ideal machine \(M\) (no resource limits, no breakdowns).
Uniform: The same machine \(M\) must be used for all arguments \(a\) (the machine may not differ for different inputs).
Process: Input \(a\) is placed on the device \(\to\) machine runs \(\to\) produces \(F(a)\) after finitely many steps.
Solvability and Unsolvability Examples
Example: Solvable Diophantine Equation
Problem: Is \(15x + 9y + 12 = 0\) solvable for \(x, y \in \mathbb{Z}\)?
Theorem:\(ax + by + c = 0\) is solvable in \(\mathbb{Z} \iff \gcd(a, b) \mid c\).
Calculation: Using Euclid's algorithm:
$$ 15 = 1 \cdot 9 + 6 $$
$$ 9 = 1 \cdot 6 + 3 $$
$$ 6 = 2 \cdot 3 + 0 $$
So, \(\gcd(15, 9) = 3\). Since \(3 \mid 12\), the equation is solvable (e.g., \(x = 4, y = -8\)).
Example: Unsolvable (Hilbert's 10th Problem)
Instance: A polynomial equation \(p(x_1, \ldots, x_n) = 0\) with integer coefficients.
Question: Are there integer solutions \(x_1, \ldots, x_n \in \mathbb{Z}\)?
Theorem (Matijasevič, 1970): Hilbert's 10th Problem is unsolvable (no general algorithm exists).
Non-Effective Methods (Not Calculable)
Methods involving chance (e.g., tossing a coin).
Methods involving magic (e.g., asking a fortune teller).
Methods requiring unformalized, unmechanised human insight.
Historical Timeline (Key Milestones)
1900: Hilbert's 23 Problems in mathematics.
1928: Hilbert/Ackermann formulate the Entscheidungsproblem (decision problem for predicate calculus).
1930: Gödel proves the completeness theorem of predicate calculus.
1931: Gödel's incompleteness theorems for first-order arithmetic.
1932: Church introduces the \(\lambda\)-calculus.
1933/34: Herbrand/Gödel define general recursive functions.
1936: Church (with Kleene) shows \(\lambda\)-definable \(\sim\) general recursive. Church proves the Entscheidungsproblem is unsolvable. Turing gives a convincing analysis of a "human computer" leading to the Turing machine.
1937: Post introduces his machine model.
Classification of Models of Computation (MoCs)
Classical Models
Machine models: Turing machines, Post machines, Register machines.
Inspired by physics/biology: Quantum computing, bio-computing, reversible computing.
Other: Fractran, term rewrite systems, interaction nets, cellular automata, neural networks, process algebras, \(\pi\)-calculus, abstract state machines.
Relevance of Models of Computation (Calculator Case Study)
Constructive Real Numbers
A real number \(x \in \mathbb{R}\) is constructive if there exists a program \(P_x\) such that for every bound \(0 < \delta \in \mathbb{Q}\), \(P_x(\delta)\) returns a rational approximation with:
$$ |x - P_x(\delta)| < \delta $$
Undecidability in Practice
Problem: How to recognize if two constructive reals \(x\) and \(y\) are the same (\(x = y\))?
Answer: This problem is undecidable (no program \(Compare\) can decide equality for arbitrary \(P_x, P_y\)).
Consequence:\(x - y = 0\) cannot always be decided.
Böhm's Full Precision Calculator
Uses products of:
Full-precision rational arithmetic.
Symbolic representations of constants (e.g., \(\pi, e, \sqrt{x}, \ln(x), \sin(\pi x)\) for \(x \in \mathbb{Q}\)).
Constructive real numbers.
Key fact: Equality of products with only symbolic representations can be decided. Equality of products containing at least one constructive real number cannot be decided.
Fields Where MoCs Are Important
Complexity Theory: Recognizing decidable problems and classifying their complexity.
Recursion Theory: Theory of computability for sets and functions on \(\mathbb{N}\) (including degrees of unsolvability).
Logic and Philosophy: Studying (un)decidability of logical theories.
Rewriting: Operational and denotational aspects of \(\lambda\)-calculus, term rewriting, interaction nets.
Neuro-psychology & Cognitive Modelling: Formal platforms for studying human cognition.
Artificial Intelligence: Modeling the human mind, understanding inherent problem complexity.
Linguistics: Formal calculi for discovering language structures (Chomsky hierarchy).
Discussion Questions from Lecture
Suppose \(P(a, b)\) is a calculable predicate. Why does \((\exists x) P(a, x)\)not have to be calculable? (Hint: infinite search over \(x\)).
Let \(f: \mathbb{N} \to \mathbb{N}\) be defined by a finite expression. Is \(f\) always calculable? (Requires careful definition of the expression).
Can computation problems for mappings \(F: \mathbb{N}^n \to \mathbb{N}^m\) always be represented by decision problems? (Hint: consider encoding the graph of \(F\)).