Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons)

DOI10.1016/J.TCS.2016.07.016zbMATH Open1348.68053arXiv1602.03228OpenAlexW2261544458WikidataQ115046237 ScholiaQ115046237MaRDI QIDQ306278FDOQ306278

Authors: James Harland 

Publication date: 31 August 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The busy beaver is a well-known specific example of a non-computable function. Whilst many aspect of this problem have been investigated, it is not always easy to find thorough and convincing evidence for the claims made about the maximality of particular machines, and the phenomenal size of some of the numbers involved means that it is not obvious that the problem can be feasibly addressed at all. In this paper we address both of these issues. We discuss a framework in which the busy beaver problem and similar problems may be addressed, and the appropriate processes for providing evidence of claims made. We also show how a simple heuristic, which we call the observant otter, can be used to evaluate machines with an extremely large number of execution steps required to terminate. We also show empirical results for an implementation of this heuristic which show how this heuristic is effective for all known `monster' machines.

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

Recommendations

• scientific article; zbMATH DE number 8896
• scientific article; zbMATH DE number 1927169
• A note on busy beavers and other creatures
• Improved bounds for functions related to busy beavers
• Busy beaver competition and Collatz-like problems

zbMATH Keywords

busy beaverplacid platypusTuring machines

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• A proof of the Kepler conjecture
• Title not available (Why is that?)
• Complexity of Langton's ant
• Title not available (Why is that?)
• Improved bounds for functions related to busy beavers
• Problems in number theory from busy beaver competition
• Computability and Logic
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on busy beavers and other creatures
• Looking for busy beavers. A socio-philosophical study of a computer-assisted proof
• On non-computable functions
• Computer Studies of Turing Machine Problems
• Busy beaver competition and Collatz-like problems

Cited In (5)

• Busy beavers and Kolmogorov complexity
• Improved bounds for functions related to busy beavers
• Generating candidate busy beaver machines (or how to build the zany zoo)
• Busy beavers gone wild
• Title not available (Why is that?)

Uses Software

• Flyspeck
• kepler98

This page was built for publication: Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons)

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