Timeline for Can Turing machines clarify mathematical, philosophical, and physical existence?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:42 | history | edited | CommunityBot |
replaced http://philosophy.stackexchange.com/ with https://philosophy.stackexchange.com/
|
|
| Mar 22, 2016 at 23:13 | vote | accept | Thomas Klimpel | ||
| Mar 20, 2016 at 16:24 | answer | added | Thomas Klimpel | timeline score: 3 | |
| Mar 12, 2016 at 13:36 | comment | added | Thomas Klimpel | @AndrejBauer I think I have it now. Given some (computable) axiom system for ZFC, the model existence theorem can construct a Turing machine with access to an oracle for deciding $\Pi_1^0$ sentences, and that machine can be queried with ZFC formulas (which may include special constants $c_\phi$ denoting not necessarily distinct but actually existing sets, in fact all existing sets), and will consistently answer those queries with "true" or "false" after finitely many steps. (If ZFC is inconsistent, then it will answer all queries with "inconsistent" instead). | |
| Mar 12, 2016 at 11:48 | comment | added | Andrej Bauer | Perhaps you're just asking about reverse mathematics? Have a look at en.wikipedia.org/wiki/Reverse_mathematics where it is explained that Gödel's completeness theorem follows from weak König's lemma $\mathsf{WKL}_0$ (over the base theory $\mathsf{RCA}_0$). | |
| Mar 12, 2016 at 9:45 | comment | added | Thomas Klimpel | @მამუკა ჯიბლაძე The physical random sources are relevant, because Turing machines (with oracles for $\Pi_\alpha^0$ sentences) have a hard time emulating them. If we would switch to game theory with two players (i.e. two Turing machines playing some game against each other), then access to a random source which the opponent (i.e. the other Turing machine) cannot predict can be advantageous. That's why randomized algorithms sometimes have advantages over deterministic algorithms. | |
| Mar 12, 2016 at 9:30 | comment | added | Thomas Klimpel | @AndrejBauer My current guess is that the existence of Turing machines with oracles for $\Pi_\alpha^0$ sentences for some suitable ordinal number $\alpha$ is sufficient for proving the model existence theorem. If it works out, it would be interesting to know whether $\alpha=\omega^\omega$ is required, or whether already $\alpha=\omega$ or $\alpha=2$ is enough. But maybe the "correct" answer should go into a completely different direction? Believing in existence of mutually inconsistent entities is no problem (to me), physical and mathematical existence take place in different universes anyway. | |
| Mar 12, 2016 at 9:12 | comment | added | Thomas Klimpel | @NoahSchweber The "equivalence" between consistency of ZFC and the corresponding $\Pi_0^1$ sentence can be proved without relying on set theory and choice principles. The hope was that the set theory and choice principle required for the model existence theorem can be encoded into a $\Pi_2^0$ sentence, and the "equivalence" be proved again without relying on any choice principles or set theory. I got the impression that it somehow doesn't work out without using some base theory, hence I guess it is not "equivalent" to a $\Pi_2^0$ sentence in the same sense as the other "equivalence". | |
| Mar 12, 2016 at 7:48 | comment | added | Andrej Bauer | It's a bit strange to equate consistency with existence, as then at the very least we have to believe in existence of mutually incinsistent entitites. In any case, I do not understand what is being asked here. It sounds as if you are asking about the logical complexity of Gödel's completeness theorem (every consistent first-order theory has a set-theoretic model), or maybe what it takes to prove it? | |
| Mar 12, 2016 at 7:01 | comment | added | მამუკა ჯიბლაძე | @ThomasKlimpel May I ask you to explain what exactly do you mean by physical random sources and why are they relevant? | |
| Mar 12, 2016 at 5:39 | comment | added | Noah Schweber | "Equivalent" in what sense? Since the model existence theorem is true, it is equivalent to lots of $\Pi^0_1$ sentences - for example, the sentence asserting that the Turing machine which on any input halts automatically, halts on input zero. Presumably, you mean equivalent over some base theory - but then you need to specify that theory! | |
| Mar 12, 2016 at 0:54 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
Simplified question by removing the part about Max Tegmark. Made a clearer connection to the question in the title.
|
| Mar 12, 2016 at 0:51 | history | rollback | Thomas Klimpel |
Rollback to Revision 1
|
|
| Mar 6, 2016 at 23:47 | comment | added | Thomas Benjamin | Also Tien D. Kieu's paper "Computing the noncomputable" (arXiv:quant-ph/0203034v4/8 Oct 2003) regarding quantum computation. | |
| Mar 6, 2016 at 23:39 | comment | added | Thomas Benjamin | (cont.) these 'Oracles' somewhere in nature (or if they exist at all....). | |
| Mar 6, 2016 at 23:37 | comment | added | Thomas Benjamin | @ThomasKlimpel: In thinking about these 'Oracles', you might want to take a look at these papers by Marian Boykan Pour-El and Ian Richards: "Noncomputability in Analysis and Physics: A Complete Determination of the Class of Noncomputable Linear Operators" [Advances in Mathematics 48, 44-74 (1986)], and "The Wave Equation with Computable Initial Data Such That its Unique Solution is Not Computable" [Advances in Mathematics 39, 215-239 (1983)], then ask yourself, "What physical processes (if any) are embodied by the results in these papers". Perhaps these papers will help you discover | |
| Mar 6, 2016 at 23:08 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
Made it clearer what I want to know, because I guess this was the reason for the downvote (and the absence of answers)
|
| Mar 6, 2016 at 16:08 | comment | added | Thomas Klimpel | @usul By an "oracle" for $\Pi_1^0$ sentences, I mean some (mathematical or physical) way to decide the truth of arbitrary $\Pi_1^0$ sentences. Denying the physical existence of such oracles is an intuitionistic position, denying the existence of arbitrary Turing machines would be an ultrafinitistic position. But I might be willing to grant the existence of physical random sources, which even all those hypothetical oracle Turing machines cannot provide. | |
| Mar 6, 2016 at 14:22 | comment | added | usul | You contrast physical existence of TMs and an "oracle" for $\Pi_1^0$ or $\Pi_2^0$ sentences", but depending on what you mean by oracle, I have trouble understanding this connection. After all, given a TM, how do we check that it always halts on any input, or never halts on any input? In general we cannot, either in a physical sense (by running it to see) or in a mathematical sense (by trying to prove it). So the connection is murky to me. | |
| Mar 6, 2016 at 11:05 | comment | added | Thomas Klimpel | @ThomasBenjamin The intention is to better understand in which ways Turing machines can help to clarify different notions of existence. I'm especially interested in connections to the model existence theorem of first order logic. Also physical existence is somewhat important to me in this context, but I slightly fear inconclusive conjectures here, because our current understanding of physics is incomplete in this respect. | |
| Mar 6, 2016 at 10:50 | comment | added | Thomas Benjamin | By the way, what would happen to Tegmark's Theses if Church's Thesis were false? | |
| Mar 6, 2016 at 10:46 | comment | added | Thomas Benjamin | What, then, is the intention behind this question? | |
| Mar 6, 2016 at 10:41 | comment | added | Thomas Klimpel | @ThomasBenjamin Let's just assume that the Church's Thesis holds. Let's also assume that mathematical existence is a prerequisite for physical or philosophical existence. Of course, we could get philosophical subtle and question those assumptions, but that is not the intention behind this question. | |
| Mar 6, 2016 at 10:30 | comment | added | Thomas Benjamin | I would posit the answer to your question to be yes, if Church's Thesis holds. | |
| Mar 6, 2016 at 9:59 | history | asked | Thomas Klimpel | CC BY-SA 3.0 |