Skip to content

Instantly share code, notes, and snippets.

@sborquez
Last active May 18, 2020 01:04
Show Gist options
  • Save sborquez/3d3cfb09b1809f234145a79cd8fde94d to your computer and use it in GitHub Desktop.
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.
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}
@sborquez
Copy link
Author

turingmachine.io/?import-gist=3d3cfb09b1809f234145a79cd8fde94d

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