Course: Foundations of Computer Science, CS 101, University of Michigan Difficulty: Advanced Prerequisites: Part 1 (Algorithms and Graph Theory) study notes, comfort with proof by contradiction, basic set theory notation.
This document covers the computability and formal languages portion of the CS 101 midterm. The central question is: what can a computer solve, and what is provably beyond its reach? You will need to understand the hierarchy from finite automata through Turing machines, know which languages are decidable, recognisable, or neither, and be able to construct reductions that prove undecidability. This material is proof-heavy, and the exam will almost certainly require you to build or analyse a reduction.
Some problems have no algorithm that solves them, full stop. The halting problem is the most famous example. You prove a language is undecidable by reducing a known undecidable language to it. Rice's theorem gives a shortcut: any non-trivial property of the language recognised by a Turing machine is undecidable.
Turing machine (TM)
A 7-tuple (Q, Sigma, Gamma, delta, q0, q_accept, q_reject) that models computation. It reads and writes symbols on an infinite tape, moving left or right. It is the standard model for what "computable" means.
Decidable language
A language L is decidable if there exists a Turing machine that halts on every input and correctly accepts strings in L and rejects strings not in L. Think of it as: a program that always finishes and always gives the right yes/no answer.
Recognisable language (Turing-recognisable, recursively enumerable)
A language L is recognisable if there exists a TM that accepts every string in L. It may loop forever on strings not in L. So it can say "yes" reliably, but its "no" might never arrive.
Co-recognisable language
A language L is co-recognisable if its complement (the set of all strings not in L) is recognisable. Equivalently, there is a TM that can reliably say "no" for strings not in L, but may loop on strings in L.
Theorem 4.22 (Decidable = recognisable + co-recognisable)
A language is decidable if and only if it is both recognisable and co-recognisable. This is a key structural result: if you can reliably say "yes" and reliably say "no" (from two separate machines), you can combine them into one that always halts.
Turing reduction
Language A is Turing-reducible to B (written A <=T B) if there exists a program M_A that decides A using a "black box" (oracle) that decides B. In simple terms, if you could magically solve B, you could use that to solve A.
Halting problem (A_TM)
The language A_TM = { (M, w) : M is a TM and M accepts w }. This is undecidable: there is no algorithm that can correctly determine, for every TM and input, whether that TM will accept.
Rice's theorem
Any non-trivial property of the language recognised by a Turing machine is undecidable. A property is non-trivial if some recognisable languages have it and some do not.
Regular language
A language that can be recognised by a finite automaton (DFA or NFA). Regular languages are closed under union, concatenation, and star. Every regular language is decidable.
Injective (one-to-one)
A function f: A -> B where distinct inputs always map to distinct outputs. Formally: a1 != a2 implies f(a1) != f(a2).
Surjective (onto)
A function f: A -> B where every element of B is mapped to by at least one element of A. Formally: for every b in B, there exists a in A such that f(a) = b.
Bijective
A function that is both injective and surjective. It pairs every element of A with exactly one element of B, and vice versa.
A regular language is any language recognised by a DFA or NFA
The class of regular languages is closed under union, concatenation, and the star (Kleene) operation
Every NFA has an equivalent DFA (subset construction)
A language is regular if and only if some regular expression describes it
All regular languages are decidable (a DFA always halts)
Regular expressions, NFAs, and DFAs are all equivalent in expressive power
Languages that require "counting" or "matching" (e.g. a^n b^n) are not regular
The pumping lemma is the standard tool for proving a language is not regular (not directly on this cheatsheet, but often tested)
A TM is a 7-tuple: (Q, Sigma, Gamma, delta, q0, q_accept, q_reject)
Q = set of states, Sigma = input alphabet, Gamma = tape alphabet (includes a blank symbol), delta = transition function, q0 = start state, q_accept and q_reject = halting states
A TM can move its head left or right, read and write on the tape
Every multitape TM has an equivalent single-tape TM
A language is Turing-recognisable if some multitape TM recognises it
A language is Turing-recognisable if some enumerator enumerates it
Regular languages are a strict subset of decidable languages
Decidable languages are a strict subset of recognisable languages
Recognisable languages include some that are not decidable (e.g. A_TM)
Some languages are not even recognisable (e.g. the complement of A_TM)
A_DFA = { (B, w) : B is a DFA that accepts w }. Decidable: just simulate the DFA.
E_DFA = { (A) : A is a DFA and L(A) = empty set }. Decidable: check if any accept state is reachable from the start.
EQ_DFA = { (A, B) : A and B are DFAs and L(A) = L(B) }. Decidable: build the symmetric difference and test emptiness.
If A <=T B and B is decidable, then A is decidable. The contrapositive is what you use on the exam: if A is undecidable and A <=T B, then B is undecidable.
A_TM = { (M, w) : M is a TM and M accepts w }
Proof that A_TM is undecidable (by contradiction):
Assume a decider H exists for A_TM
Construct a new TM D that calls H to determine what M does on its own description
D on input (M): run H on (M, (M)). If H accepts, reject. If H rejects, accept
Run D on itself: D((D)) leads to a contradiction. If D accepts (D), then H says D accepts (D), so D rejects. If D rejects (D), then H says D rejects (D), so D accepts
No such H can exist. A_TM is undecidable
A_TM is recognisable (you can simulate M on w and accept if it halts and accepts, though you may loop if it does not halt)
The complement of A_TM is not recognisable
The standard technique: to show language L is undecidable, reduce A_TM (or another known undecidable language) to L.
Construct a TM that, given an instance of A_TM, transforms it into an instance of L
If L were decidable, you could decide A_TM, contradicting its undecidability
Common reductions from the cheatsheet:
A_TM <=T L_HALT (the halting language, does M halt on w?)
A_TM <=T L_ACC (does M accept at least one string?)
L_HALT <=T various other languages
L_HALT = { (M, w) : M is a TM that halts on input w }. This is undecidable. The reduction from A_TM works by constructing a modified machine that halts if and only if the original accepts.
L_ALL-REJECT = { (M) : M is a TM that rejects all inputs }. The cheatsheet shows a decider for L_ACC can be used to build a decider for this: construct M' that runs M on x, then flips the answer. M rejects everything if and only if M' accepts everything.
A property P of recognisable languages is non-trivial if: (a) at least one recognisable language has property P, and (b) at least one recognisable language does not have property P
Rice's theorem states: if P is a non-trivial property, then the language { (M) : L(M) has property P } is undecidable
This is a powerful shortcut. Instead of building a reduction from scratch, you can invoke Rice's theorem directly
What Rice's theorem covers: any question about what a TM's language looks like (is it empty? is it finite? is it regular? does it contain a specific string?)
What Rice's theorem does not cover: questions about the TM's structure or behaviour (does it halt within 12 steps? does it have more than 376 states? does it write a 1 to its tape?). Those are questions about the machine, not its language
L_WritesOne = { (M, x) : M writes a 1 to its tape when run on x }. This is not in the form Rice's theorem requires (it is about behaviour, not the language), but it is still undecidable. The proof constructs a modified machine M' that writes a 1 exactly when M halts, reducing L_HALT to L_WritesOne.
To show B is undecidable, pick a known undecidable language A and show A <=T B
The reduction is a construction: given an oracle for B, build a decider for A
Contrapositive: if no decider for A exists, and A <=T B, then no decider for B exists either
The typical reduction from A_TM to some target language L follows this pattern:
Assume a decider D exists for L
Construct a reduction machine R that, on input (M, x):
Builds a new machine M' whose behaviour encodes the question "does M accept x?"
Runs D on (M') or on some constructed input
Uses D's answer to decide whether M accepts x
Since R decides A_TM and A_TM is undecidable, D cannot exist
L_0 can be decided by counting the number of bits in (M) and accepting if that number is greater than 376, rejecting otherwise. L_0 is decidable.
L_1 is undecidable because it is the complement of A_ACC (the complement of a recognisable, undecidable language).
L_2 is decided by the machine that simulates running M(x) for 12 steps and accepts if M accepts within those steps, otherwise rejects. L_2 is decidable.
L_3 is decided by the machine that ignores its input and rejects. L_3 = empty set, which is decidable.
L_EQ = { (M1, M2) : L(M1) = L(M2) }
L_EQ is undecidable (reduce from A_TM)
L_EQ is not recognisable and not co-recognisable
The proof works by showing that both L_EQ and its complement can be reduced from known undecidable languages
If L1 and L2 are undecidable languages, then L1 union L2 is undecidable (consider A_HALT and its complement, whose union is Sigma*)
If L1 and L2 are undecidable languages, L1 intersection L2 is undecidable
If L1 and L2 are decidable languages, L1 union L2 is decidable
If L is an undecidable language, its complement is undecidable
The set of recognisable languages is countable
Some languages are not Turing-recognisable (the set of all languages is uncountable, but the set of all TMs is countable)
The halting problem is why no compiler can perfectly detect all infinite loops. Static analysis tools are necessarily conservative: they catch some loops but must give up on others.
Rice's theorem explains why perfect virus detection is impossible in the general case. Any non-trivial question about a program's behaviour ("does it delete files?") is undecidable, so antivirus software relies on heuristics and signatures rather than mathematical proof.
Regular expressions power search tools, text editors, and log-parsing systems. Understanding their limits (they cannot match balanced parentheses, for example) prevents misuse.
Students often think "undecidable" means "unsolvable for all inputs." It does not. It means no single algorithm works correctly on every input. A particular instance might be easy; the problem is that there is no universal method.
A frequent mistake is applying Rice's theorem to properties of the machine rather than properties of its language. "Does M have fewer than 100 states?" is a question about the machine's structure, not about what it recognises. Rice's theorem does not apply.
Students confuse "recognisable" with "decidable." Recognisable means the machine accepts strings in L but might loop forever on strings outside L. Decidable means it always halts with the correct answer.
When building reductions, students sometimes construct the reduction in the wrong direction. To show L is undecidable, you reduce a known undecidable problem to L (not the other way round).
⚠️ The halting problem proof is almost certainly on the exam. Be able to reproduce the diagonalisation argument step by step.
⚠️ Know how to construct a reduction. The exam will likely give you a target language and ask you to prove it undecidable by reducing A_TM or L_HALT to it.
⚠️ Rice's theorem questions often appear as "is this language decidable?" where the language is defined in terms of what a TM recognises. If the property is non-trivial, the answer is no, and you cite Rice's theorem.
⚠️ The relationship between decidable, recognisable, and co-recognisable is a classic short-answer target. Know Theorem 4.22 cold: decidable = recognisable + co-recognisable.
⚠️ Be prepared for a question asking you to classify several languages as decidable, recognisable but not decidable, or not recognisable. The L_0 through L_3 examples in the cheatsheet are exactly this format.
True or False: A_TM is decidable. (False. It is recognisable but not decidable.)
True or False: If a language is both recognisable and co-recognisable, it is decidable. (True. This is Theorem 4.22.)
Fill in the blank: Rice's theorem applies to non-trivial properties of a TM's ___, not properties of the TM itself. (Language.)
True or False: The complement of A_TM is recognisable. (False. If it were, A_TM would be decidable by Theorem 4.22.)
True or False: Every decidable language is also regular. (False. All regular languages are decidable, but not vice versa.)
Q: Outline the diagonalisation proof that A_TM is undecidable.
A: Assume a decider H exists for A_TM. Construct D that, on input (M), runs H on (M, (M)). If H accepts, D rejects; if H rejects, D accepts. Running D on (D) yields a contradiction: D accepts (D) if and only if D rejects (D). Therefore H cannot exist.
Q: Is the language { (M) : M is a TM and |L(M)| = 5 } decidable?
A: No. The property "the language has exactly 5 strings" is a non-trivial property of the language recognised by M (some TMs recognise languages of size 5, others do not). By Rice's theorem, this language is undecidable.
Q: Is the language { (M) : M is a TM that accepts w within 12 steps } decidable?
A: Yes. Simulate M on w for 12 steps. If M accepts within 12 steps, accept. Otherwise reject. The simulation always halts because it runs at most 12 steps.
Q: Prove that L_HALT is undecidable by reducing A_TM to L_HALT.
A: Assume a decider R exists for L_HALT. Construct a decider S for A_TM: on input (M, w), build M' that simulates M on w and, if M rejects, enters an infinite loop. Then M' halts on w if and only if M accepts w. Run R on (M', w). If R accepts, M' halts, so M accepts w: accept. If R rejects, M' loops, so M did not accept w: reject. Since S decides A_TM and A_TM is undecidable, R cannot exist.
Q: Explain why Rice's theorem does not apply to the language { (M) : M has more than 376 states }.
A: "Has more than 376 states" is a property of the Turing machine's description, not a property of the language it recognises. Two different TMs can recognise the same language while having different numbers of states. Rice's theorem only governs properties of L(M), not of M itself.
Decidability connects directly to complexity theory, which typically follows in the second half of the course. Once you know some problems cannot be solved at all, the next question is which solvable problems can be solved efficiently (P vs NP). Turing reductions are the ancestor of polynomial-time reductions used in NP-completeness proofs. The formal language hierarchy (regular, context-free, decidable, recognisable) also appears in compiler design, where lexers use finite automata and parsers use context-free grammars.
Turing machine, TM, decidable, undecidable, recognisable, Turing-recognisable, recursively enumerable, co-recognisable, halting problem, A_TM, diagonalisation, Rice's theorem, non-trivial property, Turing reduction, mapping reduction, L_HALT, L_ACC, L_EQ, regular language, DFA, NFA, finite automaton, closure properties, injective, surjective, bijective, one-to-one, onto, CS 101, Foundations of Computer Science, UMich, midterm review, computability theory, decidability hierarchy