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 ?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
13
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.
answered Jan 31, 2015 at 23:35
-
$\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