Turing Machines and Quantum Physics
So, I'm pretty new to thinking about computing theory, and I'm pretty new to studying physics. And I haven't studied either in a deep, mathematically-rigorous way. I'm hoping that someone out there can shed some light on something I've been thinking about a lot lately:
A lot of people think that the Turing Machine is the most powerful (in the formal sense) computing machine possible in the universe as we know it. This flows from the notion that when we've tried hard enough, we've been able to simulate any other computing machine that we've thought of with some kind of Turing Machine. When people try to think about machines more powerful than Turing Machines, they almost always resort to spooky stuff - like machines that can instantly factor primes, or machines that have some component that operates in a different temporal frame of reference. That kind of thing.
The thought that Turing Machines are universal computers is pretty exciting. It implies that any process can be simulated on a Turing Machine with a sufficiently complicated state space. Anything! That covers a whole lot of ground. It gives hope that we might actually achieve real artificial intelligence - since, after all, our brains are just complicated Turing Machines. Or maybe even real synthetic life. In fact, if the Turing Machine is the most powerful simulator possible (rather than just the most powerful simulator available), I'd expect that it can simulate everything - up to and including the whole Universe.
Now, that gets a bit sticky. From the viewpoint of classical physics, it seems perfectly reasonable to assume that we can run the Universe on a Turing Machine. After all, every effect has an immediate preceding cause, and all of that. It looks pretty mechanistic. But classical physics is wrong, and we know it's wrong. At the quantum level, causality breaks down, and the state of any particle is really just a cloud of probabilities that collapses down when we observe it. Physicists say that these probabalistic quantum phenomena are truly random - in fact, the only truly random things possible. But, if they're truly random, they can't be simulated on a Turing Machine, can they?
The best a Turing Machine (unextended) can give us is pseudo-random state generation. As von Neumann said, "Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin." So something's got to give. Either the Turing Machine can't actually simulate the known Universe (in which case, something more powerful must be possible in principal), or else it can, and quantum phenomena aren't really random. They could be pseudo-random with a period longer than the lifetime of the Universe, and maybe that's good enough; but maybe it's not. I am not a physicist, so I can't say.
If we assume that time, at resolutions significantly smaller than covered by the noise of Heisenberg's equations, is discrete (and who's to say it's not?), and that we have a quantum doo-dad that can allow the FSM of a Turing Machine to pop out truly random numbers any time it wants, then this extension to the Turing Machine may be sufficient to allow us to simulate the universe. And if it's enough, then the ability to generate random numbers is a meaningful extension to the Turing Machine, one which creates a more powerful machine (even if we can't actually harness that extra power).
A lot of people think that the Turing Machine is the most powerful (in the formal sense) computing machine possible in the universe as we know it. This flows from the notion that when we've tried hard enough, we've been able to simulate any other computing machine that we've thought of with some kind of Turing Machine. When people try to think about machines more powerful than Turing Machines, they almost always resort to spooky stuff - like machines that can instantly factor primes, or machines that have some component that operates in a different temporal frame of reference. That kind of thing.
The thought that Turing Machines are universal computers is pretty exciting. It implies that any process can be simulated on a Turing Machine with a sufficiently complicated state space. Anything! That covers a whole lot of ground. It gives hope that we might actually achieve real artificial intelligence - since, after all, our brains are just complicated Turing Machines. Or maybe even real synthetic life. In fact, if the Turing Machine is the most powerful simulator possible (rather than just the most powerful simulator available), I'd expect that it can simulate everything - up to and including the whole Universe.
Now, that gets a bit sticky. From the viewpoint of classical physics, it seems perfectly reasonable to assume that we can run the Universe on a Turing Machine. After all, every effect has an immediate preceding cause, and all of that. It looks pretty mechanistic. But classical physics is wrong, and we know it's wrong. At the quantum level, causality breaks down, and the state of any particle is really just a cloud of probabilities that collapses down when we observe it. Physicists say that these probabalistic quantum phenomena are truly random - in fact, the only truly random things possible. But, if they're truly random, they can't be simulated on a Turing Machine, can they?
The best a Turing Machine (unextended) can give us is pseudo-random state generation. As von Neumann said, "Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin." So something's got to give. Either the Turing Machine can't actually simulate the known Universe (in which case, something more powerful must be possible in principal), or else it can, and quantum phenomena aren't really random. They could be pseudo-random with a period longer than the lifetime of the Universe, and maybe that's good enough; but maybe it's not. I am not a physicist, so I can't say.
If we assume that time, at resolutions significantly smaller than covered by the noise of Heisenberg's equations, is discrete (and who's to say it's not?), and that we have a quantum doo-dad that can allow the FSM of a Turing Machine to pop out truly random numbers any time it wants, then this extension to the Turing Machine may be sufficient to allow us to simulate the universe. And if it's enough, then the ability to generate random numbers is a meaningful extension to the Turing Machine, one which creates a more powerful machine (even if we can't actually harness that extra power).
- So, two additional thoughts:
- In this way, real computers are already more powerful than Turing Machines. Nowadays it's not all that uncommon for a hardware manufacturer to provide a chip that just takes very fine measurements of the quantum noise inside it's own silicon, so it can provide truly random numbers to the operating system on-demand.
- Is it possible that there are problems (language classification tasks, decision tasks) for which a partially stochastic machine can be shown to be (at least extremely likely to be) more powerful than a fully deterministic one? Perhaps that's the real boundary of decidability - not the limits of what we can know, but merely the limit of what we can know without assigning a probability. And pragmatically - if we can push those probabilities into the 5, 6, or 7 nines range, do we care?
I can't believe that my thought process is novel; has anyone got good pointers elsewhere?