Computability Theory Foundations

Building on the foundation of Turing Machines, this module explores the mathematical theory of computation—what can and cannot be computed in principle. We extend the concepts of computability, examine the hierarchy of language classes, and delve into the mathematical foundations that underpin the limits of computation.

While Turing Machines establish the boundary of what can be computed algorithmically, computability theory provides a rich framework for understanding the various degrees of computability and the profound implications of these limits for mathematics, computer science, and beyond.

This exploration connects the concrete models of computation to abstract mathematical concepts, revealing deep insights about the nature of algorithms, the structure of computational problems, and the fundamental limitations that no computing device—regardless of its power—can overcome.

Advanced Turing Machine Concepts

In the Turing Machines section, we introduced the basic model of Turing Machines and explored their fundamental properties. Here, we expand on these concepts and examine more sophisticated variations and their implications for computability theory.

Advanced Configurations and Multi-tape Equivalence

Recall that a configuration of a Turing Machine captures its complete state at any moment: the current state, the contents of the tape, and the position of the head. We can formalize this as a triple (q, w, i), where q is the current state, w is the tape content, and i is the head position.

When working with more complex computations, we often need a more efficient way to represent the machine's operation. Multi-tape Turing Machines provide this efficiency by allowing the machine to have multiple tapes, each with its own read/write head.

Definition: Multi-tape Turing Machine

A k-tape Turing Machine is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject) where:

Q is a finite set of states
Σ is a finite input alphabet not containing the blank symbol _
Γ is a finite tape alphabet, where _ ∈ Γ and Σ ⊂ Γ
δ: Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ is the transition function, where L indicates left movement, R indicates right movement, and S indicates staying in place
q₀ ∈ Q is the start state
q_accept ∈ Q is the accept state
q_reject ∈ Q is the reject state, where q_reject ≠ q_accept

The machine operates by reading the symbols under all k tape heads simultaneously, then writing new symbols to all tapes, moving each head independently (left, right, or stay), and transitioning to a new state, all according to the transition function δ.

Theorem: Equivalence of Multi-tape and Single-tape Turing Machines

For any k-tape Turing Machine M, there exists a single-tape Turing Machine M' such that L(M) = L(M'). Furthermore, if M runs in time T(n), then M' runs in time O(T(n)²).

Variants of Turing Machines

Beyond multi-tape Turing Machines, several other variants extend the basic model in different ways. These variants often make the model more intuitive for certain applications or provide efficiency gains, though they remain equivalent in terms of computational power.

Definition: Nondeterministic Turing Machine

A Nondeterministic Turing Machine (NTM) is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject) where the transition function δ maps Q × Γ to the power set of Q × Γ × {L, R}:

δ: Q × Γ → P(Q × Γ × {L, R})

This means that for each state and input symbol, the machine has multiple possible next moves. The machine accepts an input if and only if at least one computation path leads to the accept state.

Definition: Alternating Turing Machine

An Alternating Turing Machine (ATM) is an extension of the nondeterministic Turing Machine where states are divided into two types: existential states and universal states.

For an existential state, the machine accepts if at least one of the possible next moves leads to acceptance, similar to an NTM. For a universal state, the machine accepts if all possible next moves lead to acceptance.

Definition: Probabilistic Turing Machine

A Probabilistic Turing Machine (PTM) is a nondeterministic Turing Machine where each transition has an associated probability. The transition function δ maps each pair (q, a) to a probability distribution over possible next configurations:

δ: Q × Γ → Dist(Q × Γ × {L, R})

The probability that the machine accepts an input is the sum of the probabilities of all computation paths that lead to the accept state.

Theorem: Equivalence of Turing Machine Variants

The following models of computation are all equivalent in terms of the languages they can recognize: single-tape Turing Machines, multi-tape Turing Machines, nondeterministic Turing Machines, and probabilistic Turing Machines with bounded error. That is, for any language L, if L is recognized by any of these variants, then L is also recognized by a standard single-tape deterministic Turing Machine.

Universal Turing Machines in Depth

The Universal Turing Machine (UTM) was briefly introduced in the Turing Machines module. Here, we examine it more deeply and explore its profound implications for computability theory and computer science as a whole.

Definition: Universal Turing Machine

A Universal Turing Machine U is a Turing Machine that can simulate any other Turing Machine M on any input w. Given an encoding ⟨M, w⟩ of a Turing Machine M and an input w, U accepts ⟨M, w⟩ if and only if M accepts w.

Formally, L(U) = {⟨M, w⟩ | M is a TM and w ∈ L(M)}.

Simulation Details

How does a Universal Turing Machine perform its simulation? The key insight is that a Turing Machine can be encoded as a string, which can then be processed by another Turing Machine. This encoding typically includes:

The states Q
The alphabets Σ and Γ
The transition function δ
The special states q₀, q_accept, and q_reject

The Universal Turing Machine operates by:

Parsing the encoded Turing Machine M and input w
Creating an internal representation of M's initial configuration on input w
Iteratively applying M's transition function to update the configuration
Accepting if M enters its accept state, rejecting if M enters its reject state

This process is more efficient on a multi-tape machine, where separate tapes can be used for the encoded machine, the current state, the simulated tape, and working memory.

Implications of Universal Turing Machines

The existence of Universal Turing Machines has profound implications:

Self-reference: Computations can refer to and manipulate other computations, including potentially themselves, enabling meta-programming and reflection.
Stored-program concept: Programs can be treated as data, the foundation of modern computing where software is stored and manipulated just like any other data.
General-purpose computing: A single machine can perform any computable task given the right program, eliminating the need for specialized hardware for each specific computation.
Computability results: The existence of UTMs enables many foundational results in computability theory, including the unsolvability of the Halting Problem.

Language Classes Extended

Building on the language classification from the Turing Machines section, we now explore the hierarchy of language classes in more detail, examining the relationships between them and their properties.

Decidable, Recognizable, and Beyond

Let's begin by recalling the fundamental distinction between decidable and recognizable languages, and then extend this framework to include co-recognizable languages and beyond.

Definition: Decidable Languages (Recursive Languages)

A language L is decidable (or recursive) if there exists a Turing Machine M such that:

For all w ∈ L, M accepts w
For all w ∉ L, M rejects w
For all inputs w, M halts (either accepting or rejecting)

Definition: Recognizable Languages (Recursively Enumerable Languages)

A language L is recognizable (or recursively enumerable, RE) if there exists a Turing Machine M such that:

For all w ∈ L, M accepts w
For all w ∉ L, M either rejects w or runs forever (doesn't halt)

Definition: Co-Recognizable Languages (co-RE Languages)

A language L is co-recognizable (or co-RE) if its complement L̄ = Σ* - L is recognizable. Equivalently, there exists a Turing Machine M such that:

For all w ∉ L, M accepts w
For all w ∈ L, M either rejects w or runs forever

Theorem: Relationship Between Decidable, RE, and co-RE Languages

Let L be a language. The following are equivalent:

L is decidable
L is recognizable and co-recognizable
Both L and its complement L̄ are recognizable

Proof: Proof of the Relationship Between Decidable, RE, and co-RE Languages

Let's prove that a language L is decidable if and only if both L and its complement L̄ are recognizable.

(⇒) If L is decidable, then there exists a Turing Machine M that decides L. This machine halts on all inputs, accepting strings in L and rejecting strings in L̄. Therefore, M recognizes L. We can construct a Turing Machine M' that recognizes L̄by swapping the accept and reject states of M. Thus, both L and L̄ are recognizable.

(⇐) Suppose both L and L̄ are recognizable. Let M₁ recognize L and M₂ recognize L̄. We can construct a Turing Machine M that decides L as follows:

Run M₁ and M₂ in parallel on the input w by simulating one step of each machine alternately
If M₁ accepts, then accept
If M₂ accepts, then reject

Since w is either in L or in L̄, one of the machines M₁ or M₂ must eventually accept, ensuring that M always halts. Therefore, M decides L, making L decidable.

Examples of Languages in Different Classes

To better understand the hierarchy of language classes, let's examine specific examples of languages in each class.

Decidable Languages

Regular languages: All regular languages, such as {aⁿbⁿ | n ≥ 0}, are decidable, as they can be recognized by finite automata.
Context-free languages: All context-free languages, such as {aⁿbⁿ | n ≥ 0}, are decidable, as they can be recognized by pushdown automata.
The language of palindromes: {w | w = w^R}, where w^R is the reverse of w, is decidable. A Turing Machine can check if a string reads the same forward and backward.
The language of prime numbers: {1ⁿ | n is a prime number} is decidable. A Turing Machine can check if a number is prime using a primality testing algorithm.

Recognizable but Not Decidable Languages

These languages are recognizable (RE) but not decidable, meaning they are not co-recognizable (not co-RE).

The Halting Problem language: H = {⟨M, w⟩ | M is a TM and M halts on input w} is recognizable but not decidable. A Turing Machine can simulate M on w and accept if M halts, but cannot determine in general if M will run forever.
The acceptance problem: Aₜₘ = {⟨M, w⟩ | M is a TM and M accepts w} is recognizable but not decidable. A Universal Turing Machine can simulate M on w and accept if M accepts, but cannot determine if M will reject or run forever.
The language of Turing Machines that halt on the empty string: {⟨M⟩ | M is a TM and M halts on ε}is recognizable but not decidable.

Co-Recognizable but Not Recognizable Languages

These languages are co-recognizable (co-RE) but not recognizable (not RE), meaning their complements are recognizable but not decidable.

The complement of the Halting Problem: H̄ = {⟨M, w⟩ | M is a TM and M does not halt on w} is co-recognizable but not recognizable.
The language of Turing Machines that do not accept any input: {⟨M⟩ | M is a TM and L(M) = ∅} is co-recognizable but not recognizable.
The language of Turing Machines that accept all inputs: {⟨M⟩ | M is a TM and L(M) = Σ*} is co-recognizable but not recognizable.

Non-Recognizable and Non-Co-Recognizable Languages

These languages are neither recognizable nor co-recognizable, putting them beyond the reach of Turing Machines altogether.

The language of Turing Machines that halt on exactly the inputs in some undecidable but recognizable language: {⟨M⟩ | M is a TM and L(M) = L}, where L is a specific undecidable but recognizable language, is neither recognizable nor co-recognizable.
The language of all valid encodings of Turing Machines that compute busy beaver functions: This language is neither recognizable nor co-recognizable.

Degrees of Undecidability

Not all undecidable problems are equally "hard." The concept of reducibility allows us to compare the relative difficulty of undecidable problems, leading to a rich structure known as the degrees of undecidability.

Definition: Turing Reducibility

A language A is Turing-reducible to a language B, denoted A ≤_T B, if there exists an oracle Turing Machine M with an oracle for B such that M decides A.

An oracle Turing Machine is a Turing Machine with an additional oracle tape and special states that allow it to query the oracle. When the machine enters a query state, it instantaneously receives an answer whether the string currently on the oracle tape is in the oracle language B.

Definition: Turing Degree

Two languages A and B are Turing-equivalent if A ≤_T B and B ≤_T A. This equivalence relation partitions the set of all languages into equivalence classes called Turing degrees or degrees of unsolvability.

A Turing degree represents a level of computational complexity that is invariant under Turing reducibility.

Important Turing Degrees

0 (Zero degree): Contains all decidable languages. This is the lowest Turing degree.
0' (Zero jump): Contains the Halting Problem and all problems Turing-equivalent to it, such as the acceptance problem A_TM. This is the first level of undecidability.
0'' (Double jump): Contains problems that are undecidable even with an oracle for the Halting Problem, such as determining if a Turing Machine with a Halting Problem oracle halts on all inputs.
Higher jumps: The hierarchy continues with 0''', 0'''', and so on, each level representing problems undecidable even with access to all lower levels.

This hierarchy, known as the arithmetical hierarchy, provides a way to classify undecidable problems based on their relative hardness. It demonstrates that undecidability is not a binary property but exists on a spectrum.

Mathematical Foundations

Computability theory is deeply rooted in mathematical concepts, particularly set theory and the theory of cardinality. These concepts provide crucial insights into the nature of computation and its fundamental limits.

Extended Cardinality Arguments

Cardinality—the size of sets—plays a crucial role in establishing fundamental limits of computation. We'll explore how different infinities relate to computation and what they tell us about the landscape of computational problems.

Countable and Uncountable Sets

Definition: Countable and Uncountable Sets

A set S is countable if there exists a bijection between S and the natural numbers ℕ or a subset of ℕ. A set is uncountable if it is not countable.

A countable set can be either finite or countably infinite. A countably infinite set has the same cardinality as ℕ, denoted by ℵ₀ (aleph-null).

Cardinality of Important Sets

Let's examine the cardinality of several sets that are relevant to computability theory:

The set of natural numbers (ℕ): Countably infinite, with cardinality ℵ₀.
The set of integers (ℤ): Countably infinite, with cardinality ℵ₀. We can list them as 0, 1, -1, 2, -2, 3, -3, ...
The set of rational numbers (ℚ): Countably infinite, with cardinality ℵ₀. Despite appearing "denser" than integers, rationals can be arranged in a sequence using a diagonal enumeration.
The set of real numbers (ℝ): Uncountable, with cardinality 2^ℵ₀ (also called c, the cardinality of the continuum). Cantor's diagonal argument proves that reals cannot be arranged in a sequence.
The set of all finite strings over a finite alphabet (Σ*): Countably infinite, with cardinality ℵ₀. We can list them by length: first all strings of length 0, then length 1, then length 2, and so on.
The set of all Turing Machines: Countably infinite, with cardinality ℵ₀. Since each Turing Machine can be encoded as a finite string, and there are countably many finite strings, there are countably many Turing Machines.
The set of all languages over a finite alphabet (P(Σ*)): Uncountable, with cardinality 2^ℵ₀. A language is a subset of Σ*, and the power set of a countably infinite set is uncountable.

Cardinality and Computability

Theorem: Uncountability of Undecidable Languages

The set of all languages over an alphabet Σ is uncountable, while the set of decidable languages is countable. Therefore, there exist uncountably many undecidable languages.

Proof: Proof of the Uncountability of Undecidable Languages

Let Σ be a finite alphabet. The set of all languages over Σ is the power set P(Σ*), which has cardinality 2^ℵ₀ (uncountable).

The set of all Turing Machines is countable because each Turing Machine can be encoded as a finite string, and there are countably many finite strings.

Each decidable language is decided by at least one Turing Machine. Since there are only countably many Turing Machines, there can be at most countably many decidable languages.

Therefore, the set of undecidable languages (the complement of the set of decidable languages in P(Σ*)) must be uncountable.

Effective Enumeration Techniques

Enumeration is a powerful technique in computability theory that allows us to systematically list objects such as Turing Machines, recursive functions, or recognizable languages.

Definition: Effective Enumeration

An effective enumeration of a set S is a surjective computable function f: ℕ → S. In other words, it is a computable listing of the elements of S such that every element of Sappears at least once in the listing.

Enumeration of Turing Machines

We can effectively enumerate all Turing Machines by encoding them as strings and then enumerating these strings. One approach is to enumerate all strings over a suitable alphabet, filter out invalid encodings, and interpret the valid ones as Turing Machines.

This enumeration gives us a way to refer to the i-th Turing Machine, which we can denote as Mᵢ. We can then study the language recognized by Mᵢ, denoted L(Mᵢ).

Enumeration of Recognizable Languages

Theorem: Enumeration Theorem for Recognizable Languages

The set of all recognizable languages is effectively enumerable. That is, there exists a computable functionf: ℕ → P(Σ*) such that {f(i) | i ∈ ℕ} is exactly the set of all recognizable languages.

The Recursion Theorem

The Recursion Theorem is a powerful result that allows Turing Machines to access their own descriptions, enabling self-reference in computations.

Theorem: Kleene's Recursion Theorem

Let f: Σ* → Σ* be a computable function. Then there exists a string w such that f(w) and w encode the same Turing Machine.

Equivalently, for any computable function g that transforms Turing Machine descriptions, there exists a Turing Machine M that behaves exactly like g(⟨M⟩), where ⟨M⟩ is the description of M.

Computable Functions vs. Computable Sets

Computability theory can be approached from two different but equivalent perspectives: through functions or through sets/languages. Understanding the relationship between these perspectives provides additional insight into the nature of computation.

Definition: Computable Function

A function f: Σ* → Σ* is computable if there exists a Turing Machine M that, on input w, halts with f(w) on its tape.

A partial function f: Σ* ⇀ Σ* is partial computable if there exists a Turing Machine M that, on input w, halts with f(w) on its tape if f(w) is defined, and doesn't halt if f(w) is undefined.

Definition: Computable Set/Decidable Language

A set S ⊆ Σ* is computable (or decidable) if its characteristic function χₛ: Σ* → {0,1}is computable, where:

χ_S(w) = 1 if w ∈ S
χ_S(w) = 0 if w ∉ S

Definition: Computably Enumerable Set/Recognizable Language

A set S ⊆ Σ* is computably enumerable (or recursively enumerable) if there exists a partial computable function f: ℕ ⇀ Σ* such that S = {f(n) | n ∈ ℕ and f(n) is defined}

Equivalently, S is computably enumerable if it is the domain of a partial computable function, or if it is the range of a total computable function.

Theorem: Relationship Between Computable Functions and Sets

Let f: Σ* → Σ* be a function. The following are equivalent:

f is computable
The graph of f, G(f) = {(x, f(x)) | x ∈ Σ*}, is decidable

Let f: Σ* ⇀ Σ* be a partial function. The following are equivalent:

f is partial computable
The graph of f, G(f) = {(x, f(x)) | x ∈ dom(f)}, is recursively enumerable

Implications and Applications

The relationship between computable functions and sets has several important implications:

Turing-complete languages: Programming languages are often described as "Turing-complete" if they can compute all computable functions. This is equivalent to saying they can decide all decidable sets.
Complexity theory: When studying the efficiency of algorithms, we can focus either on the time and space complexity of computing functions or deciding languages, depending on which perspective is more natural.
Undecidability results: Many undecidability results can be formulated either in terms of uncomputable functions or undecidable languages, with the choice often depending on which makes the proof clearer.
Computability in mathematics: In mathematical analysis, a real number is computable if its decimal expansion can be computed to any desired precision by an algorithm. This connects the notion of computable functions to the computability of mathematical objects.

Summary

Advanced Turing Machine Concepts: Multi-tape TMs, nondeterministic TMs, alternating TMs, and probabilistic TMs all have the same computational power as standard TMs but offer different perspectives and potential efficiency gains.
Universal Turing Machines: A single machine that can simulate any other TM, forming the theoretical foundation of general-purpose computers and enabling self-reference in computation.
Language Classes: Decidable languages (always halt), recognizable languages (RE, accept if in the language), co-recognizable languages (co-RE, accept if not in the language), and their relationships form a rich hierarchy of computability.
Degrees of Undecidability: Not all undecidable problems are equally hard; Turing reducibility and Turing degrees provide a framework for comparing the relative complexity of undecidable problems.
Cardinality Arguments: There are countably many Turing Machines but uncountably many languages, proving that most languages are undecidable.
Effective Enumeration: Systematic ways to list countably infinite sets, allowing us to enumerate all TMs and all recognizable languages.
Computable Functions vs. Sets: The function-based and set-based perspectives on computability are equivalent and complementary, offering different insights into the nature of computation.