A turing machine to calc monus.

monus_tm.py

from itertools import product

import pytest
from automata.tm.configuration import TMConfiguration
from automata.tm.dtm import DTM
from automata.tm.tape import TMTape

tm = DTM(
    states={f"q{i}" for i in range(7)},
    input_symbols=set("01"),
    tape_symbols=set("01B"),
    transitions={
        "q0": {
            "0": ("q1", "B", "R"),
            "1": ("q5", "B", "R"),
        },
        "q1": {
            "0": ("q1", "0", "R"),
            "1": ("q2", "1", "R"),
        },
        "q2": {
            "0": ("q3", "1", "L"),
            "1": ("q2", "1", "R"),
            "B": ("q4", "B", "L"),
        },
        "q3": {
            "0": ("q3", "0", "L"),
            "1": ("q3", "1", "L"),
            "B": ("q0", "B", "R"),
        },
        "q4": {
            "0": ("q4", "0", "L"),
            "1": ("q4", "B", "L"),
            "B": ("q6", "0", "R"),
        },
        "q5": {
            "0": ("q5", "B", "R"),
            "1": ("q5", "B", "R"),
            "B": ("q6", "B", "R"),
        },
    },
    initial_state="q0",
    blank_symbol="B",
    final_states={"q6"},
)


# noinspection SpellCheckingInspection
def monus(a: int, b: int) -> int:
    """See https://en.wikipedia.org/wiki/Monus."""
    return max(a - b, 0)


def tm_input(a: int, b: int) -> str:
    return "0" * a + "1" + "0" * b


@pytest.mark.parametrize(
    "a,b",
    product(range(16), repeat=2),
)
def test_tm(a: int, b: int):
    actual = tm.read_input(tm_input(a, b)).tape.tape.count("0")
    expected = monus(a, b)
    assert actual == expected


def format_conf(conf: TMConfiguration) -> str:
    tape: TMTape = conf.tape
    s = "".join(tape.tape)
    pos = tape.current_position

    return s[:pos] + conf.state + s[pos:]


def test_format_conf():
    assert (
        format_conf(
            TMConfiguration(
                "q",
                TMTape("01", current_position=1, blank_symbol="B"),
            )
        )
        == "0q1"
    )


if __name__ == "__main__":
    for c in tm.read_input_stepwise(tm_input(5, 3)):
        print(format_conf(c))
    print("=" * 32)
    for c in tm.read_input_stepwise(tm_input(3, 5)):
        print(format_conf(c))