Pascal Michel - Problems in number theory from busy beaver competition

lmcs:1611 - Logical Methods in Computer Science, December 14, 2015, Volume 11, Issue 4 - https://doi.org/10.2168/LMCS-11(4:10)2015
Problems in number theory from busy beaver competitionArticle

Authors: Pascal Michel

    By introducing the busy beaver competition of Turing machines, in 1962, Rado defined noncomputable functions on positive integers. The study of these functions and variants leads to many mathematical challenges. This article takes up the following one: How can a small Turing machine manage to produce very big numbers? It provides the following answer: mostly by simulating Collatz-like functions, that are generalizations of the famous 3x+1 function. These functions, like the 3x+1 function, lead to new unsolved problems in number theory.


    Volume: Volume 11, Issue 4
    Published on: December 14, 2015
    Submitted on: March 11, 2015
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • AIM - AI-driven Multi-factor peptide manufacturing platform; Code: 103521

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1223 times.
    This article's PDF has been downloaded 971 times.