A Reflexive Busy Beaver Problem
Chris Salzberg
A search problem inspired by Rado’s busy beaver game for Turing machines is proposed for a system of labeled directed graph structures upon which a simple read/write rule is applied locally. In the formulation employed, explicit separation of passive (information carrying) and active (information processing) structures, imposed by mandate of rules or physics in other computational formalisms, emerges instead as a result of a structure-function dynamic that is reflexive: objects may operate directly on their own structure. In contrast to the original busy beaver problem, in which topology of the tape is fixed and only machines are varied, in the reflexive problem it is the entire space of structures that is searched: solutions are those systems that maximize the number of steps taken in computation on their own structure. Solutions are presented for finite (hence computable) systems of between four and twelve “parts”. Certain revealing results are highlighted and discussed.