Exercises — Church-Turing thesis

(a) False. CTT equates an informal notion ("effectively calculable") with a formal one (Turing machines). There is no formal object standing for the informal side, so there is nothing to prove against. It is a hypothesis backed by evidence. (b) False. Extra tapes change only speed, never the set of computable functions. A 1-tape machine can simulate any $k$-tape machine. (c) False. CTT never says "everything is computable." It says "if something is computable at all, a Turing machine does it." The Halting Problem is undecidable, and CTT actually makes that impossibility universal.

All of them. That collapse of independent definitions onto one class is the central evidence for CTT: $\{\text{Turing-computable}\}=\{\lambda \text{-definable}\}=\{\mu \text{-recursive}\}=\{\text{register-machine-computable}\}.$

Idea: $2x=x+x$. We already have $add$ from the parent note. So define $d(x)=add(x,x).$ This is composition: feed the input $x$ into both argument slots of an already-computable function. Formally $d(x)=add(P_1^1(x),P_1^1(x))$, where $P_1^1(x)=x$ just returns its input. Composition of computable functions is computable, so $d$ is primitive recursive. Check: $d(3)=add(3,3)=3+3=6=2\cdot 3.$ ✓

Step 1 (finite mechanical procedure): loop $k=0,1,2,\dots$ up to $n$; if $k\cdot k=n$ output yes; if $k\cdot k>n$ output no. Bounded loop $\Rightarrow$ always halts. Step 2 (invoke CTT — this is the licensed leap): a finite mechanical always-halting procedure exists $\Rightarrow$ by CTT a Turing Machine exists that decides it. We skip constructing the machine. Therefore "is $n$ a perfect square" is decidable. Check example: $n=16\Rightarrow k=4,4^2=16\Rightarrow$ yes; $n=15\Rightarrow$ we pass $3^2=9$, hit $4^2=16>15\Rightarrow$ no. ✓

The missing property: unbounded search. A primitive-recursive for loop must decide its bound before it starts — you say "repeat $n$ times" up front. That guarantees halting but forbids "keep going until a condition is met, however long that takes." Minimization $f(\vec{x})=\mu y[g(\vec{x},y)=0]=\text{smallest }y\text{ with }g(\vec{x},y)=0$ is a while loop: try $y=0,1,2,\dots$ with no ceiling, stopping the instant $g$ hits $0$. If no such $y$ exists, it runs forever — producing a partial function. Why real programs need it: actual code contains while loops that can loop forever (e.g. searching for a proof, waiting for a solution that may not exist). Any model that only had for loops would be too tame to model real software. The Mu-Recursive Functions add exactly this one wild card, and the result equals the Turing-computable functions — a theorem, on top of which CTT adds the informal identification.

(a) Total, primitive recursive. Factorial is a bounded ladder: $f(0)=1,f(n+1)=(n+1)\cdot f(n)$ — a for loop, always halts. No $\mu$ needed. (b) Partial, needs $\mu$. For $x=9$ it finds $y=3$ and halts. For $x=8$ (not a perfect square) no $y$ satisfies $y^2=8$, so the search runs forever — undefined on non-squares. This partiality is the fingerprint of genuine minimization. Numeric checks: $f(4)=24$; $g(9)=3$; $g(8)$ diverges. ✓

The argument confuses two different claims.

• What CTT actually says: every effectively calculable function is Turing-computable. "Effectively calculable" means computable by a finite mechanical rule with no magic — pencil, paper, patience.
• What the oracle is: a non-mechanical black box. Pressing a button that answers an undecidable question in one step is not a finite mechanical procedure — no pencil-and-paper recipe produces that answer. So $M$ is not an effectively calculable device. Therefore $M$ lies outside the domain CTT quantifies over. CTT says nothing about hypercomputers/oracles; it only claims that among ordinary mechanical processes, Turing machines are maximal. Conclusion: the oracle machine doesn't refute CTT — it just isn't the kind of thing CTT talks about. (If oracles were physically buildable, that would challenge the Strong/physical thesis, but nobody has built one; the Halting Problem remains undecidable for real machines.)

Line 1 (a theorem, proved by diagonalization): no Turing Machine decides the halting problem. Line 2 (apply CTT — the leap): by CTT, any algorithm is realizable as some Turing machine. Contrapositive: if no Turing machine does it, then no algorithm does it — in any model (Python, $\lambda$-calculus, register machine, human with paper). Where CTT enters: exactly at "any algorithm = some Turing machine." Without CTT you could only say "this one model fails"; with CTT the impossibility becomes universal, closing every loophole across all models at once.

Recall the two theses:

• Standard CTT — about what is computable (the set of functions). Widely accepted.
• Strong/physical CTT — about how efficiently: any physically realizable device is simulable by a Turing machine with at most polynomial slowdown. Contested.

(a) Stresses the Strong thesis only. Quantum speed-up is about time, not new functions — quantum machines compute the same set as Turing machines. Whether they beat classical machines by more than polynomial factors is exactly the tension around the Strong thesis (see P vs NP and Computational Complexity). Standard CTT is untouched. (b) Attacks the Standard thesis — this would be genuine hypercomputation, computing a non-Turing function. But no such device has ever been built or shown physically realizable, so Standard CTT stands. (This is the L4 oracle again, dressed up.) (c) Neither thesis is threatened. A polynomial (indeed linear-factor) speed-up is permitted by the Strong thesis; it computes identical functions, just faster. This is ordinary and expected.

Idea: $\lfloor {\log }_{2}x\rfloor$ is "the largest $k$ with $2^k\le x$," equivalently "the smallest $y$ such that $2^{y+1}>x$." That "smallest $y$ with a condition" is precisely a job for minimization: $\ell (x)=\mu y[\text{cond}(x,y)=0],\text{where }\text{cond}(x,y)=\{\begin{array}{ll}0& \text{if }{2}^{y+1}>x\\ 1& \text{otherwise.}\end{array}$ Here $2^{y+1}$ is built by repeated multiplication (primitive recursive), and the comparison $>$ is primitive recursive too, so $\text{cond}$ is computable. Totality: for every $x\ge 1$ there is always some $y$ with $2^{y+1}>x$ (powers of 2 grow without bound), so the search halts on every input — $\ell$ is total. (We could have used bounded recursion, but $\mu$ is the most direct phrasing of "smallest $y$ with…".) Why CTT gives you the Python + Turing machine for free: we exhibited $\ell$ as $\mu$-recursive. The theorem $\{\mu \text{-recursive}\}=\{\text{Turing-computable}\}$ already hands you a Turing Machine. CTT then adds the informal identification: since $\ell$ is effectively calculable, any reasonable model — including Python — computes it. You built it once, in one model, and CTT lets you claim it in all of them. Checks: $\ell (1)=0,\ell (2)=1,\ell (3)=1,\ell (4)=2,\ell (7)=2,\ell (8)=3,\ell (16)=4.$ ✓

Standard CTT is about ::: what is computable (the set of functions). Strong/physical CTT is about ::: how fast — polynomial-slowdown simulability. Which loop type does $\mu$ add over primitive recursion? ::: unbounded while (may not halt) → partial functions. Why is halting's undecidability "universal"? ::: CTT makes "no Turing machine" equal "no algorithm at all". Does an oracle machine refute CTT? ::: No — it isn't a mechanical procedure, so it's outside CTT's scope. $\ell (8)=\lfloor {\log }_{2}8\rfloor$ = ::: 3.