# Beklemishev's worms

*10,505*pages on

this wiki

**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,0
^{13}] - Step 24: [1]
- Step 25: [0
^{26}] - Step 51: []

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

## Sources Edit

## See also Edit

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence**Hydras:** Kirby-Paris · **Beklemishev's worms** · Buchholz**Miscellaneous:** Factorial · Folkman's number · Exploding Tree Function · Graham's number · fusible number · Goodstein function · Laver table