FANDOM


These are all designed using the rule table syntax defined here.

If the above link doesn't load, this java implementation also works (if you manually remove any comments first.)

Binary Complement (Bitwise NOT)

1 state - 3 color

O(n) time with respect to bit length

0 0 1 r *
0 1 0 r *
0 _ _ * halt

Infinite Binary Counter

2 state - 3 color

Non-halting, time required to count to n is on O(n)

0 _ 1 r 1
0 0 1 r 1
0 1 0 l 0
1 _ _ l 0
1 * * r 1

Count ON Bits, Modulo 2

2 state - 3 color

O(n) time with respect to bit length

0 0 _ r 0
0 1 _ r 1
0 _ 0 * halt
1 0 _ r 1
1 1 _ r 0
1 _ 1 * halt

Polyadic AND

2 state - 3 color

O(n) time with respect to bit length

0 1 _ r 0
0 0 0 r 1
0 _ 1 * halt
1 0 _ r 1
1 1 _ r 1
1 _ _ * halt

Polyadic OR

2 state - 3 color

O(n) time with respect to bit length

0 0 _ r 0
0 1 1 r 1
0 _ 0 * halt
1 0 _ r 1
1 1 _ r 1
1 _ _ * halt

Polyadic XOR

(This is the "exactly 1 on bit" version. For the "any odd number of on bits" version, see this machine.)

3 state - 3 color

O(n) time with respect to bit length

0 0 _ r 0
0 1 _ r 1
0 _ 0 * halt
1 0 _ r 1
1 1 0 r 2
1 _ 1 * halt
2 0 _ r 2
2 1 _ r 2
2 _ _ * halt

Equality of Equal-Length Binary Strings

8 state - 4 color

O(n2) time (with respect to bit length)

On input tape, the strings to be tested should be separated by a single equals sign. Outputs 1 if the two strings are identical, 0 otherwise.

0 0 _ r A
0 1 _ r B
0 = 1 r H

A 1 1 r A
A 0 0 r A
A = = r SA

B 1 1 r B
B 0 0 r B
B = = r SB

SA 0 = l S
SA 1 = l F
SA = = r SA

SB 1 = l S
SB 0 = l F
SB = = r SB

S _ _ r 0
S * * l S

F _ 0 r H
F * * l F

H _ _ * halt
H * _ r H

Thue-Morse Sequence

10 state - 5 color (a and b are used as working symbols to keep track of where in the current cycle it is, and are working representations of 0 and 1 respectively)

Non-halting, produces n bits in O(n2) time, completes n cycles (having produced 2n bits) in O(4n) time

0 * a r 1
1 a 0 r s1
1 b 1 r s0
1 * * l *
s0 _ 0 l sc1
s1 _ 1 l sc1
sc1 _ * r e2
sc1 a * l sc3
sc1 b * l sc3
sc1 * * l *
sc3 a * l *
sc3 b * l *
sc3 * * r sc2
sc2 a 0 r s1
sc2 b 1 r s0
sc2 _ * l e1    
e1 _ * r e2
e1 * * l *
e2 0 a r *
e2 1 b r *
e2 _ * l ret
ret * * l *
ret _ _ r 1
* * * r *

"Unary" to decimal converter

6 state - 11 color

O(n2) time

0 _ _ * halt
0 1 1 r 1
1 _ _ l 2
1 1 1 r 1
2 1 _ l 3
3 _ _ l 4
3 1 1 l 3
4 _ 1 r 5
4 0 1 r 5
4 1 2 r 5
4 2 3 r 5
4 3 4 r 5
4 4 5 r 5
4 5 6 r 5
4 6 7 r 5
4 7 8 r 5
4 8 9 r 5
4 9 0 l 4
5 _ _ r 0
5 0 0 r 5
5 1 1 r 5

Convert a positive decimal integer to Skew Binary

9 state - 11 color

O(n log n) time

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

Calculate \(\lfloor log_{2} \, n \rfloor\)

n is a base-10 positive integer given as input, fails to halt for n=1 for some reason

15 state - 11 color

O(n log n) time

0 _ * l A
0 * * r *

;Right column counts down in base 10
A 1 0 l B
A 2 1 l B
A 3 2 l B
A 4 3 l B
A 5 4 l B
A 6 5 l B
A 7 6 l B
A 8 7 l B
A 9 8 l B
A 0 9 l *
A _ * r Z

B _ * l C
B * * l *

C _ 1 r E
C * * * D

;Left column counts up in base 2
D 0 1 r E
D 1 0 l *
D _ 0 * *

E _ * r 0
E * * r *

;Cleanup
Z _ * * AA
Z * _ r *

;Count the bits, less 1
AA _ * l * 
AA * _ l BB

BB _ * l CC
BB * * l BB

CC _ 0 r DD
CC * * * EE

DD _ * r FF

;Count up in base 10
EE 0 1 * GG
EE 1 2 * GG
EE 2 3 * GG
EE 3 4 * GG
EE 4 5 * GG
EE 5 6 * GG
EE 6 7 * GG
EE 7 8 * GG
EE 8 9 * GG
EE 9 0 l *
EE _ 1 * GG

FF _ * l AA
FF * * r *

GG _ * r HH
GG * * r *

HH _ * * halt
HH * * * FF

Sort a string of base-10 digits

20 state - 11 color

O(n) time best-case, O(n2) for both average-case and worst-case

Implements a variant of the Gnome Sort

0 0 0 r 0
0 _ _ r E
* _ _ * halt
* 1 1 r C1
* 2 2 r C2
* 3 3 r C3
* 4 4 r C4
* 5 5 r C5
* 6 6 r C6
* 7 7 r C7
* 8 8 r C8
* 9 9 r C9
C1 0 1 l R0
C2 0 2 l R0
C2 1 2 l R1
C3 0 3 l R0
C3 1 3 l R1
C3 2 3 l R2
C4 0 4 l R0
C4 1 4 l R1
C4 2 4 l R2
C4 3 4 l R3
C5 0 5 l R0
C5 1 5 l R1
C5 2 5 l R2
C5 3 5 l R3
C5 4 5 l R4
C6 0 6 l R0
C6 1 6 l R1
C6 2 6 l R2
C6 3 6 l R3
C6 4 6 l R4
C6 5 6 l R5
C7 0 7 l R0
C7 1 7 l R1
C7 2 7 l R2
C7 3 7 l R3
C7 4 7 l R4
C7 5 7 l R5
C7 6 7 l R6
C8 0 8 l R0
C8 1 8 l R1
C8 2 8 l R2
C8 3 8 l R3
C8 4 8 l R4
C8 5 8 l R5
C8 6 8 l R6
C8 7 8 l R7
C9 0 9 l R0
C9 1 9 l R1
C9 2 9 l R2
C9 3 9 l R3
C9 4 9 l R4
C9 5 9 l R5
C9 6 9 l R6
C9 7 9 l R7
C9 8 9 l R8
R0 * 0 l 0
R1 * 1 l 0
R2 * 2 l 0
R3 * 3 l 0
R4 * 4 l 0
R5 * 5 l 0
R6 * 6 l 0
R7 * 7 l 0
R8 * 8 l 0
E 0 0 * 0
E 1 1 * 0
E _ _ * halt

Two's Complement Signed Integer Decoder

12 state - 12 color

O(n log n) time

0 0 _ r A
0 1 - r N

A _ _ l B
A * * r A

N 1 0 r N
N 0 1 r N
N _ _ l B

B 0 1 l B
B 1 0 l C
B - _ r Z1
B _ _ r Z2

C _ _ l D
C * * l C

D _ 1 r E
D 0 1 r E
D 1 2 r E
D 2 3 r E
D 3 4 r E
D 4 5 r E
D 5 6 r E
D 6 7 r E
D 7 8 r E
D 8 9 r E
D 9 0 l D

E * * r E
E _ _ r A

Z1 _ _ l ZN1
Z1 * _ r Z1

Z2 _ _ * halt
Z2 * _ r Z2

ZN1 _ _ l ZN1
ZN1 * * * ZN2

ZN2 _ 1 l ZN3
ZN2 0 1 l ZN3
ZN2 1 2 l ZN3
ZN2 2 3 l ZN3
ZN2 3 4 l ZN3
ZN2 4 5 l ZN3
ZN2 5 6 l ZN3
ZN2 6 7 l ZN3
ZN2 7 8 l ZN3
ZN2 8 9 l ZN3
ZN2 9 0 l ZN2

ZN3 _ - * halt
ZN3 * * l ZN3

Addition of Base-10 Signed Integers

20 state - 13 color

O(n log n) time

;Start in state A
0 * * * A
 
;State A- find right end of left block, detect sign
A _ * l B
A - * r AAA
A * * r *
 
;State B- decrement left block, detect if calculations are complete
B 0 9 l *
B 9 8 r C
B 8 7 r C
B 7 6 r C
B 6 5 r C
B 5 4 r C
B 4 3 r C
B 3 2 r C
B 2 1 r C
B 1 0 r C
B _ * r AA
B * * * AA
 
;States C and D- find right end of right block, check sign on right block
C _ * r D
C * * r *
D _ * l E
D - * r AAAA
D * * r *
 
;State E- increment right block, shifting to the right if needed
E 0 1 l F
E 1 2 l F
E 2 3 l F
E 3 4 l F
E 4 5 l F
E 5 6 l F
E 6 7 l F
E 7 8 l F
E 8 9 l F
E 9 0 l *
E _ * r SHIFT1
E M * r SHIFT1
 
;State F- return to right end of left block
F _ * l B
F * * l *
 
;States AA and BB- calculations are finished, clean up and halt
AA _ * r BB
AA * _ r *
BB M - * halt
BB * * * halt
 
;States SHIFT1 and SHIFT0- shift right block 1 cell to the right
SHIFT1 0 1 r SHIFT0
SHIFT0 0 0 r SHIFT0
SHIFT0 _ 0 * F 
 
;State AAA- Left block is negative, increment left block towards 0 and detect if finished
AAA 0 9 l *
AAA 9 8 r BBB
AAA 8 7 r BBB
AAA 7 6 r BBB
AAA 6 5 r BBB
AAA 5 4 r BBB
AAA 4 3 r BBB
AAA 3 2 r BBB
AAA 2 1 r BBB
AAA 1 0 r BBB
AAA _ * r BB
AAA * * * BB
 
;States BBB and CCC- Find right end of right block, check sign on right block
BBB _ * r CCC
BBB * * r *
CCC _ * l DDD
CCC - * * AAAAA
CCC * * r *
 
;State DDD- Decrement right block, detect if finished
DDD 9 8 l EEE
DDD 8 7 l EEE
DDD 7 6 l EEE
DDD 6 5 l EEE
DDD 5 4 l EEE
DDD 4 3 l EEE
DDD 3 2 l EEE
DDD 2 1 l EEE
DDD 1 0 l EEE
DDD 0 9 l *
DDD _ * r FFF
 
;State EEE- Return to right end of left block
EEE _ * l *
EEE * * * AAA
 
;State FFF- Cleanup
FFF _ * * GGG
FFF * _ r *
 
;State GGG- Return to right end of left block
GGG _ * l *
GGG * * * HHH
 
;State HHH- finish calculations and halt
HHH 0 1 * halt
HHH 1 2 * halt
HHH 2 3 * halt
HHH 3 4 * halt
HHH 4 5 * halt
HHH 5 6 * halt
HHH 6 7 * halt
HHH 7 8 * halt
HHH 8 9 * halt
HHH 9 0 l *
 
;States AAAA and BBBB- Right block is negative, respond accordingly
AAAA _ * l BBBB
AAAA * * r * 
BBBB 9 8 l F
BBBB 8 7 l F
BBBB 7 6 l F
BBBB 6 5 l F
BBBB 5 4 l F
BBBB 4 3 l F
BBBB 3 2 l F
BBBB 2 1 l F
BBBB 1 0 l F
BBBB 0 9 l *
BBBB * * * FFF
 
;State AAAAA- Both blocks are negative, respond accordingly
AAAAA * M r E

ROT-13

1 state - 27 colors

O(n) time with respect to length of input

0 A N r 0
0 B O r 0
0 C P r 0
0 D Q r 0
0 E R r 0
0 F S r 0
0 G T r 0
0 H U r 0
0 I V r 0
0 J W r 0
0 K X r 0
0 L Y r 0
0 M Z r 0
0 N A r 0
0 O B r 0
0 P C r 0
0 Q D r 0
0 R E r 0
0 S F r 0
0 T G r 0
0 U H r 0
0 V I r 0
0 W J r 0
0 X K r 0
0 Y L r 0
0 Z M r 0
0 _ _ * halt

Deque

This is a multi-part implementation and may be seen here.

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.