Last active
May 18, 2020 01:04
-
-
Save sborquez/3d3cfb09b1809f234145a79cd8fde94d to your computer and use it in GitHub Desktop.
This is a Turing Machine that lists L_B in canonical order. Where L_B is the set formed by all natural numbers whose representation in binary is a palindrome.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
name: binary palindrome enumerator | |
source code: | | |
# Adds 1 to a binary number. | |
input: '' | |
blank: ' ' | |
start state: setup_a | |
table: | |
# binary generator | |
setup_a: | |
' ' : {write: '#', L: setup_b} | |
setup_b: | |
' ' : {write: 0, R: setup_b} | |
'#' : {L: check} | |
right: | |
[1,0] : R | |
'#' : {L: add1} | |
add1: | |
1 : {write: 0, L} | |
[0,' '] : {write: 1, L: left} | |
left: | |
[0, 1] : L | |
' ' : {R: check} | |
# Palindromo checker | |
check: | |
0 : {write: 'x', R: find_0} | |
1 : {write: 'y', R: find_1} | |
[x,y] : {L: copy_back} | |
find_0: | |
[0, 1] : R | |
['#', x, y]: {L: found_0} | |
find_1: | |
[0, 1] : R | |
['#', x, y]: {L: found_1} | |
found_0: | |
0 : {write: 'x', L: next} | |
1 : {L: no_copy_back} | |
'x' : {L: copy_back} | |
found_1: | |
1 : {write: 'y', L: next} | |
0 : {L: no_copy_back} | |
'y' : {L: copy_back} | |
next: | |
[0, 1] : L | |
[x, y] : {R: check} | |
# Enumerator | |
copy: | |
x : {write: 0, R: copy_0} | |
y : {write: 1, R: copy_1} | |
'#' : {L: end_word} | |
[0, 1] : R | |
copy_0: | |
[x, y, 0, 1, '#', '|']: R | |
' ' : {write: 0, L: copy_back} | |
copy_1: | |
[x, y, 0, 1, '#', '|']: R | |
' ' : {write: 1, L: copy_back} | |
copy_back: | |
[x, y, 0, 1, '#', '|']: L | |
' ' : {R: copy} | |
end_word: | |
[x, y, 0, 1, '|', '#']: R | |
' ' : {write: '|', L: continue} | |
no_copy: | |
x : {write: 0, R: no_copy} | |
y : {write: 1, R: no_copy} | |
[0, 1] : R | |
'#' : {L: continue} | |
no_copy_back: | |
[x, y, 0, 1]: L | |
' ' : {R: no_copy} | |
# next binary number | |
continue: | |
[0, 1, '|']: L | |
' ' : {R: right} | |
'#' : {L: right} | |
positions: | |
setup_a: {x: 40.25, y: 144.67} | |
setup_b: {x: 121.72, y: 76.12} | |
right: {x: 726.44, y: 322.03} | |
add1: {x: 729.83, y: 195.09} | |
left: {x: 731.96, y: 78.32} | |
check: {x: 340.13, y: 32.22} | |
find_0: {x: 445.03, y: 120.15} | |
find_1: {x: 216.49, y: 114.7} | |
found_0: {x: 512.01, y: 189.19} | |
found_1: {x: 101.79, y: 191.7} | |
next: {x: 346.72, y: 186.65} | |
copy: {x: 318.38, y: 452.3} | |
copy_0: {x: 99.08, y: 455.62} | |
copy_1: {x: 324.66, y: 340.32} | |
copy_back: {x: 101.93, y: 340.91} | |
end_word: {x: 490.01, y: 451.19} | |
no_copy: {x: 607.59, y: 381.76} | |
no_copy_back: {x: 506.58, y: 331.39} | |
continue: {x: 725.53, y: 452.15} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
turingmachine.io/?import-gist=3d3cfb09b1809f234145a79cd8fde94d