Brute Force is not Ignorance

Abstract. Chaitin’s notion of program elegance, that is of the smallest program to satisfy some specification, does not explicitly take account of the balance between a formal notation’s expressive power and the richness of its semantics. To explore this wider space of elegance, we are investigating realisations of the Busy Beaver game (BBG) which involves finding programs of given size that produce maximal outputs. Like elegance, BBG is undecidable. Canonically, BBG is represented us-ing Turing machines, but there has been very little investigation into alternative formulations. Thus, we are exploring BBG in a number of classic models of computability, using empirical and analytic heuristics to find optimal BBG instances. Such experiments will be used as a basis for drawing comparisons between the expressive power of Turing ma-chines and other models of computation with a view to gaining a deeper understanding of the expressive power of computer languages. In this paper, we re-introduce the Random Access Stored Program ma-chine (RASP) and build an analogue of the BBG for these machines. Though the BBG for any fixed precision RASP model is trivially com-putable, the expressivity of the model renders exhaustive search infeasi-ble as we increase the size of our machine. Thus, we explore the space of BBG RASP machines using both brute force and genetic search methods