Computability and Complexity Vocabulary

Formal Definition and Mechanics of the Turing Machine

• Formal Definition:

  • A Turing machine is defined as a $5$-tuple $T = (Q, \theta, s, \beta, F)$ where:

  • $Q$ is the finite set of states.

  • $\Sigma$ is the tape alphabet.

  • $s \in Q$ is the start state.

  • $F \subseteq Q$ is the set of accepting states.

  • $\delta$ is the transition function.

• Physical Architecture and Operation:

  • Consists of an infinite tape divided into discrete cells.

  • Features a head that reads the symbol in the current cell, writes a symbol, and moves either left or right.

  • Driven by a transition function $\delta$ that takes the current state and symbol read, then determines what symbol to write, the next state to enter, and the move direction.

  • Halts immediately upon reaching an accept state or a reject state.

  • If the machine never halts, the decision problem is undecidable for that input.

• Theoretical Significance:

  • Serves as the formal mathematical definition of an algorithm. Any well-defined procedure mapping inputs to outputs is expressible as a Turing machine.

  • Formulates two central theoretical questions:

  • Computability: What can be computed at all.

  • Complexity: What can be computed efficiently.

• The Church-Turing Thesis:

  • Asserts that anything intuitively computable can be computed by a Turing machine.

  • It equates an informal intuitive notion with a formal mathematical model, making it a non-provable thesis rather than a theorem; however, it has never been falsified.

  • Establishes Turing completeness: machine variants (such as multi-tape or non-deterministic Turing machines) possess no more decision power than a standard single-tape deterministic Turing machine, even if they run faster.

• Worked Automaton Example (Pac-Man at a Fork):

  • Input string representation: $pppgggBB$, where $p$ represents tape cells to the fork on Pac-Man's side, $g$ represents cells on the ghost's side, and $B$ represents blank cells.

  • Language: L = \{p^n g^m \mid m > n > 0\} (representing the condition that the ghost is farther from the fork than Pac-Man).

  • Decision process: The machine erases matched $p$ and $g$ pairs one at a time (writing $X$ for each matched $p$), shifts right, and cycles back as needed. It lands in an accept state if m > n > 0 or a reject state once tape structure is resolved.

Decidability Classifications

• Turing-Recognizable (Semi-Decidable):

  • A language is Turing-recognizable if some Turing machine halts and accepts every input string belonging to the language.

  • For inputs not in the language, the machine may reject or loop endlessly without halting (no finite-time termination guarantee for non-members).

• Decidable (Turing-Decidable):

  • A language is decidable if some Turing machine halts (yielding an explicit accept or reject outcome) on every input with zero risk of infinite looping.

• Undecidable:

  • A language is undecidable if no Turing machine can decide it, even when granted unlimited tape space and unlimited execution time.

• Practical Asymmetry (Pac-Man Case Study):

  • Decidable problem: "Does this specific maze let Pac-Man collect every fruit?" This is decidable because there are finitely many paths, all of which can be enumerated and verified in finite time.

  • Undecidable problem: "Can Pac-Man evade the ghosts forever?" In a maze containing a loop, there is no upper bound on how long testing paths might take. An algorithm cannot conclude "no" in finite time, even though it might quickly confirm an escape path ("yes") if one exists.

  • The accept side is resolvable in finite steps, while the reject side remains potentially open-ended.

The Halting Problem

• Definition:

  • The canonical undecidable problem in theoretical computer science.

  • Evaluates whether a testing machine $H$ can exist that takes an arbitrary Turing machine $X$ and input $I$, and correctly decides whether $X(I)$ halts.

• Proof of Undecidability (Self-Reference Argument):

  • Suppose a machine $H$ exists that takes $(X, I)$ and correctly decides halting.

  • Define a machine $X$ that takes input $I$ and calls $H(I, I)$:

  • If $H(I, I)$ returns "$I$ halts", $X$ deliberately enters an infinite loop.

  • If $H(I, I)$ returns "$I$ doesn't halt", $X$ accepts and halts.

  • Run machine $X$ on its own description, executing $X(X)$:

  • If $H$ says $X$ halts on $X$, then by $X$'s internal definition, $X$ must loop forever (Contradiction).

  • If $H$ says $X$ does not halt on $X$, then by $X$'s internal definition, $X$ must halt (Contradiction).

  • Concluding result: The premise that $H$ exists is false. The halting problem is undecidable.

• Implications and Universal Turing Machines:

  • Sets a hard boundary on what any algorithm, hardware, or computational resource can determine.

  • Deciding halting in general is impossible. However, a weaker concept—a Universal Turing Machine (UTM) that simulates any other machine given its input description—is achievable and serves as the foundation of modern stored-program computers.

The Chomsky Hierarchy

• Overview:

  • A nested hierarchy of decidable language families, where each inner level is stricter and easier to decide than the outer level, corresponding to progressively weaker variants of the Turing machine.

  • Strict containment relationship:     $\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Decidable}$

• Hierarchical Levels (Outer to Inner):

  • Level 1: Turing-Decidable / Turing-Recognizable

  • Decided by: Full Turing machine.

  • Grammar: Any decidable language.

  • Example: Any decidable language.

  • Level 2: Context-Sensitive

  • Decided by: Linear-Bounded Automaton (a Turing machine restricted to a tape length no longer than the input string).

  • Grammar: Rewriting rules where symbol transformations depend on neighboring symbols.

  • Example: $3$-way mutual dependencies (such as equal counts of $3$ fruit types).

  • Level 3: Context-Free

  • Decided by: Pushdown Automaton (equipped with stack memory only).

  • Grammar: Rewriting rules that do not depend on neighbors, or depend only simply to match counts.

  • Example: L = \{p^n g^m \mid m > n > 0\} and programming-language syntax.

  • Level 4: Regular

  • Decided by: Deterministic Finite Automaton (states and transitions, no memory).

  • Grammar: Regular expressions.

  • Example: Simplest patterns with no complex inter-character dependencies.

• Application in Compilers:

  • Compilers use context-free grammars to validate program syntax.

  • A pushdown automaton's stack provides the exact mechanism needed to track nested structural dependencies (such as matching brackets and nested expressions) that memoryless finite automata cannot process.

Asymptotic Notation and Complexity Fundamentals

• Principles of Measurement:

  • Exact running time (seconds, step counts) depends on hardware speed and software implementation.

  • Complexity measures how execution time scales relative to input size $n$.

  • Constant factors and lower-order terms are discarded.

• Worked Example (Linear Search over Unsorted Array of Size $n$):

  • Best case: Target is at the first position, yielding lower bound $\Omega(1)$.

  • Average case: Target is near the middle, yielding $\Theta(n/2)$, which simplifies to tight bound $\Theta(n)$.

  • Worst case: Target is at the end or absent, yielding upper bound $O(n)$.

• Asymptotic Notation Definitions:

  • $\text{Big-}O$: Asymptotic upper bound (worst-case scenario).

  • $\text{Big-}\Omega$: Asymptotic lower bound (best-case scenario).

  • $\text{Big-}\Theta$: Tight bound (combining upper and lower bounds), used for average-case running time.

• Standard Complexity Classes:

  • $O(1)$: Constant time (e.g., reading array[0]).

  • $O(\log_2(n))$: Logarithmic time (e.g., binary search).

  • $O(n)$: Linear time (e.g., scanning an unsorted array).

  • $O(n \log_2(n))$: Linearithmic time (e.g., average-case quicksort).

  • $O(n^2)$: Quadratic time (e.g., bubble sort).

  • $O(n^3)$: Cubic time (e.g., Floyd-Warshall algorithm).

  • $O(2^n)$: Exponential time (e.g., naive recursive Fibonacci).

  • $O(n!)$: Factorial time (e.g., brute-force Traveling Salesperson Problem).

• Binary Search Complexity Mechanics:

  • Each comparison halves the remaining search space.

  • A sequence of length $n$ can be halved at most $\log_2(n)$ times before reaching a single element, establishing $O(\log_2(n))$ running time.

Machine Architecture and Computational Efficiency

• Model Impact on Complexity vs. Computability:

  • Computability power remains unchanged across machine variants (all standard models decide the same set of languages).

  • Complexity efficiency varies drastically based on the machine model, altering the running-time class for an identical language.

• Worked Efficiency Comparison (L = \{p^n g^m \mid m = n > 0\}):

  • Machine $M_1$ (Single-tape, naive algorithm):

  • Repeatedly rescans tape, erasing one $p$ and one $g$ per pass.

  • Execution: $n/2$ passes $\times\, O(n)$ work per pass = $O(n^2)$.

  • Machine $M_2$ (Single-tape, optimized algorithm):

  • Erases every other $p$ and every other $g$ in one pass, halving what remains each time.

  • Execution: $O(\log_2(n))$ passes $\times\, O(n)$ work per pass = $O(n \log_2(n))$.

  • Machine $M_3$ (Two-tape algorithm):

  • Copies $p$ symbols to tape $2$ while scanning tape $1$, then cancels them against $g$ symbols on tape $1$ in a single pass.

  • Execution: Single pass over each tape = $O(n)$.

• Multi-Tape Equivalence and Crossover Theorem:

  • A $k$-tape Turing machine is simulated deterministically on a single-tape machine by storing $k$ tape segments separated by markers on a single tape.

  • Multi-tape machines yield no extra computational power, only increased efficiency.

  • Crossover Fact: Any language decided by a single-tape Turing machine in $O(n \log_2(n))$ time is strictly regular.

Time Complexity Classes: P, NP, and Reductions

• Class P:

  • Defined as problems decidable by a deterministic single-tape machine in polynomial time $O(n^k)$ for some constant k$.\n * Treated as computationally tractable or reasonable.\n * Significance of the Polynomial/Exponential Gap:\n * At input size n = 400$, an$O(n^4)$algorithm completes in under$7\,\text{seconds}$on a$4\,\text{GHz} processor.\n * An O(2^n)$algorithm at$n = 400 requires more execution operations than total physical operations in the history of the universe.\n\n* Class NP:\n * Defined as problems whose proposed solutions can be verified in polynomial time.\n * Equivalently defined as problems decidable in polynomial time by a Non-deterministic Turing Machine (NTM).\n * Nondeterministic Execution Mechanics:\n * An NTM's transition function branches into a set of next states simultaneously, exploring all computational branches in parallel.\n * Accepts if any branch lands in an accepting state.\n * Nondeterminism adds efficiency rather than decision power. An NTM can be deterministically simulated using a 3-tape machine performing Breadth-First Search (BFS); Depth-First Search (DFS) cannot be used because infinite non-accepting loops would block exploration of accepting branches.\n\n* P vs. NP Relationship:\n * P \subseteq NP holds trivially (any problem solvable quickly can be verified quickly).\n * Whether P = NP is the primary open problem in theoretical computer science.\n\n* Worked Verification Example (Hamiltonian Path):\n * Problem: Determine if a path exists visiting every vertex in a graph exactly once (e.g., Pac-Man eating every pellet without recrossing territory).\n * No known deterministic polynomial-time algorithm exists to find such a path.\n * Verification of a proposed path is linear time O(n) (checking that adjacent pairs are connected).\n * An NTM guesses the path and verifies it in polynomial time, placing Hamiltonian Path in NP.\n\n* Reductions and Cook-Levin Theorem:\n * Reduction: Problem B$is at least as hard as problem$C$if a solver for$C$can solve$B. If conversion runs in polynomial time, it is a polynomial reduction (e.g., reducing SAT to graph clique-finding).\n * Cook-Levin Theorem: A polynomial-time solution to any single NP-complete problem yields a polynomial-time solution for every problem in NP.\n * NP-Complete Definition: A problem is NP-complete if every problem in NP polynomially reduces to it.\n * Proven NP-Complete Problems: SAT (Boolean Satisfiability, the first proven NP-complete problem) and Hamiltonian Path.\n * Practical Consequence: Proving P = NP$requires finding only one polynomial algorithm for one NP-complete problem. None has been found, and the prevailing belief is$P \neq NP\n\n* Class NP-Hard:\n * Every problem in NP reduces to an NP-hard problem in polynomial time.\n * An NP-hard problem does not need to be in NP itself (it may not be verifiable in polynomial time and can exist in higher complexity classes like EXPTIME).\n\n\n# Space Complexity and Savitch's Theorem\n\n* Definitions:\n * \text{PSPACE}$: Problems decidable by a deterministic machine using tape length polynomial in input size$n.\n * \text{NPSPACE}$: Problems decidable by a non-deterministic machine using tape length polynomial in input size$n.\n\n* Savitch's Theorem:\n * Formally proves that \text{PSPACE} = \text{NPSPACE}.\n * A non-deterministic machine using space S(n)$can be simulated deterministically in space$(S(n))^2\n * Demonstrates a quadratic space blow-up when removing non-determinism, contrasting with the exponential time blow-up believed to occur when removing non-determinism from time complexity classes.\n\n* Worked Proof Intuition (Pathfinding in Directed Graphs):\n * Problem: Determine if a path exists from source s$to target$t$in an$n-vertex graph.\n * An NTM guesses and verifies a path using O(\log_2(n)) space (storing current vertex, target, step count).\n * Deterministic Simulation (Savitch Recursion):\n * To check if a path of length L$exists from$s$to$t$, recursively test if a length-$L/2$path exists from$s$to midpoint$v$, and another length-$L/2$path exists from$v$to$t$.

  • Recursion depth is $O(\log_2(L))$.

  • Each level stores data of size $O(\log_2(n))$.

  • Total space required: $O(\log_2(n)) \times O(\log_2(n)) = O((\log_2(n))^2)$, matching the predicted quadratic blow-up.

• Hierarchy of Complexity Inclusion Chains:

  • Because space utilized cannot exceed total time steps taken (space used $\le$ steps taken), $P \subseteq \text{PSPACE}$ and $NP \subseteq \text{NPSPACE}$.

  • Combining these bounds with Savitch's Theorem yields the complete inclusion chain:     $\text{P} \subseteq \text{NP} \subseteq \text{PSPACE} = \text{NPSPACE} \subseteq \text{EXPTIME}$

  • The converse inclusion does not hold: a problem requiring polynomial space can still demand exponential running time.