meditationatae

Just another WordPress.com site

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:

 

rlc200k

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/

Advertisements

Written by meditationatae

March 13, 2018 at 7:09 am

Posted in History

%d bloggers like this: