From Harvey Friedman's [manuscript][1] on "Order Invariant Relations and Incompleteness":
> DEFINITION 4.4. A $\Pi_1^0$ sentence is a sentence asserting that some given Turing machine never halts at the empty input tape. A $\Pi_2^0$ sentence is 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*][2]) or alternatively that you use your implicit ontological commitments (like Descartes did in [*ego cogito, ergo sum*][3]).

A Turing machine seems 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?*

The two *questions* above feel reasonably precise and answerable to me: Yes, I'm missing something! No, the model existence theorem is not equivalent to a $\Pi_2^0$ sentence! OK, but where else can one draw the line between physical and mathematical (or philosophical) existence? OK, but what is the connection between the model existence theorem and (oracle) Turing machines?

**Edit:** The part of the question about how Max Tegmark uses Turing machines to define existence has been removed, because it made the question less clear and less self-contained.


  [1]: https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
  [2]: https://tu-dresden.de/die_tu_dresden/fakultaeten/philosophische_fakultaet/iph/thph/braeuer/lehre/metameta/Quine%20-%20On%20What%20There%20Is.pdf
  [3]: http://philosophy.stackexchange.com/questions/14101/are-there-any-other-things-like-cogito-ergo-sum-that-we-can-be-certain-of/14461#14461