-
Notifications
You must be signed in to change notification settings - Fork 14
/
Omega
95 lines (87 loc) · 4.54 KB
/
Omega
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
Related discussions:
https://mathoverflow.net/questions/353514/whats-the-smallest-lambda-calculus-term-not-known-to-have-a-normal-form
https://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown
https://www.reddit.com/r/programming/comments/4mwkam/small_programs_with_unknown_halting_status
https://www.reddit.com/r/haskell/comments/4mwpkn/shortest_programs_with_unknown_halting_status
.000100011 < omega_lambda < .0010101
BLC prefix parsed term term applied to input_bits of form \.0 M unread_bits ?
00 00 00 \.\.\.M FAIL 2^-6
00 00 01 00 00 \.\.(\.\.M) N FAIL 2^-10
00 00 01 00 01 \.\.(\.M N) O ? 2^-10
00 00 01 00 10 0 \.\.(\.0) M ? 2^-11
00 00 01 00 10 1 \.\.(\.0) 0+ FAIL 2^-11
00 00 01 00 11 \.\.(\.1+) M FAIL 2^-10
00 00 01 01 \.\.M N ? 2^-8
00 00 01 10 \.\.0 M FAIL 2^-8
00 00 01 110 00 0 \.\.1 (\.M) ? 2^-12
00 00 01 110 00 10 \.\.1 (\.0) FAIL 2^-13
00 00 01 110 00 110 \.\.1 (\.1) FAIL 2^-14
00 00 01 110 00 111 \.\.1 (\.2+) FAIL 2^-14
00 00 01 110 01 \.\.1 (M N) ? 2^-11
00 00 01 110 10 \.\.1 0 HALT 2^-11
00 00 01 110 11 \.\.1 1+ FAIL 2^-11
00 00 01 111 \.\.2+ M FAIL 2^-9
00 00 1 \.\.0+ FAIL 2^-5
00 01 00 00 00 \.(\.\.\.M) N FAIL 2^-10
00 01 00 00 01 \.(\.\.M N) O ? 2^-10
00 01 00 00 10 \.(\.\.0) M FAIL 2^-10
00 01 00 00 11 \.(\.\.1+) M FAIL 2^-10
00 01 00 01 00 \.(\.(\.M) N) O ? 2^-10
00 01 00 01 01 \.(\.M N O) P ? 2^-10
00 01 00 01 1 \.(\.0+ M) N ? 2^-9
00 01 00 10 00 0 \.(\.0) (\.M) ? 2^-11
00 01 00 10 00 1 \.(\.0) (\.0+) FAIL 2^-11
00 01 00 10 01 \.(\.0) (M N) ? 2^-10
00 01 00 10 10 \.(\.0) 0 HALT 2^-10
00 01 00 10 11 \.(\.0) 1+ FAIL 2^-10
00 01 00 110 \.(\.1) M HALT 2^-9
00 01 00 111 \.(\.2+) M FAIL 2^-9
00 01 01 00 \.(\.M) N O ? 2^-8
? 2^-10
? 2^-11
? 2^-12
00 01 01 01 01 11 \.1+ M N O P FAIL 2^-12
00 01 01 01 10 \.0 M N O ? 2^-10
00 01 01 01 11 \.1+ M N O FAIL 2^-10
00 01 01 10 00 \.0 (\.M) N ? 2^-10
00 01 01 10 01 \.0 (M N) O ? 2^-10
00 01 01 10 10 \.0 0 M HALT 2^-10
00 01 01 10 11 \.0 1+ M FAIL 2^-10
00 01 01 11 \.1+ M N FAIL 2^-8
00 01 10 00 00 10 \.0 (\.\.0) HALT 2^-12
00 01 10 00 00 110 \.0 (\.\.1) FAIL 2^-13
00 01 10 00 1 \.0 (\.0+) FAIL 2^-9
00 01 10 01 10 10 \.0 (0 0) FAIL 2^-12
00 01 10 01 10 11 \.0 (0 1+) FAIL 2^-12
00 01 10 01 11 \.0 (1+ M) FAIL 2^-10
00 01 10 10 \.0 0 FAIL 2^-8
00 01 10 11 \.0 1+ FAIL 2^-8
00 01 11 \.1+ M FAIL 2^-6
00 10 \.0 HALT 2^-4
00 11 \.1+ FAIL 2^-4
01 00 00 10 (\.\.0) M HALT 2^-8
01 00 00 111 (\.\.2+) M FAIL 2^-9
01 00 00 11 (\.\.1+) M FAIL 2^-8
01 00 01 10 10 1 (\.0 0) 0+ FAIL 2^-11
01 00 01 10 110 1 (\.0 1) 0+ FAIL 2^-12
01 00 01 10 1110 1 (\.0 2) 0+ FAIL 2^-13
01 00 10 00 00 10 (\.0) (\.\.0) FAIL 2^-12
01 00 10 00 00 11 (\.0) (\.\.1+) FAIL 2^-12
01 00 10 00 10 (\.0) (\.0) HALT 2^-10
01 00 10 00 11 (\.0) (\.1+) FAIL 2^-10
01 00 10 01 1 (\.0) (0+ M) FAIL 2^-9
01 00 10 1 (\.0) 0+ FAIL 2^-7
01 00 11 (\.1+) M FAIL 2^-6
01 01 00 10 1 (\.0) 0+ M FAIL 2^-9
01 01 00 11 (\.1+) M N FAIL 2^-8
01 01 01 00 10 1 (\.0) 0+ M N FAIL 2^-11
01 01 01 00 11 (\.1+) M N O FAIL 2^-10
01 01 01 01 00 10 1 (\.0) 0+ M N O FAIL 2^-13
01 01 01 01 00 11 (\.1+) M N O P FAIL 2^-12
01 01 01 01 01 01 1 0+ M N O P R S FAIL 2^-13
01 01 01 01 01 1 0+ M N O P R FAIL 2^-11
01 01 01 01 1 0+ M N O P FAIL 2^-9
01 01 01 1 0+ M N O FAIL 2^-7
01 01 1 0+ M N FAIL 2^-5
01 1 0+ M FAIL 2^-3
1 0+ FAIL 2^-1