/machines/1RB---_1LC1RE_1LD0LC_1LE1LC_1RF0RE_1RA0RB/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
"""Validate the observe-stage rules of machine #14 by direct simulation from concrete configurations.

Each rule: LHS -> RHS in exactly `steps` steps, with random context words glued on both sides
(the rule must not depend on them). Variables n, m drawn small (0..3), medium (4..40), large (100..3000),
covering every residue mod 2, 3, 4, 5. Prints JSON {name: {instances, passed}}.
"""
import json
import random
import sys

sys.path.insert(0, "[local working file]")
import sim  # noqa: E402

TM = "1RB---_1LC1RE_1LD0LC_1LE1LC_1RF0RE_1RA0RB"
M = sim.parse(TM)

# name: (lhs, rhs, steps(n, m), min n, min m, left context allowed?, right context allowed?)
RULES = {
    # sweeps
    "S_R  dark->light, B moving right": ("B> (11000)^n", "(10111)^n B>", lambda n, m: 5 * n, 0, 0, True, True),
    "S_L  light->dark, C moving left (C on 0)": ("(11110)^n <C", "<C (00011)^n", lambda n, m: 5 * n, 0, 0, True, True),
    "S_L' light->dark, C moving left (C on 1)": ("(10111)^n <C", "<C (11000)^n", lambda n, m: 5 * n, 0, 0, True, True),
    # edges
    "EdgeR right edge +4 cells": ("E> 0^inf", "1^3 <C 1 0^inf", lambda n, m: 4, 0, 0, True, False),
    "EdgeL left edge +2 cells": ("0^inf <C", "0^inf 1 0 B> 1", lambda n, m: 4, 0, 0, False, True),
    # one wall, five states: W0 -> W1 -> Lw1 -> Lw2 -> Lw3 -> W0 (moved +5 cells)
    "W0 reflects B (segment comes back dark, wall -> W1)": ("B> (11000)^n 0", "<C (11000)^n 1", lambda n, m: 10 * n + 1, 0, 0, True, True),
    "W1 lets B pass (wall -> Lw1)": ("B> (11000)^n 1 (11000)^m", "(10111)^n 1 00111 (10111)^(m-1) B>", lambda n, m: 5 * n + 5 * m + 1, 0, 1, True, True),
    "Lw1 reflects C (-> Lw2)": ("1 00111 (10111)^m <C", "000111 (10111)^m B>", lambda n, m: 10 * m + 11, 0, 0, True, True),
    "Lw2 reflects C (-> Lw3)": ("000111 (10111)^m <C", "101111 (10111)^m B>", lambda n, m: 10 * m + 11, 0, 0, True, True),
    "Lw3 lets C pass (-> W0, one block right)": ("101111 (10111)^m <C", "<C 110000 (11000)^m", lambda n, m: 5 * m + 6, 0, 0, True, True),
}


def cells(cfg, shift=0):
    ones = frozenset(cfg.lo + i + shift for i, v in enumerate(cfg.tape) if v)
    return ones, cfg.state, cfg.pos + shift


def ctx(rng):
    return "".join(rng.choice("01") for _ in range(rng.randint(1, 8))) + "1"


def values(rng, lo):
    vals = list(range(lo, lo + 4)) + [rng.randint(4, 40) for _ in range(6)] + [rng.randint(100, 3000) for _ in range(4)]
    return [v for v in vals if v >= lo]


def check(name, lhs, rhs, steps, nmin, mmin, lctx, rctx, rng):
    inst = ok = 0
    fails = []
    for n in values(rng, nmin):
        for m in values(rng, mmin)[:5]:
            for _ in range(2):
                L = ("0^inf " + ctx(rng) + " ") if lctx else ""
                R = (" " + ctx(rng)[::-1] + " 0^inf") if rctx else ""
                a = sim.Config.parse(L + lhs + R, n=n, m=m)
                b = sim.Config.parse(L + rhs + R, n=n, m=m)
                r = sim.run(M, a, steps(n, m))
                inst += 1
                # align the expected configuration on the shared left context (else on the right end)
                shift = (a.lo - b.lo) if lctx else (a.hi - b.hi)
                if not r.halted and cells(r.final) == cells(b, shift):
                    ok += 1
                elif len(fails) < 3:
                    fails.append((n, m, L, R))
    return {"instances": inst, "passed": ok, "fails": fails}


if __name__ == "__main__":
    rng = random.Random(int(sys.argv[1]) if len(sys.argv) > 1 else 14)
    out = {name: check(name, *spec, rng) for name, spec in RULES.items()}
    print(json.dumps(out, indent=1))