Googology Wiki

Beklemishev's worms

10,505pages on
this wiki
Add New Page
Talk5 Share

Beklemishev's worms are a construction described by Lev D. Beklemishev (Russian: Беклемишев Лев Дмитриевич[1][2]) that result in a one-player game that takes a long time to terminate.[3] It is very similar to Kirby-Paris hydras.

Description Edit

A worm is simply a list of nonnegative integers \([W_0, W_1, \ldots, W_n]\). In a game Beklemishev calls "the Worm battle," our hero Cedric is presented with an arbitrary worm \(W\), and his task is to reduce it to an empty list. On turn \(m\) of the game, the worm is altered by the function \(\text{next}(W, m)\):

  • If \(W_n = 0\), then \(\text{next}(W, m) = [W_0, W_1, \ldots, W_{n-1}]\). (That is, Cedric chops off the worm's head.)
  • Otherwise, define \(k = \max_{i < n} W_i < W_n\). We define the good part of the sequence to be \(g = [W_0, \ldots, W_k]\) and the bad part to be \(b = [W_{k+1}, \ldots, W_{n-1}, W_n - 1]\). (Note that \(W_n\) is decremented by 1.) If \(k\) is nonexistent, define \(g\) to be an empty list and \(b = [W_0, \ldots, W_{n-1}, W_n - 1]\). We then define \(\text{next}(W, m) = g + b + b + \cdots + b + b\) with \(m+1\) copies of \(b\). (Here + means sequence concatenation, so for example [0, 3, 2] + [1, 4, 5] = [0, 3, 2, 1, 4, 5].)

Beklemishev proved, in a theorem he calls the Worm principle, that Cedric can always defeat the worm regardless of the initial value of \(W\). He further showed that this fact is unprovable in Peano arithmetic.

From this, we can create a specific fast-growing function. Define \(\text{Worm}(n)\) to be the number of steps required to defeat a worm starting with \(W = [n]\). Then \(\text{Worm}(n)\) is a function that dominates all functions provably recursive in Peano arithmetic, giving the function a growth rate comparable to \(f_{\varepsilon_0}(n)\).

Examples Edit

  • Start: [1]
  • Step 1: [0,0]
  • Step 2: [0]
  • Step 3: []

So \(\text{Worm}(1) = 3\).

  • Start: [2]
  • Step 1: [1,1]
  • Step 2: [1,0,1,0,1,0]
  • Step 3: [1,0,1,0,1]
  • Step 4: [1,0,1,0,0,0,0,0,0]
  • Step 10: [1,0,1]
  • Step 11: [1,013]
  • Step 24: [1]
  • Step 25: [026]
  • Step 51: []

So \(\text{Worm}(2) = 51\).

Sources Edit

  1. [1]
  2. [2]
  3. “The Worm principle”, Logic Colloquium '02 (Münster, 2002)

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.