5 ms·
> Turing machines are only “universal” in the sense that they can represent any statement of mathematical logic That's not quite right. TM's in general are no
by lisper 2y ago
> Turing machines are only “universal” in the sense that they can represent any statement of mathematical logic
That's not quite right. TM's in general are not universal. The "universality" of TMs has to do with the existence of a universal TM which is capable of emulating any other TM by putting a specification of the TM to be emulated on the universal TM's tape. The reason this matters is that once you've built a universal TM, you never have to build any more hardware. Any TM can then be emulated in software. That result is due to Turing.
The relationship between TMs and mathematical logic is of a fundamentally different character. It turns out that any system of formal logic can be emulated by a TM (and hence by a UTM), but that is a different result, mainly due to Godel, not Turing. There is also the empirical observation (famously noted by Eugene Wigner [1]) that all known physical phenomena (with the exception of quantum measurements) can be modeled mathematically, and hence can be emulated by a TM, and hence can be emulated by a UTM. But it is entirely possible that a new class of physical phenomena could be discovered tomorrow that cannot be modeled mathematically.
But here's the thing: no one has been able to come up with any idea of what such a phenomenon could possibly look like, and there is a reason to believe that this is not just a failure of imagination but actually a fundamental truth about the universe because our brains are physical systems which themselves can be modeled by mathematics, and that is (empirical) evidence that our universe is in some sense "closed" under Turing-equivalence (with quantum randomness being the lone notable exception). That is the kind of universality embodied in the idea that TM's can emulated "anything we can dream up". It's called the Church-Turing thesis [2] and unlike the universality of universal TM's it cannot be proven because a counterexample might be discovered at any time.
[1] https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
[2] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- adastra22 2y agoI appreciate the detail, but for the record I don’t think we disagree. There’s a lot that I had to oversimplify in my already long comment.
- Y_Y 2y ago> all known physical phenomena (with the exception of quantum measurements) can be modeled mathematically Of course you can model quantum measurements! And Wigner certainly knew so.
- lisper 2y ago> Of course you can model quantum measurements! No, you can't. You can statistically model the results of multiple quantum measurements in the aggregate but you cannot model the physical process of a single measurement because there is a fundamental disconnect between the physics of quantum measurements and TMs, namely, TMs are deterministic and quantum measurements are not. There is a reason that the Measurement Problem is a thing.
- 11101010001100 2y agoSure, the 'problem' is that while the schrodinger equation is deterministic, we can only 'measure' the amplitudes of the solution. Is the wavefunction epistemic or ontological?
- lisper 2y agoNo, this has nothing to do with ontology vs epistemology. That's a philosophical problem. The problem here is that a measurement is a sample from a random distribution. A TM cannot emulate that. It can compute the distribution, but it cannot take a random sample from it. For that you need a random oracle (https://en.wikipedia.org/wiki/Random_oracle https://en.wikipedia.org/wiki/Random_oracle).
- 11101010001100 2y agoRight I did hijack the thread a bit, but for me, the distribution is more than enough. The rest is just interpretation.
- lisper 2y ago
- gedpeck 2y ago… our brains are physical systems which themselves can be modeled by mathematics.. How do you know this? What is the model? Can an AI come up with the Incompleteness Theorems? It can be proven ZFC that PA is consistent. Can an AI or Turing Machine or whatever do the same? EDIT: I’m equating “our brians” with consciousness.
- adastra22 2y agoUnless you're a Cartesian dualist, the mind maps to the brain which is governed by physical laws that are, in principle, fully modeled by mathematical theory that can be simulated on a computer.
- gedpeck 2y ago..physical laws that are, in principle, fully modeled by mathematical theory that can be simulated on a computer. Consciousness so far appears to be something that can’t be modeled mathematically. Can a Turing Machine conclude that while it can’t prove the consistency of the axiomatic system it works under if one embeds that system in a larger system then it could be possible to prove consistency? Aren’t you assuming super determinism? What if consciousness is not “computable” in any meaningful way? For example suppose the theoretically most efficient mathematical model of consciousness requires more variables than the number of particles in the observable universe.
- Terr_ 2y ago> Consciousness so far appears to be something that can’t be modeled mathematically. That doesn't tell us anything though: Almost every single physical phenomenon we can start to model mathematically looked impossible at some point in history. Just because something's hard is not a reason to expect it's magic. If consciousness is somehow un-model-able, that will most likely be for a different reason, where the premise itself is somehow flawed, like how we can't bottle phlogiston or calculate the rate of air turning into maggots.
- 2y ago