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 ?


1 Answer 1


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$ Feb 1, 2015 at 3:49
  • 4
    $\begingroup$ @Rafael: building a special-purpose (not Turing-complete) computer certainly has connections with computability. $\endgroup$ Feb 1, 2015 at 18:05
  • $\begingroup$ Re the question about Colossus, its Wikipedia page links to dl.acm.org/citation.cfm?id=1612096 $\endgroup$ Feb 2, 2015 at 12:04
  • 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, 2015 at 19:53
  • 1
    $\begingroup$ @Jeffε: On the other hand, a hydrogen atom, if confined to take up no more space than the solar system, has a finite-dimensional quantum state space, so there is indeed a finite amount of available storage. But it's not a simple function of the number of elementary particles. $\endgroup$ Apr 24, 2019 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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