Question bank — Church-Turing thesis

False. One side ("effectively calculable") is an informal, intuitive notion with no formal object to manipulate, so there is nothing to prove against; it is a hypothesis backed by overwhelming evidence.

True. Both sides are formal models (functions built from $Z,S,P$ with $\mu$, versus functions computed by a tape machine), so their equality was proved (Kleene). CTT is the extra claim that this formal class also equals the informal "everything computable."

False. A single-tape machine can simulate $k$ tapes by storing them side-by-side (interleaved) on its one tape and shuttling the head back and forth; the simulation is at worst quadratically slower but always faithful. So multi-tape, 2-D-tape, and nondeterministic machines compute the exact same set of functions — only speed changes. This robustness is itself evidence for CTT.

False. A UTM takes a description of any TM plus its input and simulates it step-by-step, so its outputs are exactly the outputs of ordinary TMs — nothing outside the Turing-computable class. It is a general-purpose machine, not a more-powerful one.

True. All the 1930s models were proven mutually equivalent by explicit translations (each simulates the others), so λ-definable, $\mu$-recursive, and Turing-computable name one and the same class.

False. CTT is silent about speed and resources. The efficiency claim is the separate, contested Strong/Physical thesis, not the standard one.

False. Undecidability is fully consistent with CTT: the thesis only claims that whatever is computable is Turing-computable, not that everything is computable. Some functions are computable by nobody.

False. The class deliberately includes partial functions (functions undefined on some inputs) — the minimization operator $\mu$ (an unbounded while) can fail to halt, mirroring real programs that run forever.

False. A quantum device's output is still a Turing-computable function (a TM can simulate the amplitude bookkeeping); it may be faster, so it only pressures the Strong/physical thesis about efficiency, not standard CTT (see Computational Complexity).

Error: it says every effectively calculable function is Turing-computable. Most functions on $\mathbb{N}$ are non-computable (there are uncountably many functions but only countably many algorithms).

Error: proving two formal models equal does not touch the informal notion. Convergence of formal models is strong evidence, but CTT's claim about the intuitive notion stays unprovable.

Error: primitive recursion = only bounded for loops. The Ackermann function is computable yet not primitive recursive; the unbounded search $\mu$ is what closes the gap (see Mu-Recursive Functions).

Error: by CTT any algorithm is some Turing machine, so "no TM decides halting" upgrades to "no algorithm of any kind decides halting" — the impossibility is universal.

Error: CTT lets you describe an algorithm in English/pseudocode instead of a TM once you have one. It never conjures an algorithm you have not exhibited.

Error: nondeterminism changes time complexity (the P vs NP question lives there), not the set of computable functions — a deterministic TM can try all branches one after another. Uniqueness of the computable class is untouched.

Any precise replacement would just be another formal model; proving CTT against it only shows two formal models agree, leaving the original intuitive notion still unformalized.

Because each proof only links formal models to each other; none reaches the informal notion. Their agreement makes it implausible they all missed something, but "implausible" is not "proven."

$\mu y[g(\vec{x},y)=0]$ searches $y=0,1,2,\dots$ with no upper bound; if no such $y$ exists the search never stops, so the function is undefined there — precisely a partial function.

Without CTT, "no TM solves it" might seem like a limitation of one clunky model. CTT says every algorithm equals some TM, so the barrier applies to Python, quantum, and pencil-and-paper alike.

It makes an empirical claim about physics and efficiency (polynomial slowdown), which experiments and models like quantum computing can genuinely challenge; the standard thesis is only about what is computable.

Yes, as a partial function (undefined on the odd inputs) — the computable class includes partial functions, and $\mu$-recursion naturally produces exactly this kind of "defined only sometimes" behaviour.

On $\mathbb{N}$ directly, but strings/graphs can be encoded as natural numbers (write them in binary and read as a number), so CTT covers them too. Full real numbers need a separate computability theory since they are not finitely representable in general.

It would violate CTT's spirit, but such a device is not "effectively calculable" (no finite mechanical recipe). CTT is about finite step-by-step procedures, so a physically impossible oracle is out of scope.

That is no longer a Turing machine (states must be finite), so CTT does not license it. An infinite control could in principle "hard-code" non-computable answers, which is exactly why the finiteness condition matters.

Yes, trivially — the everywhere-undefined partial function is $\mu$-recursive. For example $\mu y[S(y)=0]$ searches for a $y$ with successor $y+1=0$, which never exists over $\mathbb{N}$, so it never halts on any input — sitting at the degenerate boundary of the class.

No. It claims the set of computable functions is captured by TMs; a single function has infinitely many different algorithms/TMs computing it. CTT is about the class, not about uniqueness of recipes.