X Summary

Theory of Computation

Theory of computation studies formal models of languages, machines, computability, and complexity. It asks what can be recognized, what can be generated, what can be computed, and what can be computed efficiently.

Basics

• Core objects: sets, relations, alphabets, strings, and languages.
• A recognizer answers whether a string belongs to a language.
• A generator produces strings of a language from rules.
• Standard proof tools include contradiction, induction, the pigeonhole principle, and diagonalization.
• Diagonalization is one of the main proof patterns behind non-computability.

Automata

• Finite automata recognize regular languages.

• A DFA is built from a finite set of states, an input alphabet, a transition function, an initial state, and a set of accepting states.

• Finite automata work when membership can be decided by keeping only a bounded amount of information in the current state.

• Nondeterminism and regular expressions belong to the same regular-language layer.

• Regular-language reasoning often focuses on state design, minimal DFAs, and closure properties.

• Context-free grammars generate languages with recursive structure.

• A CFG uses variables, terminals, production rules, and a start symbol.

• Parse trees represent derivations and expose ambiguity when one string has multiple valid trees.

• Normal-form transformations clean grammars into restricted rule shapes such as Chomsky and Greibach normal forms.

• Pushdown automata recognize context-free languages.

• A PDA extends finite control with a stack.

• The stack stores information for later comparison, which is why PDAs handle patterns such as matched nesting and mirror structure that finite automata cannot.

• Final-state acceptance and empty-stack acceptance are the two standard acceptance views.

Computation

• Turing machines model general mechanical computation.
• A Turing machine uses finite control together with an unbounded tape, read-write access, and head movement.
• This model captures procedures that cannot be handled by finite state or a single stack alone.
• Variants such as multitape machines, multiple heads, and nondeterministic forms change convenience or efficiency, not the underlying notion of computability.

Two classical routes were used to formalize effective calculation:

• define a class of functions and call those the computable ones
• define an abstract machine and call the functions it computes the computable ones

These routes converge on the same notion:

$$\text{effectively calculable functions}\approx \text{general recursive functions}\approx \text{Turing-computable functions}$$

This is the core intuition behind the Church-Turing thesis: the informal idea of an effective procedure is captured by Turing computation.

The universal Turing machine sharpens that idea further:

• one machine can simulate another machine from its description
• the input and the machine description can both be treated as data
• this is the conceptual basis of programmable computation

Stored-program computers and Turing machines are equivalent in computational power. The practical machine model that grew from this line is the von Neumann stored-program architecture.

Limits

• Computability asks whether a problem can be solved at all by an algorithm.
• Undecidability begins once a problem lies beyond that limit.

The halting problem is the canonical example:

• given a machine (M) and input (w), determine whether (M) halts on (w)
• there is no algorithm that correctly answers this for every (M) and (w)

The universal-machine viewpoint and diagonalization together expose this limit. They show that formalizing computation also makes it possible to formally prove non-computability.

Related language classes form a hierarchy of increasing power:

• regular languages: finite automata
• context-free languages: pushdown automata and context-free grammars
• context-sensitive languages: linear bounded automata and context-sensitive grammars
• recursively enumerable languages: Turing machines and unrestricted grammars

Each higher layer can express languages that the lower layers cannot.

Complexity

Complexity theory asks a different question from computability. Once a problem is computable in principle, complexity asks how much time or space is needed to solve it.

• (P): problems solvable by deterministic machines in polynomial time
• (EXP): problems solvable in exponential time
• (NP): problems solvable by nondeterministic machines in polynomial time, or equivalently problems whose proofs can be verified in polynomial time

NP-completeness marks the hardest problems in (NP):

• a language is NP-complete if it is in (NP) and every problem in (NP) reduces to it in polynomial time
• if any NP-complete problem is in (P), then (P = NP)

This creates the central split:

• computability sets the outer boundary of algorithmic possibility
• complexity separates infeasible computation from practically feasible computation

---