Turing Encyclopedia

#States #Symbols
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal Not universal
2 Not universal Believed to not be weakly universal (T. Neary, 2017) Weakly universal (A. Smith 2007) Universal (Y. Rogozhin 1996)
3 Not universal Unknown Universal (Y. Rogozhin 1996)
4 Not universal Unknown Universal (Y. Rogozhin 1996)
5 Not universal Unknown Universal (Y. Rogozhin 1996)
6 Not universal Weakly universal (T. Neary, D. Woods 2007)
7 Not universal Universal (Y. Rogozhin 1996)
8 Not universal
9 Not universal
10 Not universal Universal (Y. Rogozhin 1996)
11 Not universal
12 Not universal
13 Not universal
14 Not universal
15 Not universal
16 Not universal
17 Not universal
18 Not universal
19 Not universal
20 Not universal
21 Not universal
22 Not universal
23 Not universal
24 Not universal Universal (Y. Rogozhin 1996)

"Weakly universal" means the tape needs to be prefilled with a pattern (finite or infinite, repeating or non repeating) and the machine doesn't need to halt.

References