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

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

CC BY-SA 3.0
2015-02-01T03:49:26.750Z
So the Turing's work in second war doesn't have any relation with computability ?! 
Yes, would be fun :D Thank you!
Rafael Castro
CC BY-SA 3.0
2015-02-01T18:05:52.900Z
@Rafael: building a special-purpose (not Turing-complete) computer certainly has connections with computability.
Peter Shor 
CC BY-SA 3.0
2015-02-02T12:04:05.663Z
Re the question about Colossus, its Wikipedia page links to http://dl.acm.org/citation.cfm?id=1612096
Peter Taylor
CC BY-SA 3.0
2015-02-02T22:27:15.700Z
It is not true that computers aren't Turing complete: they can use an unlimited amount of external storage.
reinierpost
CC BY-SA 3.0
2015-02-07T19:53:34.617Z
@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.
Jeffε
CC BY-SA 3.0
2016-09-15T18:22:12.833Z
@Jeffε You seem to be assuming that any particular particle can only store a bounded amount of information. But even a hydrogen atom has an infinite-dimensional quantum state space.
Peter Shor 
CC BY-SA 4.0
2019-04-24T18:06:39.023Z
@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.
Peter Shor 
CC BY-SA 4.0
2019-04-24T21:03:28.017Z
It's a simple function of the number of elementary particles, the radius of the observable universe, the Planck constant, the speed of light, and probably the half-life of quarks, all of which are constants.
Jeffε
CC BY-SA 4.0
2019-06-04T10:10:05.487Z
@Jeffε: But the radius of the observable universe keeps on growing. At time $T$ the observable universe has volume $T^3$, and thus, even with a finite amount of matter we can access a Hilbert space with arbitrarily many dimensions, if we are willing to wait long enough.
Peter Shor 
CC BY-SA 4.0
2019-06-05T14:28:36.780Z
@PeterShor Unless the speed of light or the Hubble constant changes, the _observable_ universe has volume $O_T(1)$.  Beyond a certain distance, the universe is expanding away from us faster than the speed of light, which means no matter how long we wait, we cannot access any information outside that radius.
Jeffε
CC BY-SA 4.0
2019-06-05T17:00:05.910Z
@Jeffε: That doesn't matter. The number of quantum bits needed to represent a single hydrogen atom in a volume $V$ of space approaches $\infty$ as $V$ goes to $\infty$. And no matter how much time goes by, we will have at least one hydrogen atom available to us, and an increasing volume of space that it is contained in. So there is actually no upper bound on the number of bits needed to naïvely simulate the observable universe.  I don't think this fact will actually let us build a truly Turing-complete machine, but your arguments don't disprove it.
Peter Shor 
CC BY-SA 4.0
2019-06-05T17:05:50.590Z
You don't actually need any extra *information* to run a Turing machine for an unbounded time, so it doesn't matter that we only have $O(1)$ information available to us. What you need is an unlimited amount of empty tape cells.
Peter Shor 
CC BY-SA 4.0
2019-06-06T21:16:49.430Z
Something very weird is going on here, but I suppose that's par for the course for quantum mechanics.  Do you have a reference for "The number of quantum bits needed to represent a single hydrogen atom in a volume  of space approaches ∞ as  goes to ∞", that takes the finite speed-of-light horizon into account?
Jeffε
CC BY-SA 4.0
2024-05-03T13:06:14.133Z
@PeterShor- A Turing machine would need an infinite amount of energy, in addition to storage and time, and I believe that if we accept the heat-death end of the universe, we don't get infinite usable energy.  So, no dice; can't do it even if we have eternity to wait.
Jeff Learman
CC BY-SA 3.0
2015-01-31T23:35:00.617Z
2015-01-31T23:35:00.617Z
Yuval Filmus
<p>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 ?</p>

<computability><turing-machines><universal-turing-machines>
Was bombe machine turing complete?
Rafael Castro
# Was bombe machine turing complete?

(Asked by: username_0 on 2015-01-31)

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 ?

**Tags:** computability, turing-machines, universal-turing-machines


---

## 1 answers

### Answer by username_1 on 2015-01-31. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: So the Turing's work in second war doesn't have any relation with computability ?!  Yes, would be fun :D Thank you!  
> **username_2**: @Rafael: building a special-purpose (not Turing-complete) computer certainly has connections with computability.  
> **username_3**: Re the question about Colossus, its Wikipedia page links to http://dl.acm.org/citation.cfm?id=1612096  
> **username_4**: It is not true that computers aren't Turing complete: they can use an unlimited amount of external storage.  
> **username_5**: @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.  
> **username_2**: @username_5 You seem to be assuming that any particular particle can only store a bounded amount of information. But even a hydrogen atom has an infinite-dimensional quantum state space.  
> **username_2**: @username_5: 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.  
> **username_5**: It's a simple function of the number of elementary particles, the radius of the observable universe, the Planck constant, the speed of light, and probably the half-life of quarks, all of which are constants.  
> **username_2**: @username_5: But the radius of the observable universe keeps on growing. At time $T$ the observable universe has volume $T^3$, and thus, even with a finite amount of matter we can access a Hilbert space with arbitrarily many dimensions, if we are willing to wait long enough.  
> **username_5**: @PeterShor Unless the speed of light or the Hubble constant changes, the _observable_ universe has volume $O_T(1)$.  Beyond a certain distance, the universe is expanding away from us faster than the speed of light, which means no matter how long we wait, we cannot access any information outside that radius.  
> **username_2**: @username_5: That doesn't matter. The number of quantum bits needed to represent a single hydrogen atom in a volume $V$ of space approaches $\infty$ as $V$ goes to $\infty$. And no matter how much time goes by, we will have at least one hydrogen atom available to us, and an increasing volume of space that it is contained in. So there is actually no upper bound on the number of bits needed to naïvely simulate the observable universe.  I don't think this fact will actually let us build a truly Turing-complete machine, but your arguments don't disprove it.  
> **username_2**: You don't actually need any extra *information* to run a Turing machine for an unbounded time, so it doesn't matter that we only have $O(1)$ information available to us. What you need is an unlimited amount of empty tape cells.  
> **username_5**: Something very weird is going on here, but I suppose that's par for the course for quantum mechanics.  Do you have a reference for "The number of quantum bits needed to represent a single hydrogen atom in a volume  of space approaches ∞ as  goes to ∞", that takes the finite speed-of-light horizon into account?  
> **username_6**: @PeterShor- A Turing machine would need an infinite amount of energy, in addition to storage and time, and I believe that if we accept the heat-death end of the universe, we don't get infinite usable energy.  So, no dice; can't do it even if we have eternity to wait.  

---

