Infinite time computable model theory

  • J. D. Hamkins, R. Miller, D. Seabold, and S. Warner, “Infinite time computable model theory,” in New Computational Paradigms: Changing Conceptions of What is Computable, S. B. \. Cooper, B. Löwe, and A. Sorbi, Eds., New York: Springer, 2008, pp. 521-557.  
    @INCOLLECTION{HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory,
    AUTHOR = {Hamkins, Joel David and Miller, Russell and Seabold, Daniel
    and Warner, Steve},
    TITLE = {Infinite time computable model theory},
    BOOKTITLE = "New Computational Paradigms: Changing Conceptions of What is Computable",
    PAGES = {521--557},
    PUBLISHER = {Springer},
    ADDRESS = {New York},
    YEAR = {2008},
    MRCLASS = {03C57 (03D10)},
    MRNUMBER = {2762096},
    editor = {S.B.\ Cooper and Benedikt L\"owe and Andrea Sorbi},
    isbn = "0-387-36033-6",
    file = F
    }

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines,  which provide infinitary notions of computability for structures built on the reals  $\mathbb{R}$. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time  computable analogue of the Completeness Theorem, turn out to be  independent of ZFC.

One thought on “Infinite time computable model theory

Leave a Reply