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

Definition Edit

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).

Properties Edit

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.

Values Edit

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 10000 steps. He believes that 487 is the exact value of this function.

Refrences Edit


See also Edit

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.