Infinitary computability publications

  • Effective Mathemematics of the Uncountable
    • Effective Mathematics of the Uncountable, N.~Greenberg, J.~D.~Hamkins, D.~R.~Hirschfeldt, and R.~G.~Miller, Eds., Cambridge University Press, ASL Lecture Notes in Logic, 2013, vol. 41.  
      @BOOK{EMU,
      AUTHOR = {},
      editor = {N.~Greenberg and J.~D.~Hamkins and D.~R.~Hirschfeldt and R.~G.~Miller},
      TITLE = {Effective Mathematics of the Uncountable},
      PUBLISHER = {Cambridge University Press, ASL Lecture Notes in Logic},
      YEAR = {2013},
      volume = {41},
      number = {},
      series = {},
      address = {},
      edition = {},
      month = {},
      note = {},
      abstract = {},
      isbn = {9781107014510},
      price = {},
      keywords = {},
      source = {},
      }

  • Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
    • S. Coskey and J. D. Hamkins, “Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals,” in Effective mathematics of the uncountable, Assoc. Symbol. Logic, La Jolla, CA, 2013, vol. 41, pp. 33-49.  
      @incollection {CoskeyHamkins2013:ITTMandApplicationsToEquivRelations,
      AUTHOR = {Coskey, Samuel and Hamkins, Joel David},
      TITLE = {Infinite time {T}uring machines and an application to the
      hierarchy of equivalence relations on the reals},
      BOOKTITLE = {Effective mathematics of the uncountable},
      SERIES = {Lect. Notes Log.},
      VOLUME = {41},
      PAGES = {33--49},
      PUBLISHER = {Assoc. Symbol. Logic, La Jolla, CA},
      YEAR = {2013},
      MRCLASS = {03D30 (03D60 03E15)},
      MRNUMBER = {3205053},
      eprint = {1101.1864},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      url = {http://arxiv.org/abs/1101.1864},
      }

  • Infinite time decidable equivalence relation theory
    • S. Coskey and J. D. Hamkins, “Infinite time decidable equivalence relation theory,” Notre Dame J.~Form.~Log., vol. 52, iss. 2, pp. 203-228, 2011.  
      @ARTICLE{CoskeyHamkins2011:InfiniteTimeComputableEquivalenceRelations,
      AUTHOR = {Coskey, Samuel and Hamkins, Joel David},
      TITLE = {Infinite time decidable equivalence relation theory},
      JOURNAL = {Notre Dame J.~Form.~Log.},
      FJOURNAL = {Notre Dame Journal of Formal Logic},
      VOLUME = {52},
      YEAR = {2011},
      NUMBER = {2},
      PAGES = {203--228},
      ISSN = {0029-4527},
      MRCLASS = {03D65 (03D30 03E15)},
      MRNUMBER = {2794652},
      DOI = {10.1215/00294527-1306199},
      URL = {http://dx.doi.org/10.1215/00294527-1306199},
      eprint = "0910.4616",
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

  • Post's problem for ordinal register machines: an explicit approach
    • J. D. Hamkins and R. G. Miller, “Post’s problem for ordinal register machines: an explicit approach,” Ann.~Pure Appl.~Logic, vol. 160, iss. 3, pp. 302-309, 2009.  
      @ARTICLE{HamkinsMiller2009:PostsProblemForORMsExplicitApproach,
      AUTHOR = {Hamkins, Joel David and Miller, Russell G.},
      TITLE = {Post's problem for ordinal register machines: an explicit approach},
      JOURNAL = {Ann.~Pure Appl.~Logic},
      FJOURNAL = {Annals of Pure and Applied Logic},
      VOLUME = {160},
      YEAR = {2009},
      NUMBER = {3},
      PAGES = {302--309},
      ISSN = {0168-0072},
      CODEN = {APALD7},
      MRCLASS = {03D60 (03D10)},
      MRNUMBER = {2555781 (2010m:03086)},
      MRREVIEWER = {Robert S.~Lubarsky},
      DOI = {10.1016/j.apal.2009.01.004},
      URL = {http://dx.doi.org/10.1016/j.apal.2009.01.004},
      file = F
      }

  • 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
      }

  • A survey of infinite time Turing machines
    • J. D. Hamkins, “A Survey of Infinite Time Turing Machines,” in Machines, Computations, and Universality – 5th International Conference MCU 2007, Orleans, France, 2007, pp. 62-71.  
      @INPROCEEDINGS{Hamkins2007:ASurveyOfInfiniteTimeTuringMachines,
      AUTHOR = "Joel David Hamkins",
      TITLE = "A Survey of Infinite Time {T}uring Machines",
      BOOKTITLE = "Machines, Computations, and Universality - 5th International Conference MCU 2007",
      YEAR = "2007",
      editor = "{J\'er\^ ome} Durand-Lose and Maurice Margenstern",
      volume = "4664",
      number = "",
      series = "Lecture Notes in Computer Science",
      pages = "62--71",
      address = "Orleans, France",
      month = "",
      organization = "",
      publisher = "",
      note = "",
      abstract = "",
      keywords = "",
      doi = {10.1007/978-3-540-74593-8_5},
      ee = {http://dx.doi.org/10.1007/978-3-540-74593-8_5},
      crossref = {DBLP:conf/mcu/2007},
      file = F
      }

  • The complexity of quickly decidable ORM-decidable sets
    • J. D. Hamkins, D. Linetsky, and R. Miller, “The Complexity of Quickly Decidable ORM-Decidable Sets,” in Computation and Logic in the Real World – Third Conference of Computability in Europe CiE 2007, Siena, Italy, 2007, pp. 488-496.  
      @INPROCEEDINGS{HamkinsLinetskyMiller2007:ComplexityOfQuicklyDecidableORMSets,
      AUTHOR = "Joel David Hamkins and David Linetsky and Russell Miller",
      TITLE = "The Complexity of Quickly Decidable {ORM}-Decidable Sets",
      BOOKTITLE = "Computation and Logic in the Real World - Third Conference of Computability in Europe CiE 2007",
      YEAR = "2007",
      editor = "Barry Cooper and Benedikt {L\"owe} and Andrea Sorbi",
      volume = "4497",
      number = "",
      series = "Proceedings, Lecture Notes in Computer Science",
      pages = "488--496",
      address = "Siena, Italy",
      month = "",
      organization = "",
      publisher = "",
      note = "",
      abstract = "",
      keywords = "",
      doi = {10.1007/978-3-540-73001-9_51},
      ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_51},
      crossref = {DBLP:conf/cie/2007},
      bibsource = {DBLP, http://dblp.uni-trier.de},
      file = F
      }

  • Post's Problem for Ordinal Register Machines
    • J. D. Hamkins and R. Miller, “Post’s Problem for Ordinal Register Machines,” in Computation and Logic in the Real World—Third Conference of Computability in Europe CiE 2007, Siena, Italy, 2007, pp. 358-367.  
      @INPROCEEDINGS{HamkinsMiller2007:PostsProblemForORMs,
      AUTHOR = "Joel David Hamkins and Russell Miller",
      TITLE = "Post's Problem for Ordinal Register Machines",
      BOOKTITLE = "Computation and Logic in the Real World---Third Conference of Computability in Europe CiE 2007",
      YEAR = "2007",
      editor = "Barry Cooper and Benedikt {L\"owe} and Andrea Sorbi",
      volume = "4497",
      number = "",
      series = "Proceedings, Lecture Notes in Computer Science",
      address = "Siena, Italy",
      month = "",
      organization = "",
      publisher = "",
      note = "",
      abstract = "",
      keywords = "",
      pages = {358-367},
      doi = {10.1007/978-3-540-73001-9_37},
      ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_37},
      file = F
      }

  • ${\rm P}\neq{\rm NP}\cap\textrm{co-}{\rm NP}$ for infinite time Turing machines
    • V. Deolalikar, J. D. Hamkins, and R. Schindler, “${\rm P}\neq{\rm NP}\cap$ co-NP for infinite time Turing machines,” J.~Logic Comput., vol. 15, iss. 5, pp. 577-592, 2005.  
      @ARTICLE{DeolalikarHamkinsSchindler2005:NPcoNP,
      AUTHOR = {Deolalikar, Vinay and Hamkins, Joel David and Schindler, Ralf},
      TITLE = {{${\rm P}\neq{\rm NP}\cap$} co-{NP} for infinite time {T}uring machines},
      JOURNAL = {J.~Logic Comput.},
      FJOURNAL = {Journal of Logic and Computation},
      VOLUME = {15},
      YEAR = {2005},
      NUMBER = {5},
      PAGES = {577--592},
      ISSN = {0955-792X},
      MRCLASS = {68Q05 (03D05 68Q15)},
      MRNUMBER = {2172411 (2006k:68026)},
      MRREVIEWER = {Peter G.~Hinman},
      DOI = {10.1093/logcom/exi022},
      URL = {http://dx.doi.org/10.1093/logcom/exi022},
      month = "October",
      eprint = {math/0307388},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      file = F,
      }

  • Infinitary computability with infinite time Turing machines
    • J. D. Hamkins, “Infinitary computability with infinite time Turing machines,” in New Computational Paradigms, Amsterdam, 2005.  
      @INPROCEEDINGS{Hamkins2005:InfinitaryComputabilityWithITTM,
      AUTHOR = "Joel David Hamkins",
      TITLE = "Infinitary computability with infinite time {T}uring machines",
      BOOKTITLE = "New Computational Paradigms",
      YEAR = "2005",
      editor = "Cooper, Barry S.~and {L\"owe}, Benedikt",
      volume = "3526",
      number = "",
      series = "LNCS",
      pages = "",
      address = "Amsterdam",
      month = "June 8-12",
      organization = "CiE",
      publisher = "Springer-Verlag",
      isbn = "3-540-26179-6",
      note = "",
      abstract = "",
      keywords = "",
      doi = {10.1007/11494645_22},
      ee = {http://dx.doi.org/10.1007/11494645_22},
      crossref = {DBLP:conf/cie/2005},
      file = F
      }

  • Supertask computation
    • J. D. Hamkins, “Supertask computation,” in Classical and new paradigms of computation and their complexity hierarchies, Dordrecht, 2004, pp. 141-158. (Papers of the conference “Foundations of the Formal Sciences III” held in Vienna, September 21-24, 2001)  
      @INPROCEEDINGS{Hamkins2004:SupertaskComputation,
      AUTHOR = {Hamkins, Joel David},
      TITLE = {Supertask computation},
      BOOKTITLE = {Classical and new paradigms of computation and their complexity hierarchies},
      SERIES = {Trends Log.~Stud.~Log.~Libr.},
      VOLUME = {23},
      PAGES = {141--158},
      PUBLISHER = {Kluwer Acad.~Publ.},
      ADDRESS = {Dordrecht},
      YEAR = {2004},
      MRCLASS = {03D10 (03D25 68Q05)},
      MRNUMBER = {2155535},
      DOI = {10.1007/978-1-4020-2776-5_8},
      URL = {http://dx.doi.org/10.1007/978-1-4020-2776-5_8},
      note = {Papers of the conference ``Foundations of the Formal Sciences III'' held in Vienna, September 21-24, 2001},
      eprint = {math/0212049},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      file = F,
      }

  • ${\rm P}^f\neq {\rm NP}^f$ for almost all $f$
    • J. D. Hamkins and P. D. Welch, “${\rm P}^f\neq {\rm NP}^f$ for almost all $f$,” MLQ Math.~Log.~Q., vol. 49, iss. 5, pp. 536-540, 2003.  
      @ARTICLE{HamkinsWelch2003:PfneqNPf,
      AUTHOR = {Hamkins, Joel David and Welch, Philip D.},
      TITLE = {{${\rm P}^f\neq {\rm NP}^f$} for almost all {$f$}},
      JOURNAL = {MLQ Math.~Log.~Q.},
      FJOURNAL = {MLQ.~Mathematical Logic Quarterly},
      VOLUME = {49},
      YEAR = {2003},
      NUMBER = {5},
      PAGES = {536--540},
      ISSN = {0942-5616},
      MRCLASS = {03D65 (03D10 03E45 68Q05 68Q15)},
      MRNUMBER = {1998405 (2004m:03163)},
      MRREVIEWER = {Peter G.~Hinman},
      DOI = {10.1002/malq.200310057},
      URL = {http://dx.doi.org/10.1002/malq.200310057},
      eprint = {math/0212046},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

  • Post's problem for supertasks has both positive and negative solutions
    • J. D. Hamkins and A. Lewis, “Post’s problem for supertasks has both positive and negative solutions,” Arch.~Math.~Logic, vol. 41, iss. 6, pp. 507-523, 2002.  
      @article{HamkinsLewis2002:PostProblem,
      AUTHOR = {Hamkins, Joel David and Lewis, Andrew},
      TITLE = {Post's problem for supertasks has both positive and negative solutions},
      JOURNAL = {Arch.~Math.~Logic},
      FJOURNAL = {Archive for Mathematical Logic},
      VOLUME = {41},
      YEAR = {2002},
      NUMBER = {6},
      PAGES = {507--523},
      ISSN = {0933-5846},
      CODEN = {AMLOEH},
      MRCLASS = {03D10 (68Q05)},
      MRNUMBER = {1923194 (2003f:03052)},
      MRREVIEWER = {Robert M.~Baer},
      DOI = {10.1007/s001530100112},
      URL = {http://dx.doi.org/10.1007/s001530100112},
      eprint = {math/9808128},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

  • Infinite time Turing machines
    • J. D. Hamkins, “Infinite time Turing machines,” Minds and Machines, vol. 12, iss. 4, pp. 521-539, 2002. (special issue devoted to hypercomputation)  
      @ARTICLE{Hamkins2002:Turing,
      author = {Joel David Hamkins},
      title = {Infinite time {T}uring machines},
      journal = {Minds and Machines},
      year = {2002},
      volume = {12},
      number = {4},
      pages = {521--539},
      month = {},
      note = {special issue devoted to hypercomputation},
      key = {},
      annote = {},
      eprint = {math/0212047},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

  • Infinite time Turing machines with only one tape
    • J. D. Hamkins and D. E. Seabold, “Infinite Time Turing Machines With Only One Tape,” Mathematical Logic Quarterly, vol. 47, iss. 2, pp. 271-287, 2001.  
      @article{HamkinsSeabold2001:OneTape,
      author = {Hamkins, Joel David and Seabold, Daniel Evan},
      title = {Infinite Time Turing Machines With Only One Tape},
      journal = {Mathematical Logic Quarterly},
      volume = {47},
      number = {2},
      publisher = {WILEY-VCH Verlag Berlin GmbH},
      issn = {1521-3870},
      MRNUMBER = {1829946 (2002f:03074)},
      url = {http://dx.doi.org/10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6},
      doi = {10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6},
      pages = {271--287},
      keywords = {One-tape infinite Turing machine, Supertask computation},
      year = {2001},
      eprint = {math/9907044},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

  • Infinite time Turing machines
    • J. D. Hamkins and A. Lewis, “Infinite time Turing machines,” J.~Symbolic Logic, vol. 65, iss. 2, pp. 567-604, 2000.  
      @article {HamkinsLewis2000:InfiniteTimeTM,
      AUTHOR = {Hamkins, Joel David and Lewis, Andy},
      TITLE = {Infinite time {T}uring machines},
      JOURNAL = {J.~Symbolic Logic},
      FJOURNAL = {The Journal of Symbolic Logic},
      VOLUME = {65},
      YEAR = {2000},
      NUMBER = {2},
      PAGES = {567--604},
      ISSN = {0022-4812},
      CODEN = {JSYLA6},
      MRCLASS = {03D10 (03D25 68Q05)},
      MRNUMBER = {1771072 (2001g:03072)},
      MRREVIEWER = {Robert M.~Baer},
      DOI = {10.2307/2586556},
      URL = {http://dx.doi.org/10.2307/2586556},
      eprint = {math/9808093},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      }

One thought on “Infinitary computability publications

  1. Pingback: A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020 | Joel David Hamkins

Leave a Reply