1. Digital simulation of analog computation and church's thesis.Lee A. Rubel - 1989 - Journal of Symbolic Logic 54 (3):1011-1017.
    Church's thesis, that all reasonable definitions of “computability” are equivalent, is not usually thought of in terms of computability by acontinuouscomputer, of which the general-purpose analog computer (GPAC) is a prototype. Here we prove, under a hypothesis of determinism, that the analytic outputs of aC∞GPAC are computable by a digital computer.In [POE, Theorems 5, 6, 7, and 8], Pour-El obtained some related results. (The proof there of Theorem 7 depends on her Theorem 2, for which the proof in [POE] is (...)
    Direct download (8 more)  
    Export citation  
    Bookmark   11 citations  
  2. On the ring of differentially-algebraic entire functions.Lee A. Rubel - 1992 - Journal of Symbolic Logic 57 (2):449-451.
  3.  13
    Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
    For a set A of non-negative integers, let D be the set of non-negative differences of elements of A. Clearly, if A is computable, then D is computably enumerable. We show that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set of the complement of (...)
    Direct download (4 more)  
    Export citation