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$ Commented Feb 1, 2015 at 3:49
  • 4
    $\begingroup$ @Rafael: building a special-purpose (not Turing-complete) computer certainly has connections with computability. $\endgroup$ Commented 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$ Commented 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ε
    Commented 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$ Commented Apr 24, 2019 at 18:06

Your Answer

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

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