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

DOI10.1016/J.TCS.2016.07.016MaRDI QIDQ306278zbMATH OpenOpenAlexWikidataFDO

Authors James Harland

Publication date 31 August 2016

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

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

zbMATH Keywords

busy beaver placid platypus Turing machines

Mathematics Subject Classification ID

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

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.

Recommendations

Cites work

Cited in

(5)

Describes a project that uses

Uses Software

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)