Wiki Googologie
Advertisement
Wiki Googologie

Les vers de Beklemishev sont une construction décrite par Lev D. Beklemishev (Russe: Беклемишев Лев Дмитриевич[1][2]) qui résulte en un jeu à un joueur qui prend beaucoup de temps pour se terminer.[3]

Elle est étroitement liée à l'hydre de Kirby-Paris.

Description

A worm is simply a list of nonnegative integers [W0, W1, ..., Wn]. 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 next(W, m):

  • If Wn = 0, then next(W, m) = [W0, W1, ..., Wn-1]. (That is, Cedric chops off the worm's head.)
  • Otherwise, define k = maxi < n Wi < Wn. We define the good part of the sequence to be g = [W0, ..., Wk] and the bad part to be b = [Wk+1, ..., Wn-1, Wn - 1]. (Note that Wnis decremented by 1. If k is nonexistent, define g to be an empty list and b = [W0, ..., Wn-1, Wn - 1]. We then define next(W, m) = g + b + b + ... + 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.

The Worm's expansion rule is almost identical to the séquence primitif's expansion system.

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

Examples

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

So 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 Worm(2) = 51.

Références

  1. Беклемишев Лев Дмитриевич
  2. Беклемишев Лев Дмитриевич, mathnet
  3. Beklemishev, L. (2006). The Worm principle. In Z. Chatzidakis, P. Koepke, & W. Pohlers (Eds.), Logic Colloquium '02 (Lecture Notes in Logic, pp. 75-95). Cambridge: Cambridge University Press. doi:10.1017/9781316755723.005
Advertisement