Introduction to the Theory of Computation¶
Sipser, M. (2013). Introduction to the Theory of Computation.
Cited by¶
5 citations across 5 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¶
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:da7ee5b93f64 · see in the full table