bits.

FREE CONTRIBUTION CHRONOLOGY · 1837–1843

The general machine

What minimum parts let one machine perform many different computations?

The historical question

The Analytical Engine separated storage, arithmetic, control cards, variable cards, sequencing, and output. Lovelace traced how operations could move symbolic values through time.

A machine is general-purpose when stored state and a sufficiently expressive sequence of operations can describe many procedures.

Trace a general procedure

A proposed general machine needs a representation of values, operations on those values, and a way to choose the next operation. In a modern teaching model, compute the sum of the first n positive integers using state (i, total). Begin with i = 1 and total = 0. While i ≤ n, add i to total and increment i. For n = 3, the states after each iteration are (2,1), (3,3), and (4,6).

The loop invariant is total = 1 + … + (i−1). Initialization makes the empty sum zero. Each iteration extends the sum by exactly the next term. On exit, i = n+1, so total is the required sum. A finite sequence of arithmetic instructions is not enough to explain the loop: the control model must represent repetition and its stopping condition.

Babbage’s proposed Analytical Engine and Lovelace’s 1843 Notes are important because they make operations, stored quantities, and their sequencing inspectable. Keep design, published program plan, and working implementation separate. The proposed use of operation cards is not the same architecture as storing writable instructions alongside data in electronic memory. Credit also belongs to collaboration and to earlier program plans, rather than an unqualified contest for a single first programmer.

What the evidence does not establish

Use the precise claim that Lovelace published a detailed program/table for a proposed engine; treat the label “first programmer” as a question of scope, evidence, and definition.

Reconstruction exercise

Trace the summation algorithm for n = 0 and n = 4. State a precondition on n and explain how a missing increment changes the behavior.

Worked solution

Require n to be a nonnegative integer. For 0, the loop does not execute and returns 0. For 4, the totals are 1,3,6,10. Without incrementing i, the condition remains true for positive n and the loop does not terminate. The invariant alone establishes partial correctness; termination additionally depends on progress toward the bound.

Test the limits and transfer the idea

1. Trace and proof · allow 35 minutes

Carry a loop invariant through changing representations

Use exact nonnegative integers. To compute aⁿ, initialize result=1, base=a, exponent=n. While exponent>0: if exponent is odd, multiply result by base; then square base and replace exponent by floor(exponent/2). Trace a=3,n=5. Prove the invariant result×base^exponent=aⁿ across both parity cases and justify termination. Explain what changes on a finite-word machine.

Get a starting hint

Write an odd exponent as 2k+1 and an even exponent as 2k before evaluating an iteration.

Compare your reasoning with the worked solution

States (result,base,exponent) are (1,3,5), (3,9,2), (3,81,1), then (243,6561,0). For even exponent 2k, replacing base by base² and exponent by k preserves base^(2k). For odd 2k+1, moving one base factor into result leaves an even exponent, and the same identity applies. At exponent zero, the invariant gives result=aⁿ. Every positive integer exponent becomes a smaller nonnegative integer after division by two, proving termination. With finite words, multiplication may wrap, trap or lose exactness, so the exact-integer proof must be adapted to the arithmetic contract. This is a modern algorithm used to study general control; Babbage and Lovelace's surviving design records do not by themselves establish this precise implementation on the proposed Engine.

Check your reasoning

  • Traces all states through result 243.
  • Proves both parity cases and a decreasing termination measure.
  • Separates exact arithmetic, machine arithmetic and historical attribution.

2. Source-based argument · allow 25 minutes

Distinguish a program plan from an operational machine

An exhibit contains a published operation table, a mechanical drawing and a later working replica. A caption says they prove the original full machine executed the table when it was published. Explain what each artifact can establish, and construct a stronger evidence chain for actual execution. Use the distinction among the Analytical Engine proposal, Lovelace's 1843 Notes and later museum interpretation without awarding an unqualified first-programmer title.

Get a starting hint

Design feasibility, publication and witnessed historical operation are separate assertions.

Compare your reasoning with the worked solution

The table can establish that a particular procedure was described in the published artifact; the drawing documents a proposed mechanism; the replica can demonstrate the behavior of its reconstruction under observed conditions. None alone proves that the original full machine operated at the table's publication date. A stronger chain would identify a contemporary implemented machine configuration, the actual control/data preparation, dated operational logs or independent witness reports, and outputs checked against the described task. A replica also needs documentation of substitutions and inferred missing details. Museum and library catalog entries are later curatorial interpretations of primary objects. The historical achievement of a detailed program plan remains substantial without converting it into a claim of completed execution or exclusive invention.

Check your reasoning

  • Assigns a bounded evidentiary role to each artifact.
  • Specifies records required for actual historical execution.
  • Keeps primary objects distinct from later catalog interpretation.

Check your understanding

Why is a loop invariant insufficient to establish total correctness?

  • It applies only to hardware
  • Termination must also be established
  • It prevents arithmetic operations
Explanation

Require n to be a nonnegative integer. For 0, the loop does not execute and returns 0. For 4, the totals are 1,3,6,10. Without incrementing i, the condition remains true for positive n and the loop does not terminate. The invariant alone establishes partial correctness; termination additionally depends on progress toward the bound.

Sources and further reading