| 2009 | On Ladner's Result for a Class of Real Machines with Restricted Use of Constants. | Klaus Meer |
| 2009 | A Divergence Formula for Randomness and Dimension. | Jack H. Lutz |
| 2009 | Infima of | Jiang Liu, Shengling Wang, Guohua Wu |
| 2009 | The First Order Theories of the Medvedev and Muchnik Lattices. | Andrew E. M. Lewis, Andr Nies, Andrea Sorbi |
| 2009 | Relationship between Kanamori-McAloon Principle and Paris-Harrington Theorem. | Gyesik Lee |
| 2009 | Constructing New Aperiodic Self-simulating Tile Sets. | Grgory Lafitte, Michael Weiss |
| 2009 | A Gandy Theorem for Abstract Structures and Applications to First-Order Definability. | Oleg V. Kudinov, Victor L. Selivanov |
| 2009 | Ordinal Computability. | Peter Koepke |
| 2009 | Index Sets and Universal Numberings. | Sanjay Jain, Frank Stephan, Jason Teutsch |
| 2009 | An Application of Martin-Lf Randomness to Effective Probability Theory. | Mathieu Hoyrup, Cristobal Rojas |
| 2009 | Computability of Analytic Functions with Analytic Machines. | Tobias Grtner, Gnter Hotz |
| 2009 | Definability in the Local Theory of the | Hristo Ganchev |
| 2009 | Spectra of Algebraic Fields and Subfields. | Andrey N. Frolov, Iskander Sh. Kalimullin, Russell G. Miller |
| 2009 | Computable Exchangeable Sequences Have Computable de Finetti Measures. | Cameron E. Freer, Daniel M. Roy |
| 2009 | Fractals Generated by Algorithmically Random Brownian Motion. | Willem L. Fouch |
| 2009 | Equivalence Relations on Classes of Computable Structures. | Ekaterina B. Fokina, Sy-David Friedman |
| 2009 | Computability of Continuous Solutions of Higher-Type Equations. | Martn Htzel Escard |
| 2009 | On Stateless Multicounter Machines. | mer Egecioglu, Oscar H. Ibarra |
| 2009 | Graph States and the Necessity of Euler Decomposition. | Ross Duncan, Simon Perdrix |
| 2009 | Lowness for Demuth Randomness. | Rod Downey, Keng Meng Ng |
| 2009 | Members of Random Closed Sets. | David Diamondstone, Bjrn Kjos-Hanssen |
| 2009 | Cutting Planes and the Parameter Cutwidth. | Stefan S. Dantchev, Barnaby Martin |
| 2009 | Infinite-Time Turing Machines and Borel Reducibility. | Samuel Coskey |
| 2009 | Lower Bounds for Kernelizations and Other Preprocessing Procedures. | Yijia Chen, Jrg Flum, Moritz Mller |
| 2009 | Immunity for Closed Sets. | Douglas Cenzer, Rebecca Weber, Guohua Wu |