Switch to: References

Add citations

You must login to add citations.
  1. Transfinite recursion and computation in the iterative conception of set.Benjamin Rin - 2015 - Synthese 192 (8):2437-2462.
    Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • The computational strengths of α-tape infinite time Turing machines.Benjamin Rin - 2014 - Annals of Pure and Applied Logic 165 (9):1501-1511.
    In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that Tα≻TωTα≻Tω, the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • The Limits of Computation.Andrew Powell - 2022 - Axiomathes 32 (6):991-1011.
    This article provides a survey of key papers that characterise computable functions, but also provides some novel insights as follows. It is argued that the power of algorithms is at least as strong as functions that can be proved to be totally computable in type-theoretic translations of subsystems of second-order Zermelo Fraenkel set theory. Moreover, it is claimed that typed systems of the lambda calculus give rise naturally to a functional interpretation of rich systems of types and to a hierarchy (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Taming Koepke's Zoo II: Register machines.Merlin Carl - 2022 - Annals of Pure and Applied Logic 173 (3):103041.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • The basic theory of infinite time register machines.Merlin Carl, Tim Fischbach, Peter Koepke, Russell Miller, Miriam Nasfi & Gregor Weckbecker - 2010 - Archive for Mathematical Logic 49 (2):249-273.
    Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Realisability for infinitary intuitionistic set theory.Merlin Carl, Lorenzo Galeotti & Robert Passmann - 2023 - Annals of Pure and Applied Logic 174 (6):103259.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.
    We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Supertasks.Jon Pérez Laraudogoitia - 2008 - Stanford Encyclopedia of Philosophy.
    Direct download  
     
    Export citation  
     
    Bookmark   18 citations