Skip to content

Instantly share code, notes, and snippets.

@sborquez
Last active May 26, 2020 18:57
Show Gist options
  • Save sborquez/5e20a39ad1edc4f8452191398e39e2f7 to your computer and use it in GitHub Desktop.
Save sborquez/5e20a39ad1edc4f8452191398e39e2f7 to your computer and use it in GitHub Desktop.
standard Turing Machine that decide the language of graph, with the format nodes#src1#dst1#src2#dst2.... in unary.
name: graph
source code: |-
#input: '111#1#11#11#11#1#111#111#11'
#input: '1#11'
input: '11#11#1'
#input: '11###1'
#input: '111'
blank: ' '
start state: check_zero_nodes
table:
check_zero_nodes:
1 : {R: nodes}
'#' : {L: reject}
nodes:
1 : R
'#' : {write: "v", L: count_block}
" " : {L: reject}
count_block:
[1, x, v, "#"]: L
0 : {write: 1, L}
" " : {write: I, R: right}
"I" : {write: P, R: right}
"P" : {write: I, R: right}
right:
[1, x, v, "#"] : R
' ' : {L: not_empty}
y : {L: even}
not_empty:
1 : {R: not_empty}
" " : {L: find_1}
["#", x]: {L: reject}
v : {R: accept}
find_1:
1 : {write: " ", L: left}
"#" : {write: " ", L: count_block}
x : {write: y, L: count_block}
left:
[1, "#"]: L
v : {write: x, L: match}
x : {L: match}
match:
0 : L
1 : {write: 0, R: next}
[P, I] : {L: reject}
next:
[1, x, "#", 0] : R
" " : {L: find_1}
even:
[1, 0, "#", x] : L
I : {R: accept}
P : {R: reject}
accept:
reject:
positions:
check_zero_nodes: {x: 577.2, y: 47.85}
nodes: {x: 713.26, y: 180.52}
count_block: {x: 715.86, y: 448.96}
right: {x: 575.68, y: 444.3}
not_empty: {x: 385.58, y: 438.01}
find_1: {x: 122.96, y: 285.94}
left: {x: 291.12, y: 289.63}
match: {x: 291.94, y: 101.34}
next: {x: 120.31, y: 98.9}
even: {x: 576.1, y: 311.57}
accept: {x: 381.95, y: 192.45}
reject: {x: 579.36, y: 183.08}
@sborquez
Copy link
Author

turingmachine.io/?import-gist=5e20a39ad1edc4f8452191398e39e2f7

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment