turingsubtraction.yaml

name: binary increment
source code: |
  # Adds 1 to a binary number.
  input: '111101111'
  blank: '0'
  start state: right
  table:
    # scan to the rightmost digit
    right:
      0: {R: checkdone}
      1: R
    # then carry the 1
    checkdone:
      0: {R: done}
      1: {R: gotoend}
    gotoend:
      0: {L: removeEnd}
      1: R
    removeEnd:
      0: {R: done}
      1: {write: 0, L: firstEnd}
    firstEnd:
      0: {L: firstStart}
      1: L
    firstStart:
      0: {R: subtract}
      1: L
    subtract:
      0: {L: done}
      1: {write: 0, R: right}
    done:


  # Exercises:

  # • Modify the machine to always halt on the leftmost digit
  #   (regardless of the number's length).
  #   Hint: add a state between carry and done.

  # • Make a machine that adds 2 instead of 1.
  #   Hint: 2 is '10' in binary, so the last digit is unaffected.
  #   Alternative hint: chain together two copies of the machine from
  #   the first exercise (renaming the states of the second copy).

  # • Make a machine to subtract 1.
  #   To simplify things, assume the input is always greater than 0.
positions:
  right: {x: 230, y: 250}
  checkdone: {x: 389.29, y: 293.37, fixed: false}
  gotoend: {x: 424.14, y: 431.26, fixed: false}
  removeEnd: {x: 438.73, y: 283.51, fixed: false}
  firstEnd: {x: 336.48, y: 159.48, fixed: false}
  firstStart: {x: 444.09, y: 66.77, fixed: false}
  subtract: {x: 400.4, y: 207.92, fixed: false}
  done: {x: 570, y: 250}
editor contents: |-
  #Turing subtraction
  input: '111101111'
  blank: '0'
  start state: right
  table:
    right:
      0: {R: checkdone}
      1: R
    checkdone:
      0: {R: done}
      1: {R: gotoend}
    gotoend:
      0: {L: removeEnd}
      1: R
    removeEnd:
      0: {R: done}
      1: {write: 0, L: firstEnd}
    firstEnd:
      0: {L: firstStart}
      1: L
    firstStart:
      0: {R: subtract}
      1: L
    subtract:
      0: {L: done}
      1: {write: 0, R: right}
    done: