FANDOM


These are the functions for my 22-color encoding of a Deque of base-10 integers on a TM (I could cut it down to 12, but that would make it to easy to see the contents of the deque)

Push (4 states)

Input: The base-10 integer to push, followed by the encoding of the rest of the initial deque

Output: The encoding of the final deque

O(log n) time with respect to the element pushed

0 _ _ * halt-reject
0 * * * 1
1 0 A r 1
1 1 B r 1
1 2 C r 1
1 3 D r 1
1 4 E r 1
1 5 F r 1
1 6 G r 1
1 7 H r 1
1 8 I r 1
1 9 J r 1
1 _ ' r 2
1 * * * halt-reject
2 _ _ l 3
2 * * r 2
3 ' _ * halt
3 * * r halt

Pop (3 states)

Input: The encoding of the initial deque

Output: The base-10 integer popped, followed by the encoding of the final deque

O(log n) time with respect to the element popped

0 _ _ * halt-null
0 * * r 1
1 ' _ l 2
1 _ _ l 2
1 * * r 1
2 A 0 l 2
2 B 1 l 2
2 C 2 l 2
2 D 3 l 2
2 E 4 l 2
2 F 5 l 2
2 G 6 l 2
2 H 7 l 2
2 I 8 l 2
2 J 9 l 2
2 _ _ * halt
2 * * * halt-reject

Dequeue (27 [?] states)

Requires one extra working color

Most of the states are used getting the output in the right order

Input: The encoding of the initial deque

Output: The base-10 integer dequeued, followed by the encoding of the final deque

O(m (log n)2) time, m is the number of elements, n is the average element size

0 _ _ * halt-null
0 * * r 1
1 _ _ l 2
1 * * r 1
2 ' n r 3
2 _ _ r 3
2 * * l 2
3 A 0 r 3
3 B 1 r 3
3 C 2 r 3
3 D 3 r 3
3 E 4 r 3
3 F 5 r 3
3 G 6 r 3
3 H 7 r 3
3 I 8 r 3
3 J 9 r 3
3 _ _ l 4
3 * * * halt-reject

4 0 _ l 40
40 _ _ l 40'
40' _ 0 r K
4 1 _ l 41
41 _ _ l 41'
41' _ 1 r K
4 2 _ l 42
42 _ _ l 42'
42' _ 2 r K
4 3 _ l 43
43 _ _ l 43'
43' _ 3 r K
4 4 _ l 44
44 _ _ l 44'
44' _ 4 r K
4 5 _ l 45
45 _ _ l 45'
45' _ 5 r K
4 6 _ l 46
46 _ _ l 46'
46' _ 6 r K
4 7 _ l 47
47 _ _ l 47'
47' _ 7 r K
4 8 _ l 48
48 _ _ l 48'
48' _ 8 r K
4 9 _ l 49
49 _ _ l 49'
49' _ 9 r K

4 n _ * halt

K _ _ r K'
K * * r K
K' _ _ l 4
K' * * r K

* * * l *

Optimizations on the last one are welcome.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.