Computability
Computability in Technical Interviews
At a Google Research interview, a candidate was asked: 'Write a program that determines whether a given program contains an infinite loop.' The candidate started writing code. The interviewer stopped them after a minute: 'That is impossible. Prove it.' Computability theory is not an abstraction for PhD students. It is the language researchers at Google, DeepMind, and Microsoft Research use to reason about fundamental system limitations.
- **FAANG Research interviews:** proving undecidability of static analysis, verification, and compilation problems is standard for senior/staff engineering positions
- **Static analysis:** TypeScript, mypy, Coverity all work with approximations due to Rice's Theorem. Knowing this explains why no 'perfect' analyzer exists
- **Reliable systems architecture:** circuit breakers, watchdogs, timeouts follow from the undecidability of the Halting Problem, not merely heuristic best practices
Undecidability Proofs: Templates
Research interviews at Google, DeepMind, and MSR regularly include questions like: 'prove that problem X is undecidable.' There are three reliable templates. First - diagonalization: assume decidability, derive contradiction via self-reference (Turing's classic for HP). Second - reduction from HP: show that if X were decidable, HP would be decidable too. Third - Rice's theorem: if X is a non-trivial property of TM languages, X is undecidable.
Rice's Theorem: any non-trivial semantic property of Turing machine languages is undecidable. 'Non-trivial' means not all TMs have the property and not all lack it. 'Semantic' means it depends on the computed function, not the machine description.
Rice's Theorem applies to the property 'TM M accepts the string "hello"'. Why is this Rice's Theorem rather than direct undecidability?
Reductions: Construction and Application
A reduction A <=_m B ('A many-one reduces to B') means: there exists a computable function f such that x in A if and only if f(x) in B. If B is decidable, then A is decidable. Contrapositive: if A is undecidable, then B is undecidable. In an interview the key skill is to construct f quickly: take an instance of problem A, build an instance of problem B. Critical skill - choosing the direction: reduce from a known undecidable problem to the one being proved.
Standard arsenal: HP (halting problem), ATM (acceptance problem), ETM (emptiness), EqTM (equivalence). Most undecidable interview problems reduce from HP or ATM. Many-one reduction is stricter than Turing reduction: A <=_m B does not imply B <=_m A.
Given a reduction HP <=_m X. What follows from the assumption that X is decidable?
Practical Limits of Computation
The limits of computability manifest beyond pure theory. Static analysis tools (ESLint, mypy, Coverity) cannot precisely determine any non-trivial property of programs by Rice's Theorem - only approximate. Program verification (Hoare logic, model checking) is sound and complete only for restricted models. All production verifiers sacrifice soundness (false negatives) or completeness (false positives). LLMs do not solve the halting problem - the transformer architecture does not change the computational model.
Engineering corollaries of Rice's Theorem: (1) perfect static analysis is impossible, (2) any linter has false positives or false negatives, (3) automated test generation cannot guarantee complete semantic coverage, (4) formal verification works only with restricted specifications.
Why is a perfect static analyzer that finds all null-dereference bugs without false positives impossible?
Architectural Conclusions from Computability Theory
Knowing computability theory changes architectural decisions. If a problem is undecidable, design the system around approximations with explicit guarantees. Choosing a sound analyzer (no missed errors) vs a complete analyzer (no false alarms) is a deliberate design choice, not a bug. Program termination: production systems always need timeouts, watchdogs, circuit breakers - not because the code is bad, but because termination is undecidable. Test generators (fuzzing, property-based testing) cover the space partially - an irreducible limitation.
Google Research interview question: 'Can a program determine whether another program contains an infinite loop?' The complete answer includes: (1) no in the general case (Turing's theorem), (2) yes for restricted models (finite automata, loop-free programs), (3) approximations: bounded model checking, abstract interpretation.
If a program has not hung in testing, it will definitely terminate on production inputs
The absence of hangs in tests guarantees nothing about behavior on other inputs
The Halting Problem is undecidable: no algorithm can determine from a program description and input whether it will terminate. Testing is a sample from an infinite input space.
Why must all production systems have timeouts, reasoning from computability theory?
Key Ideas
- **Three proof templates:** diagonalization (self-reference), reduction from HP/ATM, Rice's Theorem for semantic properties.
- **Reduction direction:** to prove X undecidable, build A <=_m X where A is a known undecidable problem.
- **Practical corollaries:** perfect static analysis is impossible (Rice), timeouts are mandatory (HP), verification works only for restricted models.
- **Interview vocabulary:** 'non-trivial semantic property', 'reduction', 'sound vs complete' - key terms for research positions.
Related Topics
Computability theory interview prep builds on the classical results of the course.
- Rice's Theorem — The main undecidability proof tool used throughout this lesson
- Mapping Reductions — The formal apparatus of reductions used in all the proofs
Вопросы для размышления
- A static analyzer guaranteeing no null-dereference errors produces many false positives. Is this a bug or a feature? How does Rice's Theorem affect the answer?
- LLM assistants (Copilot, Cursor) predict whether a function will terminate. Do they violate Turing's theorem? What exactly are they doing instead of 'solving' the halting problem?
- Quantum computers change which problems can be solved efficiently. Do they change the decidability boundary? What remains undecidable for quantum computational models?