Christmas Trilogy 2012 Part II: Charles and Ada: A tale of genius or of exploitation?

This year Ada Lovelace Day, a celebration of women in STEM (science, technology, engineering and mathematics) fuelled by the Finding Ada website and twitter account took off big time. Now I have nothing against this celebration and have actively supported it on this blog for the last three years; writing about Emmy Noether in 2010, a quartet of lady astronomers in 2011 and the first female professor at a European university, Laura Brassi, in 2012. I have also posted on other women in the history of science on other occasions. This year I, by chance, also attended, but did not participate in, the edit-thron for STEM women on Wikipedia held at the Royal Society. As I have already said I have nothing against this celebration but as a historian of mathematics and computing each time I do so I have very major misgivings about the organisers choice of figurehead, Ada Lovelace. These qualms were strengthened this month on the tenth, Ada’s birthday, as an echo of Ada Lovelace Day set off a flurry of biographical posts throughout the Intertubes, some of them old and merely linked, others freshly written for the occasion. All of them however had one thing in common, they were not written from original or even well researched secondary sources but simply regurgitated older fundamentally flawed largely mythical short biographies. There is nothing new in what I’m going to say now, in fact I’ve blogged about it before as has one of The Guardian’s excellent lady historians of science Rebekah “Becky” Higgitt. Even the much-maligned Wikipedia gets it largely right in its Ada Lovelace article. All of the short biographies state clearly that Ada was a mathematician and “the first computer programmer”.  Both statements are wrong. So what is the truth?

Ada, the daughter of Annabelle Milbanke and George Byron, was motivated to learn mathematics as a child (unusually for a women in the nineteenth century) by her mathematics fan mother to try to prevent her growing up to be like her “mad, bad and dangerous to know” poetic father. A stultifying logical education rather than a stimulating poetic one! Ada had various maths tutors in her youth including the aging radical reformer William Frend, Augustus De Morgan’s father in law and her mother’s old childhood tutor. None of these really managed to instil any real enthusiasm or ability for mathematics in the young Ada. Later as a young lady she became acquainted with both Mary Somerville, the mathematical translator and science populariser and Charles Babbage and became fascinated with the mathematical sciences. She received some informal tuition from Somerville who became her mentor and role model. Later determined to finally get to grips with the discipline she succeeded in persuading De Morgan, she was acquainted through his wife Sophia, Frend’s daughter, to become her maths tutor in an informal correspondence course. The surviving letters of their mathematical correspondence clearly show that although Ada is obviously the possessor of a bright and inquisitive mind she never really grasped several important fundamental mathematical concepts and her acquisition of the secrets of mathematics never progressed beyond that of a failed first year undergraduate. To call Ada a mathematician is a perversion by any stretch of the imagination. As Dorothy Stein, who has analysed the De Morgan – Ada mathematical correspondence in detail, puts it in her excellent biography Ada:  A Life and a Legacy (1985):

At twenty-eight, […] and after ten years of intermittent but sometimes intensive study, Ada was still a promising “young beginner”.

Having failed to master mathematics Ada now turned her attention to the occupation of Mary Somerville, her mentor, scientific translating. Quoting Stein again:

Translation was a good way to begin, whether or not original contributions were to follow. Mary Somerville, De Morgan and Babbage himself had all begun their published careers as translators. There was no reason why she could not proceed on a course at least as successful and rewarding as those of Mary Somerville and her mother’s friends Harriet Martineau and Anna Jameson.

In 1840 Babbage held a series of public lectures before an audience of eminent Italian philosophers and men of science on his Analytical Engine in Turin. This was a publicity exercise and Babbage’s plan was that the most eminent attendee, Baron Plana, should publish an account of the lectures creating much needed publicity for his cash strapped project. Plana declined and Babbage had to content himself with an account written in French by the young unknown military engineer, Captain Luigi Menabrea (who in a strange twist of fate would later become prime minister of Italy).  It was this document, which Ada, a long-time fan of Babbage’s calculating machines, chose at the suggestion of Charles Wheatstone, Babbage’s friend, as her first (and last) scientific translation project. (As a historian of science and a big fan of polymaths I find it fascinating that the physicist Wheatstone universally known by school kids studying physics for his Wheatstone Bridge (which he didn’t invent) was the inventor of the English Concertina.)

When he became aware, after the event, of Ada’s translation Babbage, never one to miss a trick, realised he had a great opportunity for a publicity stunt and suggested that Ada should garnish her work, in the manner of Somerville’s Laplace translation, with her own notes on the Analytical Engine; a suggestion that the flattered young lady grasped with alacrity. It is obvious from the extensive correspondence that Babbage controlled and supervised every single point and comma of the infamous Lovelace notes and it difficult to say how much of them is original Ada and how much Babbage expressed through a mouthpiece. Even some of the more interesting speculative ideas contained in the notes can be shown to be paraphrases of ideas first muted in earlier Babbage publications such as his Economy of Machinery and Manufactures (1832) and his Ninth Bridgewater Treatise (1837).

On the question of who the first computer programmer was, there is no confusion what so ever and it was not Ada Lovelace. The Menabrea Memoir that Ada had translated already contained examples of programmes for the Analytical Engine that Babbage had used to illustrate his Turin lectures and had actually developed several years before. The notes contain further examples from the same source that Babbage supplied to the authoress. The only new programme example developed for the notes was the one to determine the so-called Bernoulli numbers. Quite who contributed what to this programme is open to dispute. In his autobiography, written several years after Ada’s death, Babbage claims that Ada suggested the programme, which he then wrote, although noting that she had spotted a serious error in the original. The correspondence suggests that Ada was much more actively involved in the development of the programme and should perhaps be given more credit than Babbage allowed her. Whatever the truth of the matter Ada Lovelace was neither a mathematician nor the first computer programmer.

Ada was not some sort of mathematical genius who conceived the first computer programme but was rather an intelligent but rather confused young lady who was exploited by Charles Babbage to gain publicity for his out of control megalomaniac computer project. However Ada’s annotated translation was elegantly written, as she, despite her mother’s best efforts, seems to have inherited some of her father’s poetic genius. It would in no way be amiss to describe Ada as a female science populariser or science communicator however if one were to choose one of these as a role model for women in STEM careers then Mary Somerville would be a much more obvious choice as her annotated Laplace translation was much more significant and immensely more influential than Ada’s memoir.

In general I find it sad that the organisers of Ada Lovelace Day didn’t choose one of the many real women mathematician and scientists out of history as their figurehead rather than a woman who was neither.

 

The Cult of St Alan of Bletchley Park

I realise that to rail against anything published in the Daily Fail is about as effective as pissing against the wind in a force 8 gale but this article on Alan Turing got so up my nose that I have decided to strap on my bother-boots of historical criticism and give the author a good kicking if only to assuage my own frustration. It won’t do any good but it might make me feel better.

Before I start in on a not so subtle demolition job, I should point out that I’m actually a Turing fan who has read and absorbed Andrew Hodges’ excellent Turing biography[1] as well as many books and articles on and by Turing. I have seriously studied his legendary paper on the Entscheidungsproblem[2], I have a copy sitting on my bookshelf, which I understand thoroughly including its significance for Hilbert’s Programme, which the Mail’s journalist almost certainly does not. If I here seem to be seriously challenging Turing’s claims to scientific sainthood it is only in the interests of historical accuracy and not out of any sense of antipathy to the man himself, who would definitely be one of my heroes if I went in for them.

The Mail article opens with a real humdinger of a claim that is so wrong it’s laughable:

Own a laptop, a smartphone or an iPad? If so, you owe it to a man many of us have never heard of – a genius called Alan Turing. ‘He invented the digital world we live in today,’ says Turing’s biographer David Leavitt in a new Channel 4 drama-documentary about the brilliant mathematician.

Sorry folks Alan Turing did not invent the digital world we live in today. In the 1930s Turing was one of several meta-mathematicians who laid the theoretical foundations for computability and although his contributions were, viewed from a technical standpoint, brilliant we would still have had the computer revolution if Alan Turing as an undergraduate had turned his undoubted talents to deciphering ancient Sumerian clay tablets instead of to solving meta-logical problems. The German computer pioneer Konrad Zuse designed and built functioning digital computers in the 1930s and 40s without, as far I know, ever having heard of Turing. Zuse was an engineer and not a mathematician and approached the problem from a purely practical point of view. The American engineer Vannevar Bush built a highly advanced analogue computer, his Differential Analyser, to solve differential equations in 1927 when Turing was still at school. Claude Shannon who laid the foundations of digital circuit design was one of Bush’s graduate students. All three American groups, which developed digital computers in the late 193os and early 1940s, Atanasoff and Berry in Iowa, Aiken in Harvard and Eckert and Mauchly in Pennsylvania all referenced Bush when describing their motivations saying they wished to construct an improved version of his Differential Analyser. As far as I know none of them had read Turing’s paper, which is not surprising as Turing himself claimed that in the 1930’s only two people had responded to his paper. The modern computer industry mainly developed out of the work of these three American groups and not from anything produced by Turing.

Turing did do work on real digital computers at Bletchley Park in the 1940s but this work was kept secret by the British government after the war and so had no influence on the civil development of computing in the 1950s and 60s. Turing like many other of the computer pioneers from Bletchley started again from scratch after the war but due to their delayed start and underfunding they never really successfully competed with the Americans. We now turn to Bletchley Park and Turing’s contribution to the Allied war effort. The Mail writes:

Ironically, the same society that hounded him to his death owed its survival to him. For during the Second World War it was Turing who pioneered the cracking of Nazi military codes at Bletchley Park, allowing the Allies to anticipate every move the Germans made.

The first sentence is a reference to Turing’s suicide caused by his mistreatment as a homosexual, which I’m not going to discuss here other than to say that it’s a very black mark against my country and my countrymen. We now come to a piece of pure hagiography. The cracking of the Germany military codes was actually pioneered by the Poles before Bletchley Park even got in on the act. It should also be pointed out that Turing was one of nine thousand people working in Bletchley by the end of the War. Also he was only in charge of one team working on one of the codes in use, the navel naval Enigma, there were several other teams working on the other German codes. Turing was one cog in a vast machine, an important cog but a long way from being the whole show. The Mail next addresses Turing’s famous paper:

‘While still a student at Cambridge he wrote a paper called Computing Machinery, in which all the developments of modern computer science are foretold. If you take an iPhone to pieces, all the parts in there were anticipated by Turing in the 1930s.’

He wasn’t a student but a postgraduate fellow of his college. The title of the paper is On Computable Numbers, with an Application to the Entscheidungsproblem. It outlines some of the developments of modern computing but not all and no he didn’t anticipate all of the parts of an iPhone. Apart from that the paragraph is correct.

Turing’s outstanding talents were recognised at the outbreak of war, when he was plucked from academic life at Cambridge to head the team at Bletchley Park, codenamed Station X. They were tasked with breaking the German codes, transmitted on complex devices called Enigma machines, which encrypted words into as many as 15 million million possible combinations.

‘Turing took one look at Enigma and said, “I can crack that,”’ says Sen. ‘And he did.’ Part of Turing’s method was to develop prototype computers to decipher the Enigma codes, enabling him to do in minutes what would take a team of scientists months to unravel. It was thanks to him that the movements of German U-boats could be tracked and the battle for control of the Atlantic was won, allowing supplies to reach Britain and saving us from starvation.

Turing was not “plucked from academic life”; interested in the mathematics of cryptology Turing started working for the Government Code and Cypher School already in 1938 and joined the staff of Bletchley Park at the outbreak of war. The department he headed was called Hut 8. With reference to the computers developed in Bletchley, as I have already said in an earlier post Turing was responsible for the design of special single purpose computer, the Bombe, which was actually a development from the earlier Polish computer the Bomba and had nothing to do with the much more advance and better known Bletchley invention, the Colossus. The second paragraph is largely correct.

The life and work of Alan Turing and the role of Bletchley Park in the war effort are both important themes in the histories of science, mathematics and technology and can certainly be used as good examples on which to base popular history but nobody is served by the type of ignorant, ill-informed rubbish propagated by the Daily Fail and obviously by the Channel 4 documentary that they are reporting on, which is obviously being screened tonight. My recommendation don’t watch it!

 

---

[1] Andrew Hodges, Alan Turing: The Enigma, Simon & Schuster, 1983.

[2] Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2 ser. vol. 42, (1936 – 37), pp. 230 – 265.

Ich bin a Gastblogger III: Drinking from the same well

I’m an alien

I’m a legal alien

I’m an Englishman in Nürnberg¹

 

As an English historian of mathematics living in Germany another question that I have had put to me several times by those with somewhat more knowledge of the history of mathematics is, “who invented logarithms the Scottish aristocrat John Napier or the Swiss instrument maker Jost Bürgi?”…..

 

A Christmas Trinity II: Charlie, Ivor, Robert and me.

Charles Babbage, who was born on 26^th December 1791¹, is famous as a pioneer in the history of the computer, a fame that is to some extent exaggerated as his work, although spectacular (his analytical engine was a full von Neumann machine more than a century before von Neumann became famous for defining the same), had no real influence on the later actual development of the computer, the later inventors only becoming aware of Babbage’s work after the fact.

However Babbage is significant in the history of science and technology not only for his calculating engines. He was for a number of years the holder of the Lucasian Chair for mathematics at Cambridge, whose current holder is Michael Green the string theorist and whose previous occupants include Stephan Hawking the cosmologist, the physicists Paul Dirac and Gabriel Stokes, the astronomer and optical physicist George Biddell Airy (a friend of Babbage), its original occupant Isaac Barrow and his successor Isaac Newton. Babbage was also instrumental in the founding of a number of scientific societies most notably the Royal Astronomical Society and the British Society for the Advancement of Science.

As well as working on his calculating engines he worked as a scientific advisor to governments and rulers throughout Europe and distinguished himself as an inventor. One Internet site has the following list of his inventions, “the dynamometer, standard railroad gauge, uniform postal rates, occulting lights for lighthouses, Greenwich time signals, heliograph ophthalmoscope. He also had an interest in cyphers and lock-picking.” For me the most fascinating fact is that he also invented that essential stage prop of Hollywood westerns the cowcatcher! This was actually conceived to push aside small obstacles on the tracks and not cows!

Over the years Babbage has gained a reputation as an English eccentric based largely on his own autobiography Passages from the Life of a Philosopher (1864) and in particular for the often-quoted chapter XXVI therein Street nuisances, which he even published as a separate pamphlet. Here Babbage complains bitterly about the noise pollution produced by street musicians and street criers, to quote just one such passage:

It is difficult to estimate the misery inflicted upon thousands of persons and the absolute pecuniary penalty imposed upon multitudes of intellectual workers by the loss of their time, destroyed by organ-grinders and other similar nuisances.

He is here complaining the he and others like him are unable to work because of the noise produced by street musicians. Such passages and others like them from this chapter are quoted as evidence that Babbage was at best an eccentric and at worst a loony. I beg to differ.

Another noted British eccentric of more recent vintage was the Scottish poet, musician, storyteller and educationalist Ivor Cutler whose quirky humour and fascinating ditties enriched my childhood and my youth. I still own and love his wonderful LP Ludo. Cutler was much loved by John Peel and played a role in the Beatles Magical Mystery Tour film. He is said to be probably the only artist to have loyal audiences on BBC Radios 1, 2, 3 and 4. Cutler was notorious for his many eccentricities and in particular for his passionate support of the Noise Abatement Society. He would ask to see the manager in cafes and bars with background music and complain that the sound was hurting his sensitive ears. He always won and got the offending sound system turned off. In supermarkets with music systems he would also summon the manager and complain that he was unable to think about what he wished to purchase because of the intruding noise of the background music.

Robert Fripp legendary guitarist of King Crimson is another Englishman who has been labelled an eccentric. A man whose scorching lead solos have graced no only his own music but also such classics as Bowie’s Heroes or the new Grinderman single defies the etiquette for rock lead guitarists and plays sitting down. In a business whose public image in defined by the catchphrase “sex and drugs and rock and roll” Fripp is an abstinent intellectual who read the Financial Times and pontificates on the morals of the music business. Fripp writes a very entertaining Internet road diary and here he comments sarcastically on the Noise Pollution Units (music systems) at the breakfast troughs in the hotels where he stays whilst underway. He has taken to carrying his so-called noisebusters, an ipod loaded with suitable classical music of his own choosing.

I too have a local reputation as an English eccentric, an aging English hippie living in Franconia who is accompanied everywhere by a large shaggy mongrel dog. I too like my fellow British eccentrics intensely dislike being barraged by other people’s choice of music in bars, cafes, restaurants, shops, on the streets and even today in medical practices. I love music and even call myself a music junkie. I spent a large part of my life earning my living as a concert promoter, concert manager and live concert sound technician. I have an obscenely large record collection (an expression that dates me especially considering the fact that the majority of the music I own is now actually on CD). My favourite occupation is listening to music both live and recorded but I want to listen to the music of my choice in a space conceived for intensive listening. I do not want to be forced to listen to somebody else’s choice of music when I’m drinking a coffee, buying my groceries, having dental surgery (I once got very dirty looks in a dental clinic when I requested that they turn off the aural pollution) or just simply strolling down the street.

Today, Green politicians are very active about environmental pollution and astronomers about light pollution I think more people should take an active stand with Charlie, Ivor Robert and me on noise pollution!

1) This should have been posted yesterday but real life intervened.

Weaving the computer age.

With this post I’m going to lose whatever reputation I might have with all the feminist and politically correct denizens of the blogahedron. Why, because I intend to explode one of the greatest myths in the history of the computer. It is universally claimed that Ada Lady Lovelace was the world’s first programmer, the US Department of Defence even named a computer programme after her to celebrate this fact; this claim is total rubbish. Already in the 19^th century Babbage’s son pointed out that the credit given to Lovelace for her memoir on his fathers Analytical engine was due to his father and not to her. Lovelace has the role of a populariser, deliberately exploited by Babbage to help him in his never ending search for financing of his computer projects. The programme that Lovelace describes for generating Bernoulli numbers was created by Babbage and not by her.

So Charles Babbage is the first programmer and not Ada Lovelace, well, actually no Babbage borrowed the concept for programming his analytical engine from today’s birthday boy the French silk weaver, Joseph Maria Jacquard, 7^th July 1752. Jacquard developed the idea of using punch cards to programme the weaving patterns on his power weaving looms. If anybody should receive the credit for being the first programmer then it’s Joseph Jacquard and not Ada Lovelace.

The Colossus is not a computer!

Having bashed the Americans yesterday for ignoring Konrad Zuse, I will take the opportunity today to bash the Germans, or more precisely Horst Zuse, Konrad’s son, and at the same time correct a commonly held myth.

23^rd June is the birthday of another computer pioneer, Alan Turing. Turing of course means Bletchley Park and the breaking of the Enigma code. Now Bletchley also means one of the early computers, Colossus an electronic, binary, programmable non-Turing complete, special purpose computer designed and built in order to help the Bletchley code breakers. In a lot of popular sources Turing and Colossus are brought together as if it were obvious, Turing = computer expert, Colossus = computer, 1+1 = 3! Before the war Turing wrote one of the most important theoretical works on computing in the history of mathematics and after the War he worked on two major computer projects but in Bletchley he was responsible for the Bombe a very specialised and primitive form of computer but he was not involved in the design and construction of Colossus.

What does all this have to do with Horst Zuse? Horst is a professor for informatics who also specialises in the history of his father’s work. In one of his excellent lectures on his father’s computers, at which I was present, somebody asked him about the Colossus, his answer: “The Colossus was not a computer”. It would appear that Horst Zuse is as blind to his father’s competitors as the Americans to theirs.

Z3 or not Z3 that is the question.

Anyone who reads this blog regularly is probably aware of the fact that the history of computing has more than a passing interest for me. I should add that the history of computing is for me not just the history of the machine on which I am typing this post but covers the whole history of computing in the true meaning of the word i.e. the calculating with numbers starting with people cutting notches in bones tens of thousands of years in the past and going up to the present. This post however concerns the history of the modern computer as the machine with which you are reading this post.

Now as I have already pointed out in a post about Charles Babbage the question as to who invented the computer depends on how you define computer. Do you mean mechanical, electro-mechanical or electronic, special purpose or general purpose, programmable or not programmable, Turning complete or not, binary or decimal and so on and so forth. Beyond this list of technical problems it would appear that there is a certain national element involved in the answer to this question. If you visit the normally excellent Stanford Encyclopaedia of Philosophy and read the History of Modern Computing article you will find discussions of Babbage, Turing, Atanasoff and many others but you wont find a single word about Konrad Zuse who was born 100 years ago on 22^nd June 1910. Some of you might ask so what? The answer in really quite simple according to the Germans, and not only the Germans, Konrad Zuse invented the computer.

Konrad Zuse was a German engineer who built his first machine the Z1, a mechanical computer, in 1938. Built with massive steel components that Zuse cut out with a jigsaw the Z1 was never very reliable and Zuse transferred his concept to the Z2 a prototype that functioned with electrical relays in 1939. This he developed further and produced his Z3 in 1941. This was a fully programmable, binary, Turing complete general purpose electro-mechanical computer. Apart from the fact that it was electro-mechanical and not electronic Zuse’s Z3 was in every aspect a modern computer. Unfortunately for him the Z3 was destroyed in an air raid so after the war the honours for inventing the computer went to Eckert’s and Mauchly’s ENIAC although later an American judge in a strange ruling awarded this honour to Atanasoff and Berry, strange because the ABC never actually functioned.

After WW II Zuse built his first electronic computer the Z4 and this went into production, my university here in Erlangen had a Z4 as its first computer and it’s still here in their museum of computing and is still functioning. Today Zuse is generally recognised as the inventor of the computer for his Z3 but apparently not in America.

Is the question ‘who invented the computer’ legitimate?

I have been known in the past, before I started blogging for myself, to take John Wilkins to task for claiming that Alan Turing is the father of the computer. My objection is that Turing is only one of many so-called fathers of the computer and to give any of them prominence by calling them the father is to falsify the history of computing. As today is the birthday of another of the fathers of the computer, Charles Babbage (1791 – 1871), I have decided to address the question as to whether it is legitimate to ask who invented the computer. The answer to this question is a specific one but its general principle can be applied to almost all similar questions in the history of science and technology. The simple answer to my question is no, it’s not legitimate. This of course provokes the next question, why not? The problem lies in the definite article; what do we mean when we say the computer? Depending on how we answer this question we get wholly different answers to our original question.

There are in fact a whole series of categories that apply to different concepts of the computer that must be taken into consideration when posing the question as to its inventor. Are we talking about mechanical, electro-mechanical or electronic computers? Konrad Zuse, who is generally credited with having built the first functioning computer, actually built one of each. Is the computer in question a special- or general-purpose machine? Is it conceived to solve one specific type mathematic problems or, at least theoretically, all types? The Bletchley Park computer, Colossus, was a special-purpose computer with a limited range of abilities. Does the computer under consideration have stored-programme or not? Most of the early computers did not. Finally and very important was the computer purely theoretical or was a fully functional model actual realised? The last question has more than theoretical value as the computer that is recognised by law in America, and thus for patent purposes, as the first, the Atanasoff-Berry Computer, was never actually built. As should be clear by permutating these categories we arrive at a fairly long list of first computers.

What about our birthday boy Charles Babbage? As should be fairly obvious Babbage’s computers were mechanical. He conceived and started to construct both a special-purpose, his Difference Engine, and a general-purpose computer, his Analytical Engine. The Difference Engine was not stored-programme but the Analytical Engine was. Babbage himself never finished construction of either machine but the Swedish engineer Pehr Georg Scheutz built and sold difference engines based on Babbage’s design. An improved model was also marketed by Martin Wiberg another Swede. A fully functional module for the Analytical Engine was constructed in modern times and can be viewed in the Science Museum in London.

Riffing on an Algorithm

The estimable Thom Levenson author of the excellent Newton and the Counterfeiter, has a piece at The Inverse Square Blog on what he sees as the decline of the Atlantic Monthly; not a subject that would normally cause me to comment here but he includes a justified dismissal of the Atlantic’s abuse of the word algorithm. Now algorithm is a word that truly belongs here so I have decide to expend some thoughts on its meaning, its origins and historical development.

Thom offers up the following working definition for algorithm:

…algorithms involve at a minimum, explicit instructions that can be carried out by a person or a machine which specify operations iterated through a sequence of steps, and produce an unambiguous correct answer (for a certain value of “correct”) within a finite time.

Put simply an algorithm is a recipe for solving problems in the formal sciences, i.e. mathematics, formal logic and computer science. The recipe consists of a finite set of instructions that if carried out in the prescribed order guaranty a solution for the given problem.

Where does the term algorithm come from? It is actually the linguistic corruption of the name of the Uzbek polymath Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmi. Before I continue I should point out that all Islamic scholars of this period are polymaths and al-Khwarizmi’s ethnicity is disputed, as is the ethnicity of almost all Islamic scholars of this period. Now al-Khwarizmi is most famous as the author of Al-Kitāb al-mukhtaṣar fī hīsāb al-ğabr wa’l-muqābala the book that introduced the mathematical discipline algebra into Mediaeval Europe and also gave it its name. Algebra is a corruption of al- ğabr which can be translated as ‘set together’ and thus leads to an ‘Algebraist’ in Spanish being a medical bonesetter. al-Khwarizmi also wrote a book introducing the India decimal place value number system of Brahmagupta into Islamic culture and then in translation into Europe. In the Latin translation al-Khwarizmi becomes Algoritmi, which in turn becomes algorism and algorithm.

The first of these terms, algorism, was the name given to learning how to calculate using the so-called Hindu-Arabic number system at the mediaeval universities and also the name given to the text books used; famous and much used algorisms were written by Sacrobosco and Robert Grosseteste. Algorism was taught as a subsidiary to computos, which was  the science of computing the date of Easter a central part of the mathematics instruction at the mediaeval universities. Later by transference the word algorithm can to designate the methods of calculation used with the new number system, which are in fact algorithms in the modern use of the word.

Although the term itself is a product of the thirteenth century algorithmic mathematics is much older and in fact represents the origins of the subject. In all early mathematical cultures, Babylon, Egypt, India and China, mathematics was presented as a collection of recipes for the solution of specific types of problem. The concept of mathematical proof did not exist and neither did any concept of generalisation. These developments are that which make Greek mathematics in antiquity so important, as it was the Greek mathematicians who first developed the idea of proof and of a systematic presentation of an entire mathematical discipline.

In more recent times the term algorithm has become very central to mathematical logic and computer science as Post, Church, Turing and others all worked on Hilbert’s so-called Entscheidungsproblem. Entscheidung is the German for decision and Hilbert posed the question as to whether every mathematical problem is decidable i.e. is there a finite series of predetermined steps that will lead to a solution of  given problem; in other words an algorithm. The answer produced by the three meta-logicians (meta-mathematicians) named above is no, pushing the humble algorithm into centre stage at the junction of mathematics, logic, computing and philosophy.

Poetical Turing

SCOOPING THE LOOP SNOOPER

A proof that the Halting Problem is undecidable

Geoffrey K. Pullum
(School of Philosophy, Psychology and Language Sciences, University of Edinburgh)

No general procedure for bug checks succeeds. Now, I won’t just assert that, I’ll show where it leads: I will prove that although you might work till you drop, you cannot tell if computation will stop.

For imagine we have a procedure called P that for specified input permits you to see whether specified source code, with all of its faults, defines a routine that eventually halts.

You feed in your program, with suitable data, and P gets to work, and a little while later (in finite compute time) correctly infers whether infinite looping behavior occurs.

If there will be no looping, then P prints out `Good.’ That means work on this input will halt, as it should. But if it detects an unstoppable loop, then P reports `Bad!’ — which means you’re in the soup.

Well, the truth is that P cannot possibly be, because if you wrote it and gave it to me, I could use it to set up a logical bind that would shatter your reason and scramble your mind.

Here’s the trick that I’ll use — and it’s simple to do. I’ll define a procedure, which I will call Q, that will use P‘s predictions of halting success to stir up a terrible logical mess.

For a specified program, say A, one supplies, the first step of this program called Q I devise is to find out from P what’s the right thing to say of the looping behavior of A run on A.

If P‘s answer is `Bad!’, Q will suddenly stop. But otherwise, Q will go back to the top, and start off again, looping endlessly back, till the universe dies and turns frozen and black.

And this program called Q wouldn’t stay on the shelf; I would ask it to forecast its run on itself. When it reads its own source code, just what will it do? What’s the looping behavior of Q run on Q?

If P warns of infinite loops, Q will quit; yet P is supposed to speak truly of it! And if Q‘s going to quit, then P should say `Good’ — which makes Q start to loop! (P denied that it would.)

No matter how P might perform, Q will scoop it: Q uses P‘s output to make P look stupid. Whatever P says, it cannot predict Q: P is right when it’s wrong, and is false when it’s true!

I’ve created a paradox, neat as can be — and simply by using your putative P. When you posited P you stepped into a snare; Your assumption has led you right into my lair.

So where can this argument possibly go? I don’t have to tell you; I’m sure you must know. By reductio, there cannot possibly be a procedure that acts like the mythical P.

You can never find general mechanical means for predicting the acts of computing machines. It’s something that cannot be done. So we users must find our own bugs. Our computers are losers!

---

In October 2000, after a refereeing delay of nearly a year, an earlier and incorrect version of this poetic proof was published in Mathematics Magazine (73, no. 4, 319–320). I am very grateful to Philip Wadler (Informatics, University of Edinburgh) and Larry Moss (Mathematics, Indiana University) for helping with the development of this corrected version, which is now free of bugs (trust me; you can check it). Thanks also to the late Dr. Seuss for the style, and of course to the pioneering work of Alan Turing (and Martin Davis’s nice simplified presentation) for the content. Copyright © 2008 by Geoffrey K. Pullum. Permission is granted to reproduce or distribute this work for non-commercial, educational purposes relating to teaching computer science, mathematics, or logic.

I couldn’t resist reproducing this here; thanks to Leho a commentator at Evolving Thoughts who drew it to my attention. The original is posted here.