[skippyfish]

> Godel's incompleteness theorem or the halting problem are applicable to everything including the human brain.

Maybe. That's if you assume that the universe is a conventional computer. Far from settled and the alternative isn't necessarily just "God does it" - it might be that the universe is a "computer-plus", with some processes that produce results not computable by Turing means. It would be strange, but so is quantum mechanics, so...

[seanhunter]

This line of thinking doesn’t really go anywhere. You can say “but what if <something outside of an axiomatic system>? Then <axiomatic system> doesn’t apply!”

Well great. Then where are you? You are precisely nowhere. You haven’t disproved the results in the system and you haven’t proved anything else.

[hardbass]

As of yet we have no such evidence of physical systems that are more powerful than Turing machines. We will consider if ever such evidence arises.

[cyberax]

Turing machines can't operate on arbitrary real-numbered values because they require infinite precision.

If the universe indeed uses real values, it's possible that it's more powerful than Turing machines.

[tsimionescu]

The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers are non-computable (the set of computable numbers is countable, so it has the same "size" as the Naturals, while the Reals are not countable - so they are much larger).

However, this doesn't mean that TMs can't operate on such numbers. You can compute the fact that pi + pi = 2 * pi even if you can't enumerate all of pi's decimals.

[cyberax]

That's why I added the word "arbitrary" :)

> However, this doesn't mean that TMs can't operate on such numbers.

Well, it kinda does. For example, you can't compute the sum of two arbitrary real values in a finite number of steps.

That being said, it's possible that the universe actually is not "running" on real numbers. This would also mean that our physics built on top of calculus is just an approximation.

This has always fascinated me. You can't really construct a meaningful amount of calculus without having real-valued variables. The intermediate value theorem depends on it, and it's one of the foundational parts.

I tried to construct something like "bounded error rational calculus", by trying to use rational ranges instead of real values and then constraining the range size. I was able to recover _some_ calculus, but I really have not studied it in enough details.

[tsimionescu]

I find this topic of precision and of the computation that happens in the universe to be pretty interesting, but also very hard to pin down.

For example, let's take two arbitrary real numbers, call them x and y. They're almost certainly irrational uncomputable numbers, of course. Now, what is their sum? It's x + y, of course - I can tell you that without doing an infinity of computational work. Now, is this a useful representation? It very much depends on the use you have for it. For two unrelated uncomputable numbers, their sum is almost certainly uncomputable anyway, so there's not going to be any meaningful representation of it either. However, we can still derive useful properties about it, and use it in physical simulations as we need. For example, if both x and y are positive, I can tell you that x+y is greater than either of them, so I can also tell you that the electromagnetic force between two particles that are at distance x+y will be weaker than the force between two particles at distances of just x or just y.

So, what would it mean for the universe to "compute the exact value" of these two, or of their sum? What can physics do, assuming that some aspects are indeed continuous, that a simulation running on a TM actually can't?

[cyberax]

But you have a problem when you want to compare two numbers (to see if the particles overlap). Or if you want to divide one number by another.

In theory, in classical physics if you start a simulation on a Turing machine, then all the initial states must be computable. And you can carry on using symbolic representation of numbers, even with transcendental functions (as long as you compute them to a precision necessary to carry out the next step of the simulation).

But with quantum mechanics, we might have true randomness, so precise classic simulation can become impossible after the first interaction.

[pegasus]

Yep, a possibility that has found support with Roger Penrose, who wrote two books about it.