Skip to content

Instantly share code, notes, and snippets.

@sborquez
Last active May 18, 2020 01:05
Show Gist options
  • Save sborquez/3fa8212f4efb24ed41bd4e28eede7d64 to your computer and use it in GitHub Desktop.
Save sborquez/3fa8212f4efb24ed41bd4e28eede7d64 to your computer and use it in GitHub Desktop.
standard Turing Machine that calculates the function m^n, where m, n ≥ 1 are received coded in unary, in format m#n
name: power
source code: |-
input: '11#111'
blank: ' '
start state: setup_a
table:
setup_a:
1 : {write: 'x', L}
' ' : {write: '=', L: setup_b}
setup_b:
' ' : {write: 1, R: start}
start:
[1, '#', '=', 'x']: R
' ' : {L: exponent}
exponent:
1 : {write: ' ', L: exp_to_base}
'#' : {write: ' ', L: clean}
exp_to_base:
[1, '#', 'x'] : L
'=' : {R: read_base}
read_base:
['x', 0] : R
1 : {write: 0, L: base_to_result}
'#' : {L: reset_base}
base_to_result:
['x', 0, '=', 1] : L
' ' : {R: read_factor}
result_to_base:
['x', 0, 1] : R
'=' : {R: read_base}
read_factor:
1 : {write: 0, L: copy_digit}
[0, 'x'] : R
'=' : {L: reset_factor}
reset_factor:
0 : {write: 1, L}
x : {R: result_to_base}
reset_base:
0 : {write: 1, L}
x : L
'=' : {L: reset_result}
reset_result:
1 : L
x : {write: 1, L}
' ' : {R: start}
copy_digit:
' ' : {write: 'x', R: read_factor}
['x', 0] : L
clean:
[1, 0, 'x'] : {write: ' ', L}
'=' : {write: ' ', L: done}
done:
positions:
setup_a: {x: 69.59, y: 439.32}
setup_b: {x: 68.76, y: 67.65}
start: {x: 192.25, y: 66.74}
exponent: {x: 344.99, y: 69.12}
exp_to_base: {x: 341.6, y: 178.85}
read_base: {x: 337.61, y: 311.12}
base_to_result: {x: 466, y: 310.11}
result_to_base: {x: 337.52, y: 446.78}
read_factor: {x: 595.09, y: 311.71}
reset_factor: {x: 594.73, y: 452.21}
reset_base: {x: 189.56, y: 311.69}
reset_result: {x: 190.55, y: 178.01}
copy_digit: {x: 718.89, y: 350.47}
clean: {x: 556.77, y: 64.1}
done: {x: 722.38, y: 64.25}
editor contents: |-
input: '11#111'
blank: ' '
start state: setup_a
table:
setup_a:
1 : {write: 'x', L}
' ' : {write: '=', L: setup_b}
setup_b:
' ' : {write: 1, R: start}
start:
[1, '#', '=', 'x']: R
' ' : {L: exponent}
exponent:
1 : {write: ' ', L: exp_to_base}
'#' : {write: ' ', L: clean}
exp_to_base:
[1, '#', 'x']: L
'=' : {R: read_base}
read_base:
['x', 0] : R
1 : {write: 0, L: base_to_result}
'#' : {L: reset_base}
base_to_result:
['x', 0, '=', 1] : L
' ' : {R: read_factor}
result_to_base:
['x', 0, 1] : R
'=' : {R: read_base}
read_factor:
1 : {write: 0, L: copy_digit}
[0, 'x'] : R
'=' : {L: reset_factor}
reset_factor:
0 : {write: 1, L}
x : {R: result_to_base}
reset_base:
0 : {write: 1, L}
x : L
'=' : {L: reset_result}
reset_result:
1 : L
x : {write: 1, L}
' ' : {R: start}
copy_digit:
' ' : {write: 'x', R: read_factor}
['x', 0] : L
clean:
[1, 0, 'x'] : {write: ' ', L}
'=' : {write: ' ', L: done}
done:
@sborquez
Copy link
Author

turingmachine.io/?import-gist=3fa8212f4efb24ed41bd4e28eede7d64

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