Abstract

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