main.typ

#import "turing.typ": *
#set page(height: auto, width: auto)

= Proper Subtraction
#let a = 2
#let b = 4

#let proper-subtraction = tins(
  sins(
    0,
    one: ins(1, BLANK, RIGHT),
    asterisk: ins(5, BLANK, RIGHT),
  ),
  sins(
    1,
    one: ins(1, ONE, RIGHT),
    asterisk: ins(2, ASTERISK, RIGHT),
  ),
  sins(
    2,
    blank: ins(4, BLANK, LEFT),
    one: ins(3, ASTERISK, LEFT),
    asterisk: ins(2, ASTERISK, RIGHT),
  ),
  sins(
    3,
    blank: ins(0, BLANK, RIGHT),
    one: ins(3, ONE, LEFT),
    asterisk: ins(3, ASTERISK, LEFT),
  ),
  sins(
    4,
    blank: ins(6, ONE, RIGHT),
    one: ins(4, ONE, LEFT),
    asterisk: ins(4, BLANK, LEFT),
  ),
  sins(
    5,
    blank: ins(6, BLANK, RIGHT),
    one: ins(5, BLANK, RIGHT),
    asterisk: ins(5, BLANK, RIGHT),
  ),
  sins(6),
)

#let tape = (ONE,) * a + (ASTERISK,) + (ONE,) * b + (BLANK,)

#let steps = run(proper-subtraction, tape)
#let result = steps.last().tape

$
  #a minus.dot #b = #result.filter(s => s == ONE).len().
$
Taken #steps.len() steps.

#visualize(steps)

turing.typ

#let STOP = -1

#let BLANK = 0
#let ONE = 1
#let ASTERISK = 2

#let LEFT = -1
#let RIGHT = 1

#let ins(to, write, move) = (
  to: to,
  write: write,
  move: move,
)

#let sins(state, blank: STOP, one: STOP, asterisk: STOP) = (
  str(state): (
    str(BLANK): blank,
    str(ONE): one,
    str(ASTERISK): asterisk,
  ),
)

#let tins(..sins) = sins.pos().reduce((t, s) => t + s)

#let gins(table, state, symbol) = {
  return table.at(str(state)).at(str(symbol))
}

#let machine(tape: (), head: 0, table: (:), state: 0, ..sink) = {
  let ins = gins(table, state, tape.at(head))
  if ins == STOP { return STOP }
  let nhead = head + ins.move
  if nhead < 0 or nhead >= tape.len() { return STOP }
  return (
    tape: tape.enumerate().map(((i, s)) => if i == head { ins.write } else { s }),
    head: nhead,
    table: table,
    state: ins.to,
    taken: ins,
  )
}

#let run(table, tape) = {
  let previous = (tape: tape, head: 0, table: table, state: 0)
  let current = (:)

  while true {
    current = machine(..previous)
    if current == STOP {
      (previous + (taken: STOP),)
      break
    }
    (previous + (taken: current.taken),)
    previous = current
  }
}

#let visualize(steps) = (
  steps
    .map(step => {
      let nstroke = .4pt
      let hstroke = 1.4pt + green.darken(25%)
      let hrstroke = (left: hstroke, right: nstroke, top: nstroke, bottom: nstroke)
      grid(
        align: center + horizon,
        columns: (3.5em,) + (2.1em,) * step.tape.len(),
        rows: 2.1em,
        stroke: (x, y) => if x == 0 { none } else if x == step.head + 1 { hstroke } else if x == step.head + 2 {
          hrstroke
        } else { nstroke },

        {
          set text(size: 0.5em)
          grid(
            columns: 2,
            align: (x, _) => if x == 0 { right } else { left },
            inset: 0.3em,
            [state:], [$q_#step.state$],
            ..(
              if step.taken == STOP { (grid.cell(colspan: 2)[stopped],) } else {
                (
                  [write:],
                  [
                    #let write = step.taken.write
                    #if write == ONE [1] else if write == ASTERISK [#sym.ast] else [blank]
                  ],
                  [move:],
                  if step.taken.move == LEFT [left] else [right],
                )
              }
            )
          )
        },
        ..step.tape.map(s => if s == ONE [#s] else if s == ASTERISK {
          place(
            // center + horizon,
            // dx: 0.05em,
            // dy: -0.2em,
            dx: 0.95em,
            dy: 0.5em,
            scale(200%)[#sym.ast],
          )
        } else []),
      )
    })
    .join()
)