<p>Your question states:</p>

<blockquote>
  <p>However, the instruction set as devised by Babbage seems to support only going back or jumping ahead <strong>one single punched card</strong>.</p>
</blockquote>

<p>However, the link you supply as a reference for that says</p>

<blockquote>
  <p>The number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader.</p>
</blockquote>

<p>This would seem to render your question moot.</p>

CC BY-SA 3.0
2012-11-12T10:05:35.523Z
This is so true. I overlooked that sentence, stupid me...
Lena
CC BY-SA 3.0
2012-11-09T20:05:20.947Z
2012-11-09T20:05:20.947Z
Peter Taylor
<p>there are some new modern attempts to build the Babbage machine, one by John Graham-Cumming. he says in this <a href="http://www.newscientist.com/article/mg20827915.500-lets-build-babbages-ultimate-mechanical-computer.html" rel="nofollow">New Scientist article</a>:</p>

<blockquote>
  <p>Even though the Analytical Engine would have been mechanical and powered by steam, it would likely have been Turing-complete - that is, capable of computing any computable function.</p>
</blockquote>

<p>however, have not actually seen a strict proof of this published. suspect a proof is not difficult. from your 2nd ref by John Walker it appears that one possible scheme would be to use separate punch cards as Turing tape squares, one "symbol" per punch card. the machine appears to support some operations like "move back 1 card" and "move forward 1 card" based on the current state. since the punch card stack is not conceptually/strictly limited in size, it seems fair to say its Turing complete in the same sense modern computers are. have not seen a good theoretical description of the Babbage engine, most descriptions are more in physical terms. Babbage himself did not seem to focus so much on programming, instead he mostly devised blueprints.</p>

<p>Wikipedia, <a href="http://en.wikipedia.org/wiki/Analytical_Engine" rel="nofollow">Analytical Engine</a>:</p>

<blockquote>
  <p>The programming language to be employed by users was akin to modern day assembly languages. Loops and conditional branching were possible, and so the language as conceived would have been Turing-complete as later defined by Alan Turing.</p>
</blockquote>

<p>this next point from Wikipedia is relevant because it shows that the Babbage design for the analytical engine was analyzed by the <em>mathematician</em> Menabrea (ie from a symbolic/mathematical and not primarily engineering point of view) which was later annotated by Lovelace, recognized as the "first computer programmer", more circumstantial evidence for what might be regarded as a "<em>retroactive</em> Turing completeness" of the Babbage machine.</p>

<blockquote>
  <p>In 1842, the Italian mathematician Luigi Menabrea, whom Babbage had met while travelling in Italy, wrote a description of the engine in French. In 1843, the description was translated into English and extensively annotated by Ada Byron, Countess of Lovelace, who had become interested in the engine ten years earlier. In recognition of her additions to Menabrea's paper, which included a way to calculate Bernoulli numbers using the machine, she has been described as the first computer programmer.</p>
</blockquote>

<p>this very apropos NYT article <a href="http://www.nytimes.com/2011/11/08/science/computer-experts-building-1830s-babbage-analytical-engine.html?pagewanted=all&amp;_r=0" rel="nofollow">Computer experts building 1830s Babbage analytical engine</a> deconstructs the interconnecting historical threads of awareness more carefully.</p>

<blockquote>
  <p>The consensus of computer historians is that while Babbage was clearly the first to conceive of the flexible machine that foreshadowed the modern computer, his work was forgotten and was then conceptually recreated by Turing a century later.</p>
  
  <p>...</p>
  
  <p>“The pioneers of electronic computing reinvented the fundamental principles largely in ignorance of the details of Babbage’s work,” said Dr. Swade, the former museum curator. “They knew of him, there was a continuity of influence, but his drawings were not the DNA of modern computing.”</p>
  
  <p>He argues that Turing was a “bridging” figure between Babbage and Lovelace and the modern world of electronic computers.</p>
  
  <p>A Turing biographer, Andrew Hodges, doubts that his subject had seen the Lovelace notes when he wrote “On Computable Numbers.”</p>
  
  <p>“It’s most unlikely that Babbage/Lovelace had any influence on Turing in 1936,” Dr. Hodges, an Oxford mathematician, wrote in an e-mail. “Motivation, means, language, results were all completely different.” </p>
</blockquote>

<p>however later than the 30s when Turing wrote his initial paper, he did appear to become aware of Babbage/Lovelace.</p>

CC BY-SA 3.0
2012-11-09T16:36:26.807Z
2012-11-09T17:01:36.670Z
2012-11-09T17:01:36.670Z
vzn
<p>According to literature, Babbage's Analytical Engine is turing-complete because it supports conditional branching: it can perform different operations depending on the sign of the result last operation using a conditional arm (see <a href="http://web.archive.org/web/20100426034840/http://halfbakedmaker.org/2009/12/26/rod-logic-alu-2/" rel="nofollow noreferrer">http://web.archive.org/web/20100426034840/http://halfbakedmaker.org/2009/12/26/rod-logic-alu-2/</a>).</p>

<p>However, the instruction set as devised by Babbage seems to support only going back or jumping ahead <strong>one single punched card</strong>. (see <a href="http://www.fourmilab.ch/babbage/cards.html" rel="nofollow noreferrer">http://www.fourmilab.ch/babbage/cards.html</a>, "Combinaritorial Cards")
Surely this is computationally less mighty than supporting a goto-statement for jumping to arbitrary statements?</p>

<p>If any two turing machines can emulate each other, how can the goto-behaviour be emulated using the conditional jumping of just one instruction?</p>

CC BY-SA 3.0
2012-11-09T16:11:17.923Z
wonder too! the 1st ref appears to be an idea to implement mechanical "gates" for boolean logic using babbages mechanisms, an idea that babbage did not have (dont think babbage was aware of boolean logic...?) the 2nd ref suggests that maybe the punch cards could be used as Turing tape squares for turing equivalence. have never seen/heard a good analysis/ref of this. wikipedia states without ref "Charles Babbage's analytical engine (1830s) would have been the first [Turing-complete](http://en.wikipedia.org/wiki/Turing_completeness) machine if it had been built at the time it was designed."
vzn
CC BY-SA 3.0
2012-11-09T16:12:59.393Z
To answer the title question literally: **Obviously not**.  Like every other physical computer, the Analytical Engine has at most the power of a finite-state machine.  Now, if you really mean some _mathematical abstraction_ of the Analytical Engine, that's a different story.
Jeffε
CC BY-SA 3.0
2012-11-09T16:13:29.060Z
also repeated here without ref-- "[The Analytical Engine](http://en.wikipedia.org/wiki/Analytical_Engine) incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete." anyway it appears that the turing machine, babbage machine, and [von neumann architecture](http://en.wikipedia.org/wiki/Von_Neumann_architecture) are all highly interrelated & not easy to decouple/untangle
vzn
CC BY-SA 3.0
2012-11-09T16:34:02.107Z
@jeffe I really mean the mathematical abstraction, of course :)
Lena
CC BY-SA 3.0
2012-11-09T20:09:26.813Z
*"However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card"*. But in the linked article it is written: *"...  the number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader ..."* so it seems that you can do arbitrary jumps. However if only a "skip next instruction" operator is allowed, the machine (its abstraction) can still be Turing complete if after the last card has been processed, the first one is reinserted and the whole control card chain is processed again.
Marzio De Biasi
CC BY-SA 3.0
2012-11-12T15:46:53.060Z
@MarzioDeBiasi Yes, you can do arbitrary jumps, that was huge mistake of mine... but restarting the control card chain would require the intervention of the human attendant, which is not modeled in the machine abstraction, so I guess this wouldn't be permitted?
Lena
CC BY-SA 3.0
2016-07-26T21:54:16.510Z
@Lena: By my understanding, Jacquard looms use a sequence of cards which are fastened together to form a repeating loop.  I would think that Babbage would have planned on his machine being set up likewise, since most practical operations would require running through the cards hundreds if not thousands of times.
supercat
<computability><turing-machines><universal-computation>
Was Babbage's Analytical Engine really turing-complete?
Lena
# Was Babbage's Analytical Engine really turing-complete?

(Asked by: username_0 on 2012-11-09)

According to literature, Babbage's Analytical Engine is turing-complete because it supports conditional branching: it can perform different operations depending on the sign of the result last operation using a conditional arm (see <http://web.archive.org/web/20100426034840/http://halfbakedmaker.org/2009/12/26/rod-logic-alu-2/>).

However, the instruction set as devised by Babbage seems to support only going back or jumping ahead **one single punched card**. (see <http://www.fourmilab.ch/babbage/cards.html>, "Combinaritorial Cards")
Surely this is computationally less mighty than supporting a goto-statement for jumping to arbitrary statements?

If any two turing machines can emulate each other, how can the goto-behaviour be emulated using the conditional jumping of just one instruction?

**Tags:** computability, turing-machines, universal-computation
> **Comments:**
> **username_1**: wonder too! the 1st ref appears to be an idea to implement mechanical "gates" for boolean logic using babbages mechanisms, an idea that babbage did not have (dont think babbage was aware of boolean logic...?) the 2nd ref suggests that maybe the punch cards could be used as Turing tape squares for turing equivalence. have never seen/heard a good analysis/ref of this. wikipedia states without ref "Charles Babbage's analytical engine (1830s) would have been the first [Turing-complete](http://en.wikipedia.org/wiki/Turing_completeness) machine if it had been built at the time it was designed."  
> **username_2**: To answer the title question literally: **Obviously not**.  Like every other physical computer, the Analytical Engine has at most the power of a finite-state machine.  Now, if you really mean some _mathematical abstraction_ of the Analytical Engine, that's a different story.  
> **username_1**: also repeated here without ref-- "[The Analytical Engine](http://en.wikipedia.org/wiki/Analytical_Engine) incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete." anyway it appears that the turing machine, babbage machine, and [von neumann architecture](http://en.wikipedia.org/wiki/Von_Neumann_architecture) are all highly interrelated & not easy to decouple/untangle  
> **username_0**: @jeffe I really mean the mathematical abstraction, of course :)  
> **username_3**: *"However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card"*. But in the linked article it is written: *"...  the number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader ..."* so it seems that you can do arbitrary jumps. However if only a "skip next instruction" operator is allowed, the machine (its abstraction) can still be Turing complete if after the last card has been processed, the first one is reinserted and the whole control card chain is processed again.  
> **username_0**: @MarzioDeBiasi Yes, you can do arbitrary jumps, that was huge mistake of mine... but restarting the control card chain would require the intervention of the human attendant, which is not modeled in the machine abstraction, so I guess this wouldn't be permitted?  
> **username_4**: @Lena: By my understanding, Jacquard looms use a sequence of cards which are fastened together to form a repeating loop.  I would think that Babbage would have planned on his machine being set up likewise, since most practical operations would require running through the cards hundreds if not thousands of times.  

---

## 2 answers

### Answer by username_5 on 2012-11-09. Score: 4 | Accepted answer

Your question states:

> However, the instruction set as devised by Babbage seems to support only going back or jumping ahead **one single punched card**.

However, the link you supply as a reference for that says

> The number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader.

This would seem to render your question moot.

> **Comments:**
> **username_0**: This is so true. I overlooked that sentence, stupid me...  

---

### Answer by username_1 on 2012-11-09. Score: 0

there are some new modern attempts to build the Babbage machine, one by John Graham-Cumming. he says in this [New Scientist article](http://www.newscientist.com/article/mg20827915.500-lets-build-babbages-ultimate-mechanical-computer.html):

> Even though the Analytical Engine would have been mechanical and powered by steam, it would likely have been Turing-complete - that is, capable of computing any computable function.

however, have not actually seen a strict proof of this published. suspect a proof is not difficult. from your 2nd ref by John Walker it appears that one possible scheme would be to use separate punch cards as Turing tape squares, one "symbol" per punch card. the machine appears to support some operations like "move back 1 card" and "move forward 1 card" based on the current state. since the punch card stack is not conceptually/strictly limited in size, it seems fair to say its Turing complete in the same sense modern computers are. have not seen a good theoretical description of the Babbage engine, most descriptions are more in physical terms. Babbage himself did not seem to focus so much on programming, instead he mostly devised blueprints.

Wikipedia, [Analytical Engine](http://en.wikipedia.org/wiki/Analytical_Engine):

> The programming language to be employed by users was akin to modern day assembly languages. Loops and conditional branching were possible, and so the language as conceived would have been Turing-complete as later defined by Alan Turing.

this next point from Wikipedia is relevant because it shows that the Babbage design for the analytical engine was analyzed by the *mathematician* Menabrea (ie from a symbolic/mathematical and not primarily engineering point of view) which was later annotated by Lovelace, recognized as the "first computer programmer", more circumstantial evidence for what might be regarded as a "*retroactive* Turing completeness" of the Babbage machine.

> In 1842, the Italian mathematician Luigi Menabrea, whom Babbage had met while travelling in Italy, wrote a description of the engine in French. In 1843, the description was translated into English and extensively annotated by Ada Byron, Countess of Lovelace, who had become interested in the engine ten years earlier. In recognition of her additions to Menabrea's paper, which included a way to calculate Bernoulli numbers using the machine, she has been described as the first computer programmer.

this very apropos NYT article [Computer experts building 1830s Babbage analytical engine](http://www.nytimes.com/2011/11/08/science/computer-experts-building-1830s-babbage-analytical-engine.html?pagewanted=all&_r=0) deconstructs the interconnecting historical threads of awareness more carefully.

> The consensus of computer historians is that while Babbage was clearly the first to conceive of the flexible machine that foreshadowed the modern computer, his work was forgotten and was then conceptually recreated by Turing a century later.
>
> ...
>
> “The pioneers of electronic computing reinvented the fundamental principles largely in ignorance of the details of Babbage’s work,” said Dr. Swade, the former museum curator. “They knew of him, there was a continuity of influence, but his drawings were not the DNA of modern computing.”
>
> He argues that Turing was a “bridging” figure between Babbage and Lovelace and the modern world of electronic computers.
>
> A Turing biographer, Andrew Hodges, doubts that his subject had seen the Lovelace notes when he wrote “On Computable Numbers.”
>
> “It’s most unlikely that Babbage/Lovelace had any influence on Turing in 1936,” Dr. Hodges, an Oxford mathematician, wrote in an e-mail. “Motivation, means, language, results were all completely different.”

however later than the 30s when Turing wrote his initial paper, he did appear to become aware of Babbage/Lovelace.


---

