Googology Wiki
Googology Wiki

The doodle function is an uncomputable function devised by Lawrence Hollom.[1] It is a two-argument function similar to the busy beaver function.


The function revolves around a specific type of one-dimensional cellular automaton, in which state of a cell is determined by its own state and state of the cell to its right at previous generation (Hollom's original explanation is slighly different, but equivalent to this one). The function doodle(c,n) is then defined to be the longest time an automaton can go on without repeating the state, if we are constrained to automata with c states and initial seed of length at most n (with blank cells between non-blank cells counted).


By reduction of Turing machine to this type of automata, it has been shown that the doodle function is uncomputable, and in fact it eventually dominates every computable function.


Here are some known values and bounds for the doodle function:

doodle(1,n) = 1

doodle(2,n) = n

doodle(3,2) ≥ 487. Hollom checked every possible setup using a computer program and all others either looped in smaller number of steps, or haven't done so in 10,000 steps. He believes that 487 is the exact value of this function.


See also