Number the Turing machines in a fixed order that an algorithm can list
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch What quantum computers can compute efficiently
Problem
Number the Turing machines M1,M2,M3,… in a fixed order that an algorithm can list. No algorithm decides, for every n, whether Mn halts when started on a blank tape; this form of the halting problem is undecidable. Define the unary language L={1n:Mn halts when started on a blank tape} over the one-letter alphabet {1}, so that at length n there is exactly one candidate string, 1n.
((a)) Exhibit a family of circuits {Cn}n≥1, one per input length, each of size O(1), that decides L: Cn outputs 1 if 1n∈L and 0 otherwise.
((b)) Explain why no algorithm running in time polynomial in n can output the description of Cn given n in binary, i.e. why {Cn} is not a uniform family.
((c)) State which thesis, the Church-Turing thesis or its extended form, this example might seem to threaten, and explain why it in fact threatens neither.