The zombie misconception of theoretical computer science
Arguments over a blog post on theoretical computer science expose how easily everyday intuitions about “what a computer can do” clash with the formal notion of computability. Commenters debate examples like a function defined in terms of whether God exists, the P vs NP question, and Busy Beaver numbers to illustrate that computability is about the existence of a program (often a trivial constant function), not about our ability to find it, prove it correct, or run it in practice. The thread also touches on classical vs constructive logic, the role of the law of excluded middle, and whether the field’s jargon and pedagogy inadvertently confuse non‑specialists.
Clarifying the “God function” example
- Many readers find the textbook-style question confusing: is “f” one function or a choice between two?
- One camp says it’s really about a label: “f” denotes either the constant-1 or constant-0 function; both are computable, so whichever it is, “f is computable.”
- Others keep reading it as a function that itself branches on “God exists,” and argue the example conflates functions with choices between functions.
- Several note that the “God” wording drags in theology and modal logic (what if “God exists” is ill-posed?), which obscures the intended point about constant functions.
Computability vs knowing / proving the value
- Repeated clarification: “computable” means there exists some Turing machine that produces the right outputs, not that humans know which one or can derive it from axioms.
- There can be computable functions whose specific algorithm we can’t currently write, or whose correct constant value is unknown or even unprovable in a given formal system.
- Examples discussed: P vs NP as a single yes/no question, individual halting instances, values of Busy Beaver, and finite prefixes of uncomputable sequences.
P vs NP and “hardness of the question itself”
- Several emphasize that asking whether the single statement “P=NP?” is NP-hard or uncomputable is a type error: complexity applies to families of inputs, not one fixed instance.
- A single yes/no fact is always decidable in constant time by some trivial constant program, even if we don’t know which constant is correct or can’t prove it in ZFC.
- Some readers object that this feels like dodging the real difficulty (finding a proof), but others insist distinguishing computability/complexity from provability is the whole point.
Halting problem, Busy Beaver, and finiteness
- Many comments use the halting problem, Busy Beaver, and Kolmogorov complexity to illustrate:
- Any fixed input (or finite set of inputs) has a trivial “lookup table” or constant program;
- Non-computability only arises over infinite domains.
- There is debate over whether questions like “BB(6) is computable” are meaningful to non-specialists, since they mix the technical and everyday senses of “computable.”
Logic foundations and LEM
- A substantial subthread debates classical logic vs intuitionistic/constructive views.
- Some object that the examples implicitly assume law of excluded middle (“God exists or not”), which they find philosophically or computationally unsatisfying.
- Others reply that in classical TCS, LEM is standard; dropping it changes the framework, not the correctness of the textbook arguments.
Pedagogy and presentation
- Some see the article (and textbook question) as clever and illuminating; others call it sophistry or poorly worded, arguing it misdirects students then mocks their confusion.
- Several note a chronic gap between strict technical jargon (“computable”) and colloquial usage (“can a computer actually do this?”), and argue educators should surface that distinction more explicitly.