1
$\begingroup$

I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:

"The universe is a hypercomputer and then it is possible to build more powerful machines than Turing machines. For this it would be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said supercomputer as input"

Would that mean that every continious (or "continously-enough") model of spacetime and the universe could have fundamentally hypercomputational physics (physics described and based in hypercomputation and hypercomputational processes and laws/rules, describing a hypercomputer-like universe)? Or on the contrary only certain models could do it? In that case, can you think of any in particular?

$\endgroup$
  • $\begingroup$ I don't know what it means for "physics itself [to] be described fundamentally by hypercomputation". That doesn't seem like a well-defined notion. Often you can have multiple formalisms that make equivalent predictions but that use different mathematics (e.g., one is expressed in terms of hypercomputation and one isn't); if they make the same predictions, they are considered equivalent as far as physics goes. So would you consider that "described fundamentally by hypercomputation" or not? The very notion doesn't seem well-defined. $\endgroup$ – D.W. Feb 20 at 1:11
  • $\begingroup$ In any case, questions about physics are probably off-topic here. This site is about computation, not about theories of physics. Your question seems to be more about physics than about computation. $\endgroup$ – D.W. Feb 20 at 1:12
3
$\begingroup$

If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum. Wikipedia states that the set of functions that are computable in this model are incomparable with the set of functions that are computable in the usual model, and gives a citation where you can read more. It's not clear to me exactly how that result should be interpreted, though.

$\endgroup$
  • $\begingroup$ The BBS model, at least the popular version, bakes in discontinuity, and in any case is not about real numbers. It's about certain subfields of reals. If it were about reals, it would let you compute limits of sequences. (This is not to say that the models is useless. It is useful whenever we study computation with reals in which we have no intention to calculate limits. For instance, in computational geometry this would be the case, but usually not when we solve differential equations with iterative methods.) $\endgroup$ – Andrej Bauer Feb 23 at 8:09
2
$\begingroup$

It's a bit vague to talk about "models of universe". Let's stick to models of mathematics, as these are actually well understood. For example, we can ask about a topos (a model of a certain kind of set theory and higher-order logic, sufficient to develop theoretical physics) in which every map is continuous. Does it follow that some of the maps must be non-computable in such a topos?

No. In the realizability topos based on the computable version of Kleene's function realizability all maps are continuous (internally) and there is no non-computable map.

There are other toposes in which every map is continuous and there are also non-computable maps, for instance the realizability topos based on Kleene's function realizability.

In fact, the implication goes in the other direction: computable implies continuous. That is to say, if we allow ourselves some vagueness: in any universe in which all processes are computable, all processes are also continuous. (But not the other way around.)

$\endgroup$
  • $\begingroup$ I'd like to understand this better. In particular: how are continuity and computability defined internally to a topos? Could you point me to relevant literature? $\endgroup$ – Michael Bächtold Feb 23 at 10:16
  • 1
    $\begingroup$ In a topos you may interpret higher-order logic. You've got natural numbers as well. That's enough to define reals, and then express continuity in the usual way, with $\epsilon$ and $\delta$. You could look at Jaap van Oosten's book on realizability. $\endgroup$ – Andrej Bauer Feb 23 at 10:20
  • $\begingroup$ Ah, thanks. I was under the wrong impression that one could talk about continuity/computability of arbitrary internal maps... If I understand correctly it only applies to internal functions from naturals to naturals or reals to reals etc. $\endgroup$ – Michael Bächtold Feb 23 at 11:18
  • $\begingroup$ Well, there is also synthetic topology where you can speak about topology on any object and continuity of any map. $\endgroup$ – Andrej Bauer Feb 23 at 11:19
  • $\begingroup$ @AndrejBauer thanks for your answer. Do you know of any specific well known continous model that would satisfy the condition I posted in my question? ("The universe is a hypercomputer and then it is possible to build more powerful machines than Turing machines. For this it would be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said supercomputer as input")" $\endgroup$ – sztorwi Feb 23 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.