A Space of Solutions for the Easter Egg Problem

Adrian German

Indiana University Bloomington

Abstract

In 2004 George E. Danner (Industrial Science, LLC, and NKS Summer School 2003) proposed a benchmark search problem that he called the Easter Egg problem: a search problem for discontinuities in an otherwise continuous space. In this presentation we illustrate a solution to the Easter Egg problem: a one-head 2D Turing machine with 3 colors and 11 rewriting rules, each rule taking into account a relatively small neighborhood of the machine’s head (between 9 and 15 cells). The machine runs by extending a closed non-intersecting curve (also known as a Jordan curve), in all directions, avoiding obstacles and in the process detecting the locations of interest in the space. We will demonstrate this on any number of random initial conditions, in a space of arbitrary size. We note that when the space is infinite and empty the trajectory of the curve, which literally sweeps the space in a way that resembles a fluid flow, is following a simple spiral, as expected (see Cawley et al., comments on the NKS forum). The solution can be easily extended to a multihead Turing machine, provided we set a way of communication between the machine's heads (for example, using more colors). Once we have a solution we can abstract its features, then apply NKS and search exhaustively through their space to compare them; such a discussion will conclude our presentation. Programs to be presented are written in Mathematica and Java.