3 ms·
It can be the case that both: - The physics of the universe can be completely modeled as computation, and - It's possible to pose undecidable problems about t
by gradys 3mo ago
It can be the case that both:
- The physics of the universe can be completely modeled as computation, and
- It's possible to pose undecidable problems about the way the universe unfolds
This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".
- sgt101 3mo agoOf course, if our universe is undecidable it must be the case that computable processes can be executed within it, and it might be the case that all of the processes that are ever executed within it are computable... but it might be that some of the processes that are executed are not computable... because the machine may.. or may not?
- jerf 3mo agoI think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
- chriswarbo 3mo agoThere's no way to empirically spot an uncomputable process, since it would require infinitely-many observations. For example, if aliens claim their machine solves the halting problem, we could test it on millions of inputs whose halting/not-halting behaviour we already know; but even if it works for all of them, there's no way to know that it works for all inputs. For all we know, it might be a huge lookup table which happens to cover all of those inputs we tried.
- peter_m1 3mo agoNo, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.
- chriswarbo 3mo agoI was responding to this part: > if our universe is undecidable My point is, there would be no way to empirically test this; and therefore, it would make no observable difference, there would be no way to exploit/utilise such effects, etc. In essence: there's no way to tell the difference between a real halting oracle (which would imply an undecidable universe), versus a computable approximation which just-so-happens to be more powerful/sophisticated than the approximations we compare it against. Sure, we can prove that some abstract systems are undecidable and that others aren't. Yet that distinction is inherently unfalsifiable, and hence physically "useless".
- peter_m1 3mo agoQuantum mechanics is intrinsically probabilistic.
- GoblinSlayer 3mo agoDeterministic processes can be modeled probabilistically and are computable, so existence of a probabilistic model doesn't say much about computability.
- woopsn 3mo agoA key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infinite mass (the lattice), bespoke local interactions etc. Problems standing in the way of physics decidability are typically chaos, far from equilibrium mechanics, elementary SNR considerations and so forth, not problems of logic.
- peter_m1 3mo agoIn physics we don't talk about decidability, but solvability.