6 ms·

Quantum non-determinism isnt computable. A universal turing machine is just an implementation of a function from the Naturals to Naturals (ie., expressible as a

Quantum non-determinism isnt computable. A universal turing machine is just an implementation of a function from the Naturals to Naturals (ie., expressible as a binary -> binary). QM systems cannot be described by such functions, hence the world isnt a computer. Eg., any quantum randomness isnt a function as it has no input state and a non-determinstic output state. Worse, clearly at least the input and output states of a computer should be measurable -- but most systems arent. Even including classical ones. Ie., in chaotic systems it isn't possible, due to QM, to measure x st. f in y = f(x, t) is just a set (x, y, t) -- for large t. f here cannot be a function -- as y is necessarily a distribution of states. In abitary chaotic systems y spans the space of all possible states of abitary t, and thus we have zero ability to predict anything beyond relatively narrow time-horizons. If you wish to claim reality is a computer: (1) state the properties of a computer; (2) show that having these properties is non-trivial (ie., it is a substantive claim that something is a computer); and (3) show that these properties are at least consistent with our best theories of physics.

tsimionescu 5y ago
An ideal Turing Machine can perfectly well predict the state of a quantum system: it can solve the Schordinger equation, and predict the time evolution of the system for each possible solution. It can then predict all possible states of the world after N steps, and even the probability of each state. N can be arbitrarily large. If you believe in the Copenhagen interpretation of QM, you then need to choose one of these states randomly according to the probability the TM predicted. If you believe in the MWI, you don't even need to do that: by this point, the TM has already done exactly what the universe does. This same process also extends to chaotic systems: a Turing machine can take all possible measurement clause and compute the state of the system after N steps. The mistake you are making is in the word 'predict'. Of course you can't predict the result of a non-deterministic process. But a computer doesn't predict: it computes, that is, it follows mechanical steps to transform an input value. And non-deterministic computations are nothing special, we do them every day in real computers ( rand() is a non-deterministic computation). The most famous class of algorithms in complexity theory is even called 'Nondeterministic Polynomial Time', NP for short (of P=NP? fame).
- mjburgess 5y ago
  To do this you need uncountable turing machines, and that set isnt a computable function. Hilbert space is infinite-dimensional and real-valued. QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability.
  - tsimionescu 5y ago
    I would first note that you can keep arguing with me all you want, but it is well known and commonly practiced that a Turing machine such as a digital computer can simulate a Quantum Computer or Quantum System to arbitrary precision, given sufficiently large but finite time. There are even cloud services offering such simulation capabilities, such as Amazon Braket [0]. The simulations take exponential time to run a linear time quantum algorithm, but they will produce the same result as a QC would (after enough sampling of the QC results). > Hilbert space is infinite-dimensional and real-valued. Infinite-dimensional Hilbert state spaces are a useful mathematical model, but they are not physical. Physical systems have finite elements and thus finite state spaces. We could argue that space itself is infinitely divisible, so that we need infinite-dimensional state spaces to represent the infinite possible positions of a particle, but this is not a physical concern, as it is impossible to differentiate in finite time two states that only differ in an infinitesimal position change - so, we are free to choose some minimal unit of length (say, one over Graham's number of the Planck length) and get a finite-dimensional state space. Crucially, for any amount of time and for any sensitivity of instruments, we can always choose some such unit and ensure that our results will not be distinguishable with those measurement instruments within that amount of time. > QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. QM says no such thing, though many interpretations do. Still, that is exactly why I chose rand(), not rand(seed) in my example, so I'm not sure why you're bringing this up. rand(seed) is a deterministic computation, rand() is a non-deterministic computation. > If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability. This is not what I was proposing. I was proposing a Turing machine + perfectly random rand() as the simulation of a random world. Even this is not necessary if you believe in the MWI, where the whole universe actually evolves perfectly linearly and deterministically from a fixed initial state, with no randomness of any kind. This interpretation is perfectly compatible with all observations of QM, if we also add the postulate that observers can only observe one state at a time (the one they are entangled with). Even without going there, the construction I proposed earlier, where we essentially select enough real numbers to satisfy any possible measurement device leads to such that our computable set is indistinguishable in practice from the infinite uncomputable set we started with still applies. In general, there is no (known) way to introduce infinity into empirical science - it is a priori impossible to distinguish, in finite time, between an arbitrarily large but finite quantity, and a truly infinite quantity. [0] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/

tsimionescu 5y ago

An ideal Turing Machine can perfectly well predict the state of a quantum system: it can solve the Schordinger equation, and predict the time evolution of the system for each possible solution. It can then predict all possible states of the world after N steps, and even the probability of each state. N can be arbitrarily large. If you believe in the Copenhagen interpretation of QM, you then need to choose one of these states randomly according to the probability the TM predicted. If you believe in the MWI, you don't even need to do that: by this point, the TM has already done exactly what the universe does. This same process also extends to chaotic systems: a Turing machine can take all possible measurement clause and compute the state of the system after N steps. The mistake you are making is in the word 'predict'. Of course you can't predict the result of a non-deterministic process. But a computer doesn't predict: it computes, that is, it follows mechanical steps to transform an input value. And non-deterministic computations are nothing special, we do them every day in real computers ( rand() is a non-deterministic computation). The most famous class of algorithms in complexity theory is even called 'Nondeterministic Polynomial Time', NP for short (of P=NP? fame).

mjburgess 5y ago
To do this you need uncountable turing machines, and that set isnt a computable function. Hilbert space is infinite-dimensional and real-valued. QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability.
- tsimionescu 5y ago
  I would first note that you can keep arguing with me all you want, but it is well known and commonly practiced that a Turing machine such as a digital computer can simulate a Quantum Computer or Quantum System to arbitrary precision, given sufficiently large but finite time. There are even cloud services offering such simulation capabilities, such as Amazon Braket [0]. The simulations take exponential time to run a linear time quantum algorithm, but they will produce the same result as a QC would (after enough sampling of the QC results). > Hilbert space is infinite-dimensional and real-valued. Infinite-dimensional Hilbert state spaces are a useful mathematical model, but they are not physical. Physical systems have finite elements and thus finite state spaces. We could argue that space itself is infinitely divisible, so that we need infinite-dimensional state spaces to represent the infinite possible positions of a particle, but this is not a physical concern, as it is impossible to differentiate in finite time two states that only differ in an infinitesimal position change - so, we are free to choose some minimal unit of length (say, one over Graham's number of the Planck length) and get a finite-dimensional state space. Crucially, for any amount of time and for any sensitivity of instruments, we can always choose some such unit and ensure that our results will not be distinguishable with those measurement instruments within that amount of time. > QM says that there is no `rand(seed)`, rather there is only `rand()` that is what "no hidden variables" means. QM says no such thing, though many interpretations do. Still, that is exactly why I chose rand(), not rand(seed) in my example, so I'm not sure why you're bringing this up. rand(seed) is a deterministic computation, rand() is a non-deterministic computation. > If you want to do `rand(s) forall s`, that "forall" requires real numbers -- and then you're out-of-luck on computability. This is not what I was proposing. I was proposing a Turing machine + perfectly random rand() as the simulation of a random world. Even this is not necessary if you believe in the MWI, where the whole universe actually evolves perfectly linearly and deterministically from a fixed initial state, with no randomness of any kind. This interpretation is perfectly compatible with all observations of QM, if we also add the postulate that observers can only observe one state at a time (the one they are entangled with). Even without going there, the construction I proposed earlier, where we essentially select enough real numbers to satisfy any possible measurement device leads to such that our computable set is indistinguishable in practice from the infinite uncomputable set we started with still applies. In general, there is no (known) way to introduce infinity into empirical science - it is a priori impossible to distinguish, in finite time, between an arbitrarily large but finite quantity, and a truly infinite quantity. [0] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/