1. Infinite Time Turing Machines.Joel Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
    We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
    Export citation  
    Bookmark   40 citations  
  2.  82
    Infinite time Turing machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
    Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.
    Direct download (19 more)  
    Export citation  
    Bookmark   28 citations  
  3. 2008 Annual Meeting of the Association for Symbolic Logic-University of California, Irvine-Irvine, California-March 27-30, 2008-Abstracts. [REVIEW]Sam Buss, Stephen Cook, Jos Ferreirs, Andy Lewis, David Marker, Theodore Slaman & Jamie Tappenden - 2008 - Bulletin of Symbolic Logic 14 (3):418-437.
  4.  27
    Large cardinals and large dilators.Andy Lewis - 1998 - Journal of Symbolic Logic 63 (4):1496-1510.
    Applying Woodin's non-stationary tower notion of forcing, I prove that the existence of a supercompact cardinal κ in V and a Ramsey dilator in some small forcing extension V[G] implies the existence in V of a measurable dilator of size κ, measurable by κ-complete measures.
    Direct download (8 more)  
    Export citation  
  5.  8
    Isaac Newton Institute, Cambridge, UK July 2–6, 2012.George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen - 2013 - Bulletin of Symbolic Logic 19 (1).
    Direct download  
    Export citation  
  6.  4
    Nijmegen, The Netherlands July 27–August 2, 2006.Rodney Downey, Ieke Moerdijk, Boban Velickovic, Samson Abramsky, Marat Arslanov, Harvey Friedman, Martin Goldstern, Ehud Hrushovski, Jochen Koenigsmann & Andy Lewis - 2007 - Bulletin of Symbolic Logic 13 (2).
    Direct download (2 more)  
    Export citation