Computability and Equivalent Computational Models

Historical Context and Challenges in Mathematics

• The Late 18th Century and Early 20th Century: During this period, several developments created turmoil in the field of mathematics, specifically regarding non-Euclidean geometries, Cantor’s set theory and concepts of infinity, and fundamental problems in logic.
• Russell’s Paradox (1901): Bertrand Russell discovered a fundamental paradox in the naive set theory established by Georg Cantor.
  • Definition of the paradox: Let $S$ be the set of all sets that are not members of themselves.
  • Formal definition: $S = \{x \mid x \notin x\}$
  • The contradiction: If $S \in S$, then by definition $S \notin S$. Conversely, if $S \notin S$, then by definition $S \in S$. This is expressed as $S \in S \iff S \notin S$.
• The Quest for Foundations: Following these crises, David Hilbert sought to establish a solid foundation for mathematics, famously stating, "We must know, we can know, we shall know!"

Hilbert’s Program and the Quest for Formalization

• Formalization of Mathematics: Hilbert proposed that all mathematical statements be written in a precise formal language. These statements would be manipulated according to well-defined rules, starting from a set of axioms and using defined rules for logical inference and deduction.
• Proof Definition: A proposition is proven true if it can be derived from the axioms through a finite sequence of logical steps.
• Completeness: A primary goal was to ensure that any proposition expressible within the system could be proven either true or false.
• Decidability: This required a mechanical procedure, or an "algorithm," for deciding the truth or falsity of any given mathematical statement through mechanically verifiable proofs.

Gödel’s Incompleteness and its Impact

• Gödel’s Incompleteness Theorem (1931): Kurt Gödel proved that in any sufficiently powerful formal system, there are theorems that are true but have no proof within that system.
• Failure of Hilbert’s Goals: This theorem demonstrated that a single formal system comprising all of mathematics is impossible.
• The Follow-up Quest: If all of mathematics could not be formalized, researchers shifted focus to whether there exists a machine that can provide mechanically verifiable proofs for statements that are specifically provable. This necessitated a precise definition of "algorithm" or "effective calculability."

Defining Computability

• Concept of Computability: A thing is considered computable if there is some computation that can compute it. This is synonymous with being described by an algorithm or recipe.
• Computation as Execution: Computation is the execution of an algorithm. Therefore, computability involves both a formal process (the execution) and a formal description (the algorithm).
• Formalization Examples:
  • Derivation processes associated with grammars.
  • Evaluation processes associated with functions.
  • State transition processes associated with machines.
  • Execution processes associated with programs and programming languages.

Theoretical Models of Computation (1934–1937)

• Key Figures: The foundational mathematical machines were developed by Emil Post, Stephen Kleene, Alonzo Church, and Alan Turing.
• Power and Comparison:
  • Some models are more powerful than others. For example, Turing machines (TMs) are more powerful than pushdown automata.
  • Some models have identical power. For instance, non-deterministic finite automata (NFA) have the same power as deterministic finite automata (DFA).
• The Most Powerful Model: There are several equivalent "most powerful" models. Any model more powerful than a Turing machine has never been invented.

The Church-Turing Thesis

• Definition: The Church-Turing Thesis states that anything that is intuitively computable can be computed by a Turing machine.
• Theorem vs. Thesis: It is categorized as a "thesis" rather than a "theorem" because it bridges an informal, intuitive idea of computability with the formal, precise definition of a Turing machine. It is impossible to formally prove an equivalence between an informal idea and a formal model.
• Equivalence to TMs: Despite being different in data processing or structure, many alternative formalizations are equivalent to Turing machines in the class of problems they can solve.

Equivalent Computational Models

• Alonzo Church (1930s): Created the $\lambda$-calculus, a method for defining functions.
• Alan Turing: Created a theoretical machine model for performing calculations from inputs.
• Partial Recursive Functions: A class of functions defined by Alonzo Church, Stephen Kleene, and J.B. Rosser whose values can be calculated via recursion.
• Computational Assumption: Comparisons between models assume an unlimited amount of available memory, allowing for the representation of any natural number or finite string.
• Other Equivalent Systems:
  • Markov Algorithms: Introduced by Andrey Markov in 1954.
  • Simple Programming Language: Introduced by Shepherdson and Sturgis in 1963.
  • Post Algorithms/Systems: Introduced by Emil Post in 1943.
  • Game of Life: Introduced by John Conway in 1970.

Lambda-Calculus ($\lambda$-calculus)

• Origin: Introduced by Alonzo Church in the 1930s during investigations into the foundations of mathematics.
• Evolution: The original system was found to be logically inconsistent. Church subsequently introduced two weaker systems: untyped lambda calculus and simply typed lambda calculus.
• Legacy: These systems were instrumental in the development of programming language theory. Untyped lambda calculus served as the original inspiration for functional programming, specifically Lisp.

Simple Programming Language (Shepherdson & Sturgis, 1963)

• Power: This little imperative language is equivalent in power to a Turing machine. Any problem a TM can solve, a simple program can solve, and vice versa.
• Description and Rules:
  1. Variables: Variables take values in the set $\mathbb{N}$ of natural numbers.
  2. While Statement: The format is while X ≠ 0 do statement od.
  3. Assignment Statements: Only three forms are permitted:
     • $X := 0$
     • $X := \text{succ}(Y)$ (Successor)
     • $X := \text{pred}(Y)$ (Predecessor)
  4. Composition: A statement is either a while statement, an assignment, or a sequence of statements separated by semicolons.
  5. Program: A simple program is defined as a statement.
• Operational Nuance: To ensure all values remain in $\mathbb{N}$, the predecessor of zero is defined as zero: $\text{pred}(0) = 0$.
• Macro Examples:
  • Assigning a variable to another ($X := Y$):X := succ(Y); X := pred(X).
  • Assigning a constant ($X := 3$):X := 0; X := succ(X); X := succ(X); X := succ(X).

Markov Algorithms (1954)

• Description: A string processing model equivalent to Turing machines.
• Structure: A Markov algorithm over an alphabet $\Sigma$ consists of a finite, ordered sequence of productions in the form $x \rightarrow y$, where $x, y \in \Sigma^*$ (strings over the alphabet).
• Halt Label: Productions may optionally be labeled with the word "halt."
• Rule of Application: If a pattern $x$ occurs as a substring in the input string $w$, the leftmost occurrence of $x$ is replaced by its corresponding $y$.
• Execution Steps:
  1. Scan productions from top to bottom to check for patterns in the input string.
  2. If no patterns match, the algorithm stops.
  3. If a match is found, apply the first matching production to the leftmost occurrence in the input string.
  4. If the applied production was a "terminating" (halt) production, stop. Otherwise, go back to step 1.
• Initial Step Assumption: For any string $w$, $w = \Lambda w$ where $\Lambda$ is the empty string. Therefore, a production like $\Lambda \rightarrow y$ would transform $w$ to $yw$.
• Examples:
  • Algorithm with productions: 1. aba → b, 2. ba → b, 3. b → Λ.
  • Input $w = aabaaa$ trace:         $aabaaa \rightarrow abaa$ (via production 1)         $abaa \rightarrow ba$ (via production 1)         $ba \rightarrow b$ (via production 2)         $b \rightarrow \Lambda$ (via production 3)
  • The algorithm returns $\Lambda$ for strings $a^i b^j$ where $i \le j$.
  • The algorithm returns $a^{i-j}$ for strings $a^i b^j$ where $i > j$.
  • To delete all occurrences of the letter 'a' from a string over $\Sigma = \{a, b, c\}$, use the production: $a \rightarrow \Lambda$.

Post Algorithms (1943)

• Description: A string processing model created by Emil Post. Like Markov algorithms, they are equivalent to Turing machines.
• Structure: A set of productions to transform strings. Productions take the form $s \rightarrow t$, where the strings $s$ and $t$ consist of symbols from an alphabet $\Sigma$ and variables.
• Variable Constraint: If a variable $X$ appears in the replacement string $t$, it must have appeared in the original pattern $s$.
• Execution Steps:
  1. Find a production where the input string $w$ matches pattern $x$.
  2. If a match is found, construct a new string based on the replacement $y$. If no match exists, halt.
  3. If the production is labeled "halt," the algorithm stops.
  4. Otherwise, return to step 1.
• Variables and Logic: Variables can match the empty string $\Lambda$. Post algorithms can be either deterministic or nondeterministic.
• Example:
  • Production: $aXb \rightarrow X$ over $\Sigma = \{a, b\}$.
  • Input string aab matches $aXb$ with $X = a$. Transformation results in a. Since a no longer matches the pattern $aXb$, it halts.
  • Input string ab matches with $X = \Lambda$, transforming to $\Lambda$.
  • Effect: Transforms any string $a^i b$ into $a^{i-1}$ for $i > 0$.