In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine. That machine is the Bombe Machine. Is this machine really equivalent to a Turing Machine ?


No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete.

When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle arbitrarily large inputs. But even if we abstract this issue away (in any reasonable way), bombes are not Turing-complete. It could be fun to come up with an appropriate model and determine the exact complexity class covered by bombes.

  • $\begingroup$ So the Turing's work in second war doesn't have any relation with computability ?! Yes, would be fun :D Thank you! $\endgroup$ – Rafael Castro Feb 1 '15 at 3:49
  • 4
    $\begingroup$ @Rafael: building a special-purpose (not Turing-complete) computer certainly has connections with computability. $\endgroup$ – Peter Shor Feb 1 '15 at 18:05
  • $\begingroup$ Re the question about Colossus, its Wikipedia page links to dl.acm.org/citation.cfm?id=1612096 $\endgroup$ – Peter Taylor Feb 2 '15 at 12:04
  • $\begingroup$ It is not true that computers aren't Turing complete: they can use an unlimited amount of external storage. $\endgroup$ – reinierpost Feb 2 '15 at 22:27
  • 1
    $\begingroup$ @reinerpost: No, they can't. The amount of available storage is limited by the amount of available matter, which is limited to less than $10^{1000}$ elementary particles. $\endgroup$ – Jeffε Feb 7 '15 at 19:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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