Did the Difference Engine make a difference?

Steampunk! (photo: Kyle Cassidy)

I have been reading a few steampunk novels lately – I have a great fondness for the genre. Charles Babbage’s planned “Difference Engine” and “Analytical Engine” always play a large part in the fictional universe of such books. However, as Francis Spufford has pointed out, this does rely on some counterfactual history.

Reconstructed “Difference Engine No. 2” in the Science Museum, London (photo: “Geni”)

Babbage never completed any of his major devices, although redesigned working difference engines were built by Per Georg Scheutz (1843), Martin Wiberg (1859), and George B. Grant (1876). With much fanfare, the Science Museum, London reconstructed Babbage’s “Difference Engine No. 2” between 1985 and 2002, making only essential fixes to the original design – and it works! However, the pinnacle of this kind of technology was probably the beautiful handheld Curta calculator, produced in Liechtenstein by Curt Herzstark from 1947.

Curta Type I mechanical calculator (photo: Larry McElhiney)

The world’s first programmable digital computer was in fact built four years before the Curta, in 1943, by English electrical engineer Tommy Flowers. The wartime secrecy associated with his work has kept this monumental achievement largely in the dark.

Colossus in action at Bletchley Park in 1943 (photo: National Archives)

The significance of the Colossus has also been obscured by a kind of “personality cult” built up around Alan Turing, much like the one built up around Babbage. Turing was one of a number of people who contributed to the design of the cryptographic “Bombe” at Bletchley Park, and Turing also did important theoretical work – although the fundamental result in Turing’s 1936 paper, “On Computable Numbers, with an Application to the Entscheidungsproblem” was not actually new, as is revealed on the second page of Turing’s paper, where Turing admits “In a recent paper Alonzo Church † has introduced an idea of ‘effective calculability,’ which is equivalent to my ‘computability,’ but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem ‡. The proof of equivalence between ‘computability’ and ‘effective calculability’ is outlined in an appendix to the present paper.”

Turing’s life was more colourful than either Church’s or Flowers’s, however, and this may be why he is far more famous. In a similar way, Babage lived a more colourful life than many of his contemporaries, including his collaboration with the forward-thinking Countess of Lovelace.

1: Charles Babbage, 2: Augusta Ada King-Noel (née Byron, Countess of Lovelace), 3: Alonzo Church, 4: Alan Turing, 5: Tommy Flowers

The chart below (click to zoom) puts the work of Babbage and Flowers in a historical context. Various devices are ranked according to their computational power in decimal digits calculated per second (from 1 up to 1,000,000,000,000,000). Because this varies so dramatically, a logarithmic vertical scale is used. The Colossus marks the beginning of a chain of “supercomputers,” often built for government use, with power doubling every 1.84 years (pink line). Starting with the Intel 4004 in 1971, there is also a chain of silicon chips, with power doubling every 1.74 years (blue line). At any given point in time, supercomputers are between 1,000 and 3,000 times more powerful than the chips, but the chips always catch up around 20 years later. The revolutionary PDP-8 of 1965 sits between the two chains.

One of the things that stand out on this chart is the gap between Babbage’s Difference Engine and the later digital computers – even the Colossus was around 280 times more powerful than the Difference Engine (carrying out a simpler task much more quickly). Steampunk fiction often suggests that steam power would have made the Difference Engine faster. However, it turns out that the mechanism jams if it is cranked too quickly. Complex mechanical calculating devices simply cannot operate that fast.

Morse telegraph key (photo: Hp.Baumeler)

In fact, Charles Babbage may actually have distracted people from the way forward. Samuel Morse’s improved telegraph was officially operational in 1844. It used electromechanical principles that were also used in the Colossus a century later. Electricity also has the advantage of travelling at the speed of light, along wires that can be made extremely thin. What might the world have been like had electromechanical computing developed earlier? The chart also shows the 1964 fluidic computer FLODAC. This was a fascinating idea that was abandoned after a successful proof of concept (although a 1975 film portrayed it as the future). What if that idea had been launched in Victorian Britain?

---

Church and Turing

Alonzo Church (left) and Alan Turing (right)

Alan Turing is no doubt the most well-known of all computer scientists. His Turing machine is justly famous, and the video below shows a really cool Lego version of it.

However, it is not widely known that the fundamental result in Turing’s 1936 paper (“On Computable Numbers, with an Application to the Entscheidungsproblem” – with errors later corrected in 1937: i, ii, iii) was not actually new. This is revealed on the second page of Turing’s paper, where Turing admits “In a recent paper Alonzo Church † has introduced an idea of ‘effective calculability,’ which is equivalent to my ‘computability,’ but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem ‡. The proof of equivalence between ‘computability’ and ‘effective calculability’ is outlined in an appendix to the present paper.”

It seems that Max Newman encouraged Turing to explain how his work related to the result that Alonzo Church had already obtained, lobbied the Secretary of the London Mathematical Society to still permit publication of Turing’s paper, and arranged for Turing to go to Princeton, where Church would be his PhD supervisor (Church also supervised 34 other students). It’s a terrible feeling for a student to be “gazumped” like that, and invaluable to have helpful people backing you up. Turing went on to have a colourful, but relatively short, life. Church lived to 92, but was staid in comparison.

Church’s notation, the lambda calculus, has been quite influential, spawning programming languages such as Lisp and Haskell, as well as more theoretical work. The fundamental feature of lambda calculus, the anonymous function written function (x) { e }, has been incorporated into many other programming languages as well. Consider the following code in R, for example:

i <- function (x) { x }
k <- function (x) { function (y) { x } }
s <- function (x) { function (y) { function (z) { x(z)(y(z)) } } }
y <- function (f) { (function (x) { f(x(x)) }) (function (x) { f(x(x)) }) }

Notice that functions can themselves be arguments to other functions, and in x(x), a function is applied to itself.

The object i is the identity function, so that i(3) reduces to 3. The expressions k(3)(4) and s(k)(k)(3) also reduce to 3. The object y is the Y combinator, with y(k(3)) reducing to 3, and y(i) generating infinite recursion. The following code uses y to generate the factorial function:

fact <- y (function (g) { function (x) { if (x == 0) 1 else x * g (x - 1) } })
fact (3)

The appendix that Turing was forced to write was perhaps the most significant aspect of his 1936 paper. Showing that his definition of computability was equivalent to that of Church led to the Church–Turing thesis – the idea that that is the only kind of computability (at least on numbers). Independently of Turing, Emil Post produced another equivalent form of computability in 1936. Yet another form came out of Russia. Even Conway’s Game of Life (below) turns out to capture the same kind of computability, though in an inherently parallel form:

See more on the Church–Turing thesis at plato.stanford.edu. There was also a series of interesting talks presented on Church and Turing in 2012, including this one by Philip Wadler:

While the lambda calculus was probably the version of computability with the largest impact on programming languages, the more practical Von Neumann architecture probably had the largest impact on hardware design. It is difficult to imagine what the world would look like without those two concepts.

---