## Chaos TM of Marxen and Buntrock

Previously I wrote about the 5-state TM #4 (Chaotic TM) of Marxen and Buntrock from around 1990. It certainly appears to produce a rather complex integer sequence over time at the left end of the tape, upon counting runs of consecutive 1’s and 0’s on the tape.

If s_k is the k’th term, then s_1 = 3 and it seems that s_k is at most k+2.

The start of the sequence s_k was exhibited in:

https://meditationatae.wordpress.com/2017/09/06/content-of-tape-of-tm-4-chaos-machine/

There is also a graph of s_k as a function of k:

I decided to look at the subsequence where s_k = k+2, which begins: 3, 5, 7, 9, …

Here it is with the number of binary bits per number:

3 2

5 3

7 3

9 4

13 4

15 4

17 5

21 5

25 5

29 5

31 5

33 6

37 6

45 6

49 6

53 6

57 6

61 6

63 6

65 7

77 7

85 7

93 7

97 7

101 7

109 7

113 7

117 7

121 7

125 7

127 7

129 8

149 8

161 8

173 8

181 8

189 8

193 8

205 8

213 8

221 8

225 8

229 8

237 8

241 8

245 8

249 8

253 8

255 8

257 9

289 9

309 9

321 9

341 9

353 9

365 9

373 9

381 9

385 9

405 9

417 9

429 9

437 9

445 9

449 9

461 9

469 9

477 9

481 9

485 9

493 9

497 9

501 9

505 9

509 9

511 9

513 10

545 10

577 10

609 10

629 10

641 10

673 10

693 10

705 10

725 10

737 10

749 10

757 10

765 10

769 10

801 10

821 10

833 10

853 10

865 10

877 10

885 10

893 10

897 10

917 10

929 10

941 10

949 10

957 10

961 10

973 10

981 10

989 10

993 10

997 10

1005 10

1009 10

1013 10

1017 10

1021 10

1023 10

1025 11

etc.

2 bits: 1 number

3 bits: 2

4 bits: 3

5 bits: 5

6 bits: 8

7 bits: 12

8 bits: 18

9 bits: 27

10 bits: 41

27 + ceiling(27/2) = 27 + ceiling(13.5) = 27+ 14 = 41 [10 bits]

18 + ceiling(18/2) = 18 + ceiling(9) = 18+9 = 27 [ 9 bits]

This means the number of subsequence terms with k+1 bits would always be very close to 1.5 times the number of terms with k bits.

Needless to say, this is just a guess. Analyzing complex Turing Machines is rather hard.

Heiner Marxen on Busy Beavers and Turing Machines:

https://www.drb.insel.de/~heiner/BB/