← RoseCode

ROSECODE 371

De vermis mysteriis

Philippe_57721 · Programming ·

Professor Beklemishev defines a worm as follow:

We start with a list of non negative integers W1=[w0,w1,,wn] at step m=1

At step m
. If wn=0, then Wm=[w0,w1,,wn1] (We chop its head)
. Otherwise, let k=MAXi<nwi<wn

If k exists let G=[w0,,wk],B=[wk+1,,wn1]
If k does not exist let G=[] (an empty list),B=[w0,,wn1]
Then Wm=G+B++B (m+1) copies of B

Here is the evolution of the worm [1,1]
  1 - [1,1]
  2 - [1,0,1,0,1,0]
  3 - [1,0,1,0,1]
  4 - [1,0,1,0,0,0,0,0,0]
  5 - [1,0,1,0,0,0,0,0]
  6 - [1,0,1,0,0,0,0]
  7 - [1,0,1,0,0,0]
  8 - [1,0,1,0,0]
  9 - [1,0,1,0]
 10 - [1,0,1]
 11 - [1,0,0,0,0,0,0,0,0,0,0,0,0,0]
...
 24 - [1]
 25 - [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
...
 50 - [0]
 51 - []
He proved that every worm evolves eventually to an empty list.
This cannot be proved in Peano.
The number of steps to reach an empty list is not calculable.


At which step does the worm W1=[1,1,1] turns into [1,1] ? (It's a VERY VERY LARGE number)

[My timing: < 1 sec]