Skip to content

Instantly share code, notes, and snippets.

@ibarland
Last active November 4, 2020 12:08
Show Gist options
  • Save ibarland/7732e683354339c9993fb0fe5390af90 to your computer and use it in GitHub Desktop.
Save ibarland/7732e683354339c9993fb0fe5390af90 to your computer and use it in GitHub Desktop.
A TM to duplicate a string
name: divisible by 3
source code: |-
# A TM to duplicate a string.
# (That is, compute f(w) = ww.)
#
# @author: ibarland@radford.edu
# run this at: https://turingmachine.io/?import-gist=7732e683354339c9993fb0fe5390af90
# assignment: https://www.radford.edu/itec420/2020fall-ibarland/Homeworks/hw06.html
#
input: 'abbab'
blank: '_'
start state: copyChar
table:
copyChar:
a: {write: A, R: carryA}
b: {write: B, R: carryB}
carryA:
[a,b,A,B]: R
_: {write: A, L: moveLPastCopied }
carryB:
[a,b,A,B]: R
_: {write: B, L: moveLPastCopied }
moveLPastCopied:
[A,B]: L
[a,b]: {L: moveLPastUncopied }
_: {R: fixup} # we've copied everything!
moveLPastUncopied:
[a,b]: L
[A,B]: {R: copyChar }
fixup:
A: {write: a, R}
B: {write: b, R}
_: {L: returnHome}
returnHome:
[a,b]: L
_: {R: halt}
halt:
positions:
copyChar: {x: 219.53, y: 124.87}
carryA: {x: 566.33, y: 77.01}
carryB: {x: 476.55, y: 148}
moveLPastCopied: {x: 454.11, y: 297.98}
moveLPastUncopied: {x: 278.68, y: 298.78}
fixup: {x: 512.65, y: 342.47}
returnHome: {x: 563.37, y: 386.52}
halt: {x: 614.27, y: 428.81}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment