6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 machine if it had been built at the time it was designed." $\endgroup$ – vzn Nov 9 '12 at 16:11
  • 2
    $\begingroup$ 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. $\endgroup$ – Jeffε Nov 9 '12 at 16:12
  • $\begingroup$ also repeated here without ref-- "The 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 are all highly interrelated & not easy to decouple/untangle $\endgroup$ – vzn Nov 9 '12 at 16:13
  • $\begingroup$ @jeffe I really mean the mathematical abstraction, of course :) $\endgroup$ – Lena Nov 9 '12 at 16:34
  • $\begingroup$ "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. $\endgroup$ – Marzio De Biasi Nov 9 '12 at 20:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is so true. I overlooked that sentence, stupid me... $\endgroup$ – Lena Nov 12 '12 at 10:05
0
$\begingroup$

there are some new modern attempts to build the Babbage machine, one by John Graham-Cumming. he says in this New Scientist article:

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:

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.