check_derived_control_fold.py

#!/usr/bin/env python3
"""Exact audit of the two-state derived-control prefix-parity fold."""

from itertools import product


def prefix_parities(bits):
    parity = 0
    out = []
    for bit in bits:
        parity ^= bit
        out.append(parity)
    return tuple(out)


def folded_look(old_sites, selector_reverse):
    """Use doubled coordinates; crease c=L becomes coordinate 2L."""
    length = len(old_sites)
    fibres = {}

    for offset, value in enumerate(old_sites):
        x = 2 * offset + 1
        fibres.setdefault(x, []).append(value)

    for offset, value in enumerate(selector_reverse):
        x = 2 * length + 2 * offset + 1
        reflected = 4 * length - x
        fibres.setdefault(reflected, []).append(value)

    assert len(fibres) == length
    assert all(len(stack) == 2 for stack in fibres.values())
    return int(any(all(stack) for stack in fibres.values()))


def selector_for(index, length):
    selector = [0] * length
    selector[index] = 1
    return tuple(reversed(selector))


def check_grade(length):
    rows = {}
    by_final_state = {0: set(), 1: set()}

    for bits in product((0, 1), repeat=length):
        stored = prefix_parities(bits)
        row = tuple(
            folded_look(stored, selector_for(index, length))
            for index in range(length)
        )

        assert row == stored
        assert tuple(
            row[index] ^ (row[index - 1] if index else 0)
            for index in range(length)
        ) == bits

        rows[bits] = row
        by_final_state[stored[-1]].add(stored)

    assert len(set(rows.values())) == 2**length
    expected_fibre = 1 if length == 1 else 2 ** (length - 1)
    assert all(len(histories) == expected_fibre for histories in by_final_state.values())

    return {
        "grade": length,
        "control_states": 2,
        "row_classes": len(set(rows.values())),
        "histories_per_final_state": expected_fibre,
        "old_derived_sites": length,
        "late_selector_sites": length,
        "effective_fibres": length,
        "depth": 2,
        "folds": 1,
    }


def one_state_is_impossible_at_grade_two():
    """Enumerate every one-state binary Mealy output rule."""
    target = {
        bits: prefix_parities(bits)
        for bits in product((0, 1), repeat=2)
    }
    for output_zero, output_one in product((0, 1), repeat=2):
        rule = {0: output_zero, 1: output_one}
        produced = {
            bits: tuple(rule[bit] for bit in bits)
            for bits in product((0, 1), repeat=2)
        }
        assert produced != target


def main():
    one_state_is_impossible_at_grade_two()
    print("derived-control prefix-parity fold census")
    for length in range(1, 9):
        result = check_grade(length)
        print(
            "L={grade}: q={control_states}, rows={row_classes}, "
            "histories/state={histories_per_final_state}, "
            "M_old={old_derived_sites}, M_late={late_selector_sites}, "
            "S={effective_fibres}, D={depth}, F={folds}".format(**result)
        )
    print("one-state binary Mealy encoders fail already at L=2")


if __name__ == "__main__":
    main()