[sgt101]

Of 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]

I 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]

There'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]

No, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.

[chriswarbo]

I 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]

Quantum mechanics is intrinsically probabilistic.

[GoblinSlayer]

Deterministic processes can be modeled probabilistically and are computable, so existence of a probabilistic model doesn't say much about computability.