Introduction to the Theory of Computation¶
Sipser, M. (2012). Introduction to the Theory of Computation.
Cited by¶
10 citations across 10 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Closure
- The recursively enumerable languages are closed under union, intersection, concatenation, and Kleene star but not under complement (the latter establishing the formal asymmetry between recursive and recursively enumerable), as Sipser (2012) develops in his standard treatment of language-class closure properties.
This sourceCengage Learning. Standard theory-of-computation text developing the closure properties of regular, context-free, and Turing-recognisable languages and the three-fold (closure/automaton/regular-expression) equivalence.
- The recursively enumerable languages are closed under union, intersection, concatenation, and Kleene star but not under complement (the latter establishing the formal asymmetry between recursive and recursively enumerable), as Sipser (2012) develops in his standard treatment of language-class closure properties.
- Complement
- Recognizing the complement pattern supports several portable reasoning moves. Negative reformulation: when the affirmative version of a problem is intractable, ask whether the complement is tractable — "what is the probability of at least one X?" becomes "what is the probability of zero Xs?", "what is permitted?" becomes "what is prohibited?", "where is the white space?" becomes "what is covered?" — and one solves whichever side is simpler. Universe surfacing: when two analyses of the same quantity disagree, ask what universe each is computing in, since implicit universe-disagreement is among the most common sources of cross-talking analysis. Double-negation calibration: check in any substrate whether \((A^c)^c = A\); if it holds, classical complementation is in force and the standard moves apply, and if it fails — as in intuitionistic logic, fuzzy categories, or regulatory regimes where un-regulation does not return to a clean baseline — the substrate is non-classical and complement-based reasoning must be re-justified rather than assumed. Closure-under-complement diagnosis: families closed under complement, such as σ-algebras and Boolean algebras and the regular languages, carry structural guarantees (a measurable event has a measurable complement; a regular language has a regular complement) that simplify proofs
This sourceEstablishes closure of the regular languages under complement (swap accept/non-accept states of a DFA) and related complement-closure properties of language families. (
- Recognizing the complement pattern supports several portable reasoning moves. Negative reformulation: when the affirmative version of a problem is intractable, ask whether the complement is tractable — "what is the probability of at least one X?" becomes "what is the probability of zero Xs?", "what is permitted?" becomes "what is prohibited?", "where is the white space?" becomes "what is covered?" — and one solves whichever side is simpler. Universe surfacing: when two analyses of the same quantity disagree, ask what universe each is computing in, since implicit universe-disagreement is among the most common sources of cross-talking analysis. Double-negation calibration: check in any substrate whether \((A^c)^c = A\); if it holds, classical complementation is in force and the standard moves apply, and if it fails — as in intuitionistic logic, fuzzy categories, or regulatory regimes where un-regulation does not return to a clean baseline — the substrate is non-classical and complement-based reasoning must be re-justified rather than assumed. Closure-under-complement diagnosis: families closed under complement, such as σ-algebras and Boolean algebras and the regular languages, carry structural guarantees (a measurable event has a measurable complement; a regular language has a regular complement) that simplify proofs
- Diagonal Impossibility
- The diagonal reasoning runs without re-deriving anything: because the language expresses its own interpreter, a total equivalence-checker would let one construct a self-flipping program (reduce halting to equivalence — a program is equivalent to a trivially-looping one exactly when it fails to halt), so by the same forced-contradiction skeleton no total equivalence-decider exists.
This sourceStandard text: undecidability of program equivalence (EQ_TM) via reduction from the halting problem.
- The diagonal reasoning runs without re-deriving anything: because the language expresses its own interpreter, a total equivalence-checker would let one construct a self-flipping program (reduce halting to equivalence — a program is equivalent to a trivially-looping one exactly when it fails to halt), so by the same forced-contradiction skeleton no total equivalence-decider exists.
Domain-specific¶
Mechanisms¶
- Enumeration and Dovetailing
- Many-One Reduction Proof
- A mapping that is not total, not genuinely computable, or whose biconditional holds in only one direction proves nothing
This sourceDefines a many-one reduction as a total computable mapping that preserves membership in both directions.
- A mapping that is not total, not genuinely computable, or whose biconditional holds in only one direction proves nothing
- Turing-Reduction Analysis
- Because `A ≡_T co-A` always, a Turing reduction is deaf to complement structure and cannot certify the one-sided facts a Many-One Reduction Proof can; and it speaks only of computability, saying nothing about cost.
This sourceShows that every language is Turing-equivalent to its complement, while mapping reductions can preserve one-sided recognizability distinctions; these are computability relations rather than resource-cost bounds.
- Because `A ≡_T co-A` always, a Turing reduction is deaf to complement structure and cannot certify the one-sided facts a Many-One Reduction Proof can; and it speaks only of computability, saying nothing about cost.
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Not recorded. Neither this nor any other of the 10 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 3 other ways.
- https://math.mit.edu/~sipser/book.html ×1
- https://www.cengage.com/c/student/9781133187790/ ×1
- https://www.cengage.com/c/student/9781133187790/?filterBy=Student ×1
Registry ID ref:685aa578e2dc · see in the full table