/machines/1RB0RA_1LC0LD_1LE1LD_0LB0RE_1RF0LA_---0RA/validate_rules.py · raw
 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
#!/usr/bin/env python3
"""Observe-stage rule validation for 1RB0RA_1LC0LD_1LE1LD_0LB0RE_1RF0LA_---0RA.
Each rule is simulated from concrete configurations (random small/large parameters, random
left/right contexts) and compared cell-for-cell (state, head, trimmed tape) with the predicted
configuration. Exact step counts where given; OP/OQ: target = the next left-edge E record.
Writes validation.json next to this file.  Run: python3 -B validate_rules.py"""
import sys, random, json, os
sys.path.insert(0, "[local working file]")
import sim
TM = '1RB0RA_1LC0LD_1LE1LD_0LB0RE_1RF0LA_---0RA'
M = sim.parse(TM)
random.seed(20261010)

def key(c):
    t = c.trimmed(); return (t.tape, t.head, t.state)

def word(maxlen=8):
    return ' '.join(random.choice('01') for _ in range(random.randint(0, maxlen)))

def ctx():
    return '0^inf 1 ' + word(), word() + ' 1 0^inf'

def nval(i, lo, hi):
    if i < 6: return lo + i % 3              # small, incl. the minimum
    if i < 20: return random.randint(lo, lo + 30)
    return random.randint(lo, hi)            # large

def exact(frm, to, steps, n, ranges, use_r=True):
    ok = 0
    for i in range(n):
        v = {k: nval(i, lo, hi) for k, (lo, hi) in ranges.items()}
        l, r = ctx()
        if not use_r: r = '0^inf'
        a = sim.Config.parse(frm.format(l=l, r=r), **v)
        b = sim.Config.parse(to.format(l=l, r=r), **v)
        s = sim.Simulator(M, a); s.run(eval(steps, {}, v))
        if not s.halted and key(s.snapshot()) == key(b): ok += 1
    return {"instances": n, "passed": ok}

def next_Erec(cfg, cap):
    for ev in sim.events(M, cfg, max_steps=cap, on_record=True, on_halt=True, snapshot=True):
        if 'halt' in ev.kinds: return None
        if ev.side == 'L' and ev.state == 'E': return ev.config
    return None

def X(gaps): return ' '.join('(110)^%d 111110' % g for g in gaps)
def P(g, G, Mm): return '0^inf <E 110 111110 %s (110)^%d 00 (110)^%d 0^inf' % (X(g), G, Mm)
def Q(g, G, Mm): return '0^inf <E 110 11110 111110 %s (110)^%d 00 (110)^%d 0^inf' % (X(g), G, Mm)

def overflow(which, n):
    ok = 0
    for i in range(n):
        nd = i % 4 if i < 8 else random.choice([0, 1, 1, 2, 2, 3, 4, 5])
        gaps = [random.choice([1, 1, 2, 3, 4, 7, 10, 17]) if random.random() < 0.7 else random.randint(1, 60)
                for _ in range(nd)]
        f = 1 + nd
        G = random.choice([0, 1, 2]) if i % 5 == 0 else random.randint(0, 400)
        Mm = random.choice([0, 1]) if i % 7 == 0 else random.randint(0, 400)
        if which == 'OP': a, b = P(gaps, G + 2**f, Mm), Q(gaps, G, Mm + 2**f)
        else:             a, b = Q(gaps, G + 2**(f+2), Mm), P([1] + gaps, G, Mm + 2**(f+2))
        c = next_Erec(sim.Config.parse(a), 10**9)
        if c is not None and key(c) == key(sim.Config.parse(b)): ok += 1
    return {"instances": n, "passed": ok}

res = {}
res['R1'] = exact('{l} A> (011)^n {r}', '{l} (010)^n A> {r}', '5*n', 60, {'n': (0, 3000)})
res['R2'] = exact('{l} (010)^n <B {r}', '{l} <B (011)^n {r}', '3*n', 60, {'n': (0, 3000)})
res['R3'] = exact('{l} A> 011 00 011 {r}', '{l} <B 00 011 011 {r}', '11', 60, {})
res['R4'] = exact('{l} 010 A> 0^inf', '{l} <B 00 011 0^inf', '6', 60, {}, use_r=False)
res['L0'] = exact('{l} 0 <E 11 (011)^(a+1) 00 (011)^b 0^inf', '{l} 1 <E 11 (011)^a 00 (011)^(b+1) 0^inf',
                  '8*a+16', 60, {'a': (0, 2000), 'b': (0, 2000)}, use_r=False)
res['OP'] = overflow('OP', 120)
res['OQ'] = overflow('OQ', 120)
json.dump(res, open(os.path.join(os.path.dirname(os.path.abspath(__file__)), 'validation.json'), 'w'), indent=1)
print(json.dumps(res))