My [past attempts][1] to really understand mathematical, and philosophical existence ended by a retreat to the reverse mathematics program. But after reading Max Tegmark's attempt in [The Mathematical Universe][2] to use Turing machines to define existence, I started to wonder again in which ways Turing machines can help to clarify different notions of existence. Tegmark's attempt feels a bit unpolished to me, *so I wonder whether his ideas (or similar ideas) have been worked out in a more polished or more mathematical form somewhere?* But this question is not a reference request, it is a question about how Turing machines can be used to clarify different notions of existence. The *cursive questions* below show points where I'm currently stuck, but I'm also interested in completely different approaches (like Tegmark's).

Let a $\Pi_1^0$ sentence be a sentence asserting that some given Turing machine never halts at the empty input tape. Let a $\Pi_2^0$ sentence be a sentence asserting that some given Turing machine halts at every input tape. Let mathematical existence mean no more than consistency of an otherwise arbitrary definition. Let physical existence be based on observations and experience. (Remember those arguments evoking the number of atoms in the universe?) Let philosophical existence mean that you either explicitly define what you mean by that word (like Quine did in [*On What There Is*][3]) or alternatively that you use your implicit ontological commitments (like Descartes did in [*ego cogito, ergo sum*][4]).

A Turing machine seem to have some form of potential physical existence, but an oracle for deciding $\Pi_1^0$ or $\Pi_2^0$ sentences should not claim any form of physical existence. *Or do I miss something here?* The question whether some postulated structure (like ZFC) has mathematical existence is equivalent to a $\Pi_1^0$ sentence. The link between consistency and existence is provided by the model existence theorem of first order logic (i.e. the completeness theorem). This theorem doesn't seem equivalent to a $\Pi_1^0$ sentence. *Is it equivalent to a $\Pi_2^0$ sentence?* It is equivalent to the weak König's lemma in the context of reverse mathematics, but this doesn't look like a $\Pi_2^0$ sentence either. *Is the assumption of the existence of an oracle for deciding $\Pi_2^0$ sentences sufficient for proving the model existence theorem (or the weak König's lemma)?*

  [1]: http://philosophy.stackexchange.com/questions/14529/which-ontological-commitments-are-embedded-in-a-straightforward-turing-machine-m
  [2]: http://arxiv.org/abs/0704.0646
  [3]: https://tu-dresden.de/die_tu_dresden/fakultaeten/philosophische_fakultaet/iph/thph/braeuer/lehre/metameta/Quine%20-%20On%20What%20There%20Is.pdf
  [4]: http://philosophy.stackexchange.com/questions/14101/are-there-any-other-things-like-cogito-ergo-sum-that-we-can-be-certain-of/14461#14461