Busy beaver competition and Collatz-like problems
type: Item
instance of: scholarly article
title: Busy beaver competition and Collatz-like problems
zbMATH Open document ID: 0779.03009
DOI: 10.1007/BF01409968
author: Pascal Michel
published in: Archive for Mathematical Logic
publication date: 1993-12-09T00:00:00Z
review text: The Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior of the repeated iteration of Collatz-like functions, that is functions defined by cases according to congruence classes.
reviewed by: Michel Planat
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 11B99
zbMATH DE Number: 444901
zbMATH Keywords: Busy Beaver Competition
zbMATH Keywords: Turing machines
zbMATH Keywords: halting problem
zbMATH Keywords: repeated iteration of Collatz-like functions
MaRDI profile type: Publication
cites work: The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
cites work: Q4203822
cites work: Q4103618
cites work: Q3862379
cites work: The 3x + 1 Problem and Its Generalizations
cites work: Computer Studies of Turing Machine Problems
cites work: An unsolved problem on the powers of 3/2
cites work: Q3971350
cites work: Castor quadruplorum
cites work: Solvability of the halting problem for certain classes of Turing machines
cites work: MINSKY'S SMALL UNIVERSAL TURING MACHINE
cites work: Q3661558
Recommended article: Busy Beavers and Kolmogorov Complexity
Recommended article: Q3637636
Recommended article: Small Turing machines and generalized busy beaver competition
Recommended article: Dynamical systems approach to the busy beaver problem
Recommended article: The Collatz problem
Recommended article: Problems in number theory from busy beaver competition
Recommended article: Some results on the Collatz problem
Recommended article: Some remarks about the Collatz problem
Recommended article: Some natural generalizations of the Collatz problem
description: scientific article; zbMATH DE number 444901