Problems in number theory from busy beaver competition

DOI10.2168/LMCS-11(4:10)2015zbMATH Open1448.03028arXiv1311.1029MaRDI QIDQ3460412FDOQ3460412

Pascal Michel

Publication date: 7 January 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1311.1029

Recommendations

• scientific article
• The Undecidability of the Generalized Collatz Problem
• Busy beaver competition and Collatz-like problems
• Tag systems and Collatz-like functions
• scientific article; zbMATH DE number 9859

zbMATH Keywords

busy beaverCollatz-like functions

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cited In (6)

• The large deviations law in number theory, computable functions of several arguments, and decoding
• Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons)
• Busy beaver competition and Collatz-like problems
• An automated approach to the Collatz conjecture
• An automated approach to the Collatz conjecture
• Struggling with the 3x + 1 problem

This page was built for publication: Problems in number theory from busy beaver competition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460412)