Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Am starting an entry computable physics. For the moment this is essentialy a glorified lead-in for
I had had the feeling that most previous literature on computability in physics is suffering from being not well informed of the relevant mathematical concepts, but then I found
which seems to be sober, well-informed and sensible. The main drawback seems to be, to me, that the author looks only at type-I computability and not really seriously at quantum physics. Both of this is what Streicher’s note above aims to do!
If anyone has more pointers to decent literature on this topic, please drop me a note.
Here is what it currently has in the entry text computable physics:
The following idea or observation or sentiment has been expressed independently by many authors. We quote from Szudzik 10, section 2:
The central problem is that physical models use real numbers to represent the values of observable quantities, $[...]$ Careful consideration of this problem, however, reveals that the real numbers are not actually necessary in physical models. Non-negative integers suffice for the representation of observable quantities because numbers measured in laboratory experiments necessarily have only finitely many digits of precision.
Diverse conclusions have been drawn from this. One which seems useful and well-informed by the theory of computability in mathematics is the following (further quoting from Szudzik 10, section 2)
So, we suffer no loss of generality by restricting the values of all observable quantities to be expressed as non-negative integers — the restriction only forces us to make the methods of error analysis, which were tacitly assumed when dealing with real numbers, an explicit part of each model.
In type-I computability the computable functions are partial recursive functions and in view of this some authors conclude (and we still quote Szudzik 10, section 2) for this:
To show that a model $[$ of physics $]$ is computable, the model must somehow be expressed using recursive functions.
However, in computability theory there is also the concept type-II computable functions used in the field of “constructive analysis”, “computable analysis”. This is based on the idea that for instance for specifying computable real numbers as used in physics, an algorithm may work not just on single natural numbers, but indefinitely on sequences of them, producing output that is in each step a finite, but in each next step a more accurate approximation.
!include computable mathematics – table
This concept of type-II computability is arguably closer to actual practice in physics.
Of course there is a wide-spread (but of course controversial) vague speculation (often justified by alluding to expected implications of quantum gravity on the true microscopic nature of spacetime and sometimes formalized in terms of cellular automata, e.g. Zuse 67) that in some sense the observable universe is fundamentally “finite”, so that in the end computability is a non-issue in physics as one is really operating on a large but finite set of states.
However, since fundamental physics is quantum physics and since quantum mechanics with its wave functions, Hilbert spaces and probability amplitudes invokes (functional) analysis and hence non-finite mathematics even when describing the minimum of a physical system with only two possible configurations (a “qbit”) a strict finitism perspective on fundamental physics runs into severe problems and concepts of computable analysis would seem to be necessary for discussing computability in physics.
This issue of computable quantum physics has only more recently been considered in (Streicher 12), where it is shown that at least a fair bit of the Hilbert space technology of quantum mechanics/quantum logic sits inside the function realizability topos $RT(\mathcal{K}_2)$.
I have expanded the entry computable physics a bit more, thanks to input which I received from Bas Spitters and Stam Nicolis in this g+ discussion.
Namely I added pointer to and brief comment on results that show that standard physical evolution operators are not type-I computable, and pointers to followup-results by Weihrauch and Zhong which show that however they are type-II computable.
Also added a pointer to a seminal talk by Feynman on computable physics and to the slide where he implcitly seems to be running into this issue.
With Stam I am having discussion to the extent “but its OBVIOUS that type-II is the right notion of computability in physics” and I suppose this is indeed the conclusion one must come to, but the fact is that ranging all the way from the old masters via research articles such as in the above to contemporary excitement in mass media, people keep (maybe implcitily) sticking to the concept of type-I computability in physics. I hope the entry computable physics serves to discuss this issue a bit now.
Based on this I have now also given Church-Turing thesis an entry, though of course this is at best a very first step for the moment.
1 to 2 of 2