Publications

Paper reprints of these publications can be obtained by snail mail on request to pascalmichel314@gmail.com

  1. Borne supérieure de la complexité de la théorie de N muni de la relation de divisibilité (French) [Upper bound for the complexity of the theory of N with the divisibility relation]
    Model Theory and Arithmetic (Paris, 1979-1980), Lecture Notes in Mathematics No 890, Springer, 1981, 242-250.

  2. Six exposés sur la complexité algorithmique (French) [Six lectures on computational complexity]
    in : Introduction à la complexité algorithmique, P. Michel et J.-P. Ressayre, Séminaire de complexité algorithmique et de logique, 1986-1987-1988, Publications Mathématiques de l'Université Paris 7, No 30, 1989, 1-74.

  3. An NP-complete language accepted in linear time by a one-tape Turing machine
    Theoretical Computer Science 85 (1) 1991, 205-212.

  4. A survey of space complexity
    Theoretical Computer Science 101 (1) 1992, 99-132.

  5. Complexity of logical theories involving coprimality
    Theoretical Computer Science 106 (2) 1992, 221-241.

  6. Busy beaver competition and Collatz-like problems
    Archive for Mathematical Logic 32 (5) 1993, 351-367.

  7. Small Turing machines and generalized busy beaver competition
    Theoretical Computer Science 326 (1-3) 2004, 45-56.
    Preprint : .pdf.
    Abstract and references from the web site of Theoretical Computer Science.
    DOI No: 10.1016/j.tcs.2004.05.008.

  8. Computational complexity of logical theories of one successor and another unary function
    Archive for Mathematical Logic 46 (2) 2007, 123-148.
    Preprint : .pdf.
    Abstract from the web site of Archive for Mathematical Logic.
    DOI No: 10.1007/s00153-006-0031-1.

  9. Homology of groups and third busy beaver function
    International Journal of Algebra and Computation 20 (6) 2010, 769-791.
    Preprint : .pdf.
    Abstract from the web site of International Journal of Algebra and Computation.
    DOI No: 10.1142/S0218196710005868.

  10. (with Maurice Margenstern) Generalized 3x+1 functions and the theory of computation
    in: The Ultimate Challenge: The 3x+1 Problem, J.C. Lagarias (Ed.), AMS, 2010, 105-128.

  11. Problems in number theory from busy beaver competition
    Logical Methods in Computer Science 11 (4:10) 2015, 1-35.
    Article
    DOI No: 10.2168/LMCS-11(4:10)2015

Preprints

  1. The Busy Beaver Competition: a historical survey
    HAL , arXiv , Version 7, 75 pages, 2022.

  2. Simulation of the Collatz 3x+1 function by Turing machines
    HAL , arXiv , 8 pages, 2014.