The zombie misconception of theoretical computer science

Original Article ↗ Hacker News Discussion ↗

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.