Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment