← Chapter 01: Logic and Computability

Quantum Computing · Chapter 01

Logic and Computability

Can mathematical reasoning be given foundations whose reliability can itself be established?

Mithilesh Kumar

→ or Space to advance · N for notes · F for fullscreen

1.1

Formal Reasoning and Decision Problems

We make the rules of proof explicit and ask whether following them, or deciding what they can prove, could be left to a machine.

Axioms, inference rules, and proofs

A proof separates two tasks: choosing starting assumptions, the axioms, and drawing consequences by permitted steps, the rules of inference.

Example (modus ponens): from \(P\) and \(P\to Q\), infer \(Q\).

  • Finding a proof: search a large space of possible arguments.
  • Checking a proof: each line must be an axiom or follow from earlier lines by a rule.

Consequence

A proof in precise notation is a finite string, and checking it is mechanical. Checking shows that the conclusion follows from the axioms, not that the axioms are true.

A proof is a network of justified stepsStatements P and P implies Q lead by modus ponens to Q. Q and Q implies R lead to R. Each edge records a dependency, not a passage of time.A proof is a network of justified stepsPP implies Qmodus ponensQQ implies RR

Consistency

A formal system is consistent if it never proves both a statement \(P\) and its negation \(\neg P\).

Why a single contradiction is fatal: suppose the system proves \(P\) and \(\neg P\). Let \(Q\) be any statement at all.

  1. \(P\) (proved).
  2. \(P\lor Q\), from line 1 (disjunction introduction).
  3. \(\neg P\) (proved).
  4. \(Q\), from lines 2 and 3 (disjunctive syllogism).

So an inconsistent system proves every statement, true or false, and its proofs carry no information. Consistency is the minimum we must demand of a set of rules.

Hilbert’s program

A theorem may speak about infinitely many numbers, but its proof is a finite string of symbols. Proofs can therefore be studied as mathematical objects in their own right.

Hilbert proposed two levels of reasoning:

  • inside the system: formal deductions from the axioms;
  • outside the system: safe, finitary reasoning about those finite strings.

Goal: prove from outside, by finitary means, that no derivation ever ends in a contradiction such as \(0=1\).

If checking is mechanical, a second question follows: can a procedure decide whether a given statement has any proof at all?

Hilbert’s program: proving consistencyInside the formal system, axioms and rules derive valid theorems like 2+2=4. A contradiction like 0=1 must be impossible. Hilbert’s program studies the rules from the outside to prove that the contradiction branch is permanently closed.Hilbert’s program: proving consistencyAxiomsStarting assumptionsdeductionValid Theorems(e.g. 2 + 2 = 4)✓ PermittedContradiction(e.g. 0 = 1)✗ Forbiddenguarantees this branch never occursHILBERT’S METAMATHEMATICS (OUTSIDE VIEW)Analyzes the rules as physical symbol moves to prove that “0 = 1” is impossible.

Checking, searching, and deciding

  • Checking: a rejected argument shows only that this attempt failed, not that \(P\) is unprovable.
  • Searching: check all strings in order of length. If a proof of \(P\) exists, the search finds it and halts.
  • If none exists, the search never halts: there is no last string to rule out.

Definition

A decision procedure for a problem halts on every input with the correct answer, yes or no.

Search is not a decision procedure. To ask whether any method decides, we need a precise definition of “method”.

Checking, searching, and decidingChecking accepts or rejects a supplied record. Search enumerates and checks candidates, looping on failure and stopping on a proof. A decision procedure must also halt with no when no proof exists.Checking, searching, and decidingCHECKCandidateCheckerValid / invalidSEARCHNextcandidateCheckerproves PStop: foundotherwise: keep searchingDECIDESentence PDeciderYes / noalways haltsSearch alone has no stopping condition when no proof exists.

1.2

Models of Computation

We make “mechanical procedure” precise: configurations, transitions, and the Turing machine.

Euclid’s algorithm: correctness

Replace a pair \((a,b)\) by \((b,r)\), where \(r\) is the remainder of \(a\) on division by \(b\); stop when the second entry is \(0\).

\[(48,18)\longrightarrow(18,12)\longrightarrow(12,6)\longrightarrow(6,0).\]

Claim: the greatest common divisor never changes. Write \(a=qb+r\) with \(0\le r<b\).

  • A common divisor of \(a\) and \(b\) divides \(r=a-qb\).
  • A common divisor of \(b\) and \(r\) divides \(a=qb+r\).

So \((a,b)\) and \((b,r)\) have exactly the same common divisors. A quantity preserved by every step is an invariant. At the final pair \((g,0)\), \(\gcd(g,0)=g\); hence \(\gcd(48,18)=6\).

Euclid’s algorithm: termination

The invariant only shows: if the algorithm stops, its answer is right. A loop that repeats \((48,18)\) forever also preserves the gcd, and never answers.

Termination needs a separate argument. At each step the second entry \(b\) is replaced by \(r\), and

\[0\le r<b.\]

A strictly decreasing sequence of nonnegative integers cannot continue forever, so the second entry reaches \(0\).

Two obligations

Every algorithm needs a reason to trust its result (here an invariant) and a reason to expect the result in finite time (here a decreasing nonnegative quantity).

Euclid’s algorithm: what stays fixed, what decreasesThe pairs 48,18; 18,12; 12,6; and 6,0 all have greatest common divisor six, shown as a constant band. Bars below show the second entry falling from 18 to 12 to 6 to zero, the nonnegative measure that proves termination.Euclid’s algorithm: what stays fixed, what decreases(48, 18)(18, 12)(12, 6)(6, 0)invariant: gcd(a,b)=6 at every stepb = 18b = 12b = 6b = 0measure b (nonnegative)b = 0: stopPreservation gives correctness; decrease gives termination.

Configurations and transitions

Pause Euclid’s algorithm at \((18,12)\). To let someone else resume, we must record the numbers in memory and the next instruction; the history is not needed.

A configuration is this complete snapshot. What it contains depends on where we may pause: between whole divisions the pair suffices; mid-division we also need intermediate registers, carries, and the instruction counter.

A transition updates one configuration to the next, and a run is the sequence

\[C_0\longrightarrow C_1\longrightarrow C_2\longrightarrow\cdots\longrightarrow C_{\text{final}}.\]

A deterministic rule fixes the next configuration. It need not fix the previous one: \((48,18)\) and \((30,18)\) both lead to \((18,12)\).

Configurations contain what is needed to continueA configuration consists of stored data, control state, and position in the instructions. A transition produces the next complete configuration, and repeated transitions form a run.Configurations contain what is needed to continueConfiguration Cₜstored datacontrol state / next instructiontransitionConfiguration Cₜ₊₁updated dataupdated control positionA run: C₀→ C₁→ C₂→⋯ (until a halting condition is reached)

Turing machines

“Divide \(a\) by \(b\)” hides many smaller steps. To prove statements about all computations, Turing reduced every step to elementary actions on:

  • a tape of cells, each holding one symbol from a finite alphabet (or the blank \(\square\));
  • a head that reads and writes one cell at a time;
  • a finite control state;
  • a finite rule table: in state \(s\) reading \(a\), write \(b\), move one cell left or right, enter state \(s^\prime\).

A configuration is the tape contents, the head position, and the control state. The machine stops when it enters a halting state.

A Turing machine: tape, head, and finite controlA tape holds blanks and a finite block of ones. The head reads one cell. In state q, reading 1 leaves 1, moves right and remains in q; reading blank enters halt. A universal machine instead reads an encoded rule table and input and simulates it.A Turing machine: tape, head, and finite controlTape: no fixed bound on available cells…□111□…read / write headFinite control: qq, 1→ write 1; right; qq, □→ haltExample rule table (□ = blank)Universal simulationEncoded program Pand input xUniversal machineSimulates the stepsof P on x

Universal computation

A rule table is a finite list of rules, so it can be encoded as a string of symbols.

Universal machine

A universal machine reads the encoded table of any machine \(M\) together with an input \(x\), and imitates \(M\) on \(x\) step by step.

  • Programs are data: a program can take another program, or its own description, as input.
  • Simulation is not prediction: if \(M\) runs forever on \(x\), so does the simulation.
  • Self-reference is a finite procedure reading a finite string; nothing paradoxical is involved yet.

The halting argument in Section 1.3 uses exactly this ability of programs to inspect programs.

1.3

Computability and Its Limits

We justify the Turing machine as a model, then exhibit a question no algorithm can decide and trace its consequences for logic.

The Church–Turing thesis

Turing machines, lambda calculus, recursive functions, register machines and programming languages simulate one another step by step, so they compute the same functions. This equivalence is a theorem.

Church–Turing thesis

Any function computable by an effective mechanical method is computable by a Turing machine.

It is a thesis because “effective method” is informal. Its use: if no Turing machine solves a problem, no algorithm does.

Formal model equivalence and the Church–Turing thesisTuring machines, lambda calculus, and recursive functions compute the same class of functions. Their formal equivalence is proved. Identifying this class with every effective mechanical procedure is the Church–Turing thesis.Formal model equivalence and the Church–Turing thesisTuring machinesLambda calculusRecursive functionsSame computable functions: equivalence of formal modelsInformal notion of an effective procedureChurch–Turing thesisEquivalence concerns computability, not equal running time.

Computability is not efficiency

ComputabilityEfficiency
QuestionCan the function be computed at all?How much time and memory are needed?
Subject ofThe Church–Turing thesisComplexity theory
Quantum computersCompute the same functionsMay need fewer resources for some problems

In the standard quantum model each operation is a matrix acting on a vector of amplitudes. A classical machine can multiply such matrices, so it can simulate a quantum computer in principle.

The simulation may be astronomically slow: \(n\) qubits are described by about \(2^n\) numbers. Quantum computers therefore do not compute uncomputable functions; their promise concerns resources.

The halting problem

Given a program \(P\) and an input \(x\), will the run eventually stop? For particular programs we can often tell: Euclid’s algorithm halts by the termination argument.

Running \(P\) for a fixed number of steps is not a general test. If it is still running at the deadline, it may halt at the next step; running reports “halted” or “not yet”, never “never”.

Theorem (Turing, 1936)

There is no algorithm \(H\) that, for every program \(P\) and input \(x\), halts and correctly answers whether \(P\) halts on \(x\).

What is excluded is one total, always-correct method. Proving that individual programs halt, and analysers that may answer “unknown”, remain possible.

Proof that halting is undecidable

  1. Suppose \(H(P,x)\) always halts and says correctly whether \(P\) halts on \(x\).
  2. Build \(D(p)\): run \(H(p,p)\); if it says “halts”, loop forever; if it says “does not halt”, stop.
  3. \(D\) is a program, so it has a description \(d\). Consider the run \(D(d)\).
  4. If \(H(d,d)\) says “halts”, then \(D(d)\) loops; if it says “does not halt”, then \(D(d)\) stops.
  5. Either answer is wrong, so the assumption fails: no such \(H\) exists.

Every part of \(D\) except \(H\) is ordinary programming, so the only assumption that can fail is the existence of \(H\).

The halting contradiction: run D on its own descriptionAssume H always halts and correctly predicts halting. Program D calls H(p,p) and does the opposite. With p equal to d, the description of D, either prediction about D(d) is contradicted by its prescribed behavior.The halting contradiction: run D on its own descriptionAssume H always halts and correctly predicts halting.PROGRAM D(p)Input pCall H(p,p)“halts”Loop forever“does not halt”HaltD follows fixed instructions: it opposes the prediction.Now set p=d, the description of D.H(d,d) predicts this very run; either answer is contradicted.

Undecidability and incompleteness

Two different limits, on two different kinds of object:

  • A problem is undecidable if no algorithm halts with the correct yes/no answer on every input.
  • A formal theory is incomplete if some sentence \(P\) has neither a proof of \(P\) nor a proof of \(\neg P\) in it.

Neither follows from an unsuccessful search: a failed search only shows that one attempt failed.

The two limits are linked: if a suitable theory of arithmetic were complete, we could decide halting. Since halting is undecidable, such theories must be incomplete.

Undecidability and incompleteness concern different objectsUndecidability excludes an always-correct total algorithm for a specified decision problem. Incompleteness says that in a consistent effective theory with enough arithmetic there is a sentence P such that neither P nor not P has a proof.Undecidability and incompleteness concern different objectsUNDECIDABILITYObject: a decision problemNo algorithm always haltswith the correct yes/no answer.INCOMPLETENESSObject: a fixed theory TFor some sentence P,T proves neither P nor ¬ P.Example: the general halting problemT: consistent, effective,and sufficiently strong for arithmetic

Why a complete theory would decide halting

Take a theory of arithmetic whose axioms a program can list, and suppose it proves \(P\) or \(\neg P\) for every sentence \(P\).

  1. For a machine \(M\) and input \(x\), the claim “\(M\) halts on \(x\)” can be written as a sentence about integers.
  2. Enumerate all proofs until one proves this sentence or its negation. Completeness guarantees that the enumeration stops.
  3. If the theory proves no false sentence, the proof found gives the correct answer.
  4. This would decide halting, which is impossible. So no such theory is complete.

Step 3 needs more than consistency: a consistent theory might still prove “\(M\) halts” for a machine that never halts. Rosser’s refinement removes this extra assumption; the result is the Gödel–Rosser theorem.

The incompleteness theorems

Gödel–Rosser theorem (stated without proof)

A theory that is consistent, has axioms a program can list, and can express basic arithmetic is incomplete: some arithmetic sentence \(P\) has neither \(P\) nor \(\neg P\) provable.

Adding the undecided \(P\) as a new axiom settles \(P\), but the enlarged theory is again consistent and listable, so the theorem yields a new undecided sentence. Each hypothesis matters: weak theories can be complete, and an inconsistent theory proves everything.

Gödel’s second incompleteness theorem

Under the same conditions, a consistent theory that can describe its own proof checking cannot prove the sentence expressing its own consistency.

This answers Hilbert’s program: the consistency proof cannot be carried out inside the theory itself. A stronger theory can prove it, but then we rely on the stronger axioms.

1.4

From Computability to Reversibility

For problems we can solve, we ask what each step of a computation does to the information it is given.

Deterministic and reversible transitions

Deterministic: every running configuration has exactly one successor. That says nothing about predecessors. In Euclid’s algorithm, every pair

\[(18q+12,\;18)\longrightarrow(18,12),\qquad q=1,2,3,\ldots\]

so from \((18,12)\) we cannot tell whether we came from \((30,18)\), \((48,18)\), or another pair: the quotient \(q\) is lost.

A transition rule is one-to-one if different configurations always have different successors. If it also reaches every configuration of a fixed set, it is a bijection, and running it backward is again a deterministic rule.

Compare an invertible matrix. Quantum steps will be invertible maps that also preserve length.

Deterministic does not imply reversibleTwo distinct configurations may each have one successor yet share that successor, preventing unique reversal. A one-to-one transition retains distinct resulting states so each has a unique predecessor.Deterministic does not imply reversibleDeterministic, many-to-oneOne-to-one, reversible on its imageABCABA′B′C alone does not identify A or B.Each result identifies its predecessor.

Information loss in computation

AND on two bits returns \(0\) on three inputs. If the gate keeps only its answer, an output \(0\) cannot tell us which input occurred.

\(x_1x_2\)AND
000
010
100
111

Keep the input and write the answer into an extra target bit \(t=0\). Distinct inputs now give distinct outputs:

\((x_1,x_2,t)\)after
000000
010010
100100
110111

In general, replacing \(f(x)\) by \((x,f(x))\) never merges two inputs, even when \(f\) is many-to-one.

Why preserve information?

Keeping \((x,f(x))\) is not yet a computer: Chapter 2 must build such maps from reversible gates and clear temporary workspace without erasing it.

The reason to try is physical. The laws governing isolated quantum systems lose no information between observations: their evolution can be run backward.

A computer built from such systems must therefore reach its answers through reversible transformations.

From this chapter to the next

The question changes from “Can this be computed at all?” to “How can it be computed while preserving information?”

Retaining inputs preserves the distinctions AND discardsOrdinary AND maps inputs 00, 01, and 10 to zero and 11 to one. Retaining x and y and placing their AND into a target initially zero gives distinct three-bit outputs. The full reversible update is x,y,t to x,y,t XOR xy.Retaining inputs preserves the distinctions AND discardsRetain only AND(x,y)Retain inputs and update a target0001101101000000010010100100110111Shown: target t initially 0Full update: (x,y,t)→(x,y,t⊕ xy); applying it twice restores the input.

Summary

  1. A proof is a finite object that a procedure can check; finding a proof is a different task, and deciding provability is a third.
  2. Configurations and transitions make “procedure” precise; a universal machine runs every program, and the Church–Turing thesis identifies these machines with effective methods.
  3. No algorithm decides halting; consistent, listable theories of arithmetic are incomplete and cannot prove their own consistency.
  4. Deterministic steps can merge histories. Keeping the input, \((x,f(x))\), computes without losing information, which is what quantum evolution will require.

Notes