Turing machines in ruby arithmetic
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
# Let's implement turing machines in ruby arithemtic | |
# we want to encode tape, state and position in a single integer and - given a turing machine - write | |
# a function that emulates the turing machine. | |
# We limit our selves to simple machines - 100 states tops, 100000 positions on the tape | |
NSTATES = 100 | |
NPOSITIONS=100000 | |
# check for zero | |
def d(x) | |
1/(x*x+1) | |
end | |
# build number holding state, position counter and tape | |
# we reserve two digits for state and five for position - the rest is tape | |
def n(state, position, tape) | |
state + position*NSTATES + tape*NPOSITIONS*NSTATES | |
end | |
# pull out parts | |
def state(nn) | |
nn % NSTATES | |
end | |
def tape(nn) | |
(nn/NSTATES)/NPOSITIONS | |
end | |
def position(nn) | |
(nn/NSTATES) % NPOSITIONS | |
end | |
#now operations on the full machine | |
# read a particular position on the tape | |
def read(nn) | |
(tape(nn) / 10**position(nn) % 10) | |
end | |
# write to a particular place on the tape | |
def write(symbol, nn) | |
n(state(nn), position(nn), tape(nn) - read(nn)*10**position(nn) + symbol*10**position(nn)) | |
end | |
# change state | |
def set_state(new_state, nn) | |
n(new_state, position(nn), tape(nn)) | |
end | |
# move left - if at 0 do nothing | |
def left(nn) | |
d(position(nn))*nn+(1-d(position(nn)))*n(state(nn), position(nn)-1, tape(nn)) | |
end | |
# move right - if at 0 do nothing | |
def right(nn) | |
d(position(nn)-NPOSITIONS-2)*nn + (1-d(position(nn)-NPOSITIONS-2))*n(state(nn), position(nn)+1, tape(nn)) | |
end | |
# return result it state == test, 0 otherwise | |
def cond(state, test, result) | |
d(state-test)*result | |
end | |
# return 1 of a == b | |
def equals(a,b) | |
d(a-b) | |
end | |
# pick a value from the hash tests based on state. | |
# If state is a key in tests, return value for that key | |
# if state not found return default | |
# This is equivalent to building the expression | |
# | |
# cond(state, key1,value1)+cond(state, key2, value2) + d(equals(state, key1)+ equals(state,key2))*default | |
# returning value1 is state is key1 | |
# but default is state is neither key1 or key2 | |
def condn(state, tests, default) | |
tests.map do |test, test_result| | |
cond(state, test, test_result) | |
end.inject(&:+) + | |
(d(tests.map do |test, test_result| | |
equals(state,test) | |
end.inject(&:+))*default) | |
end | |
# so to simulate a transition of the machine - i.e. a write, move, state_change - would be e.g. | |
# set_state(1,left(write(3,n))) | |
# so a full state does something like this | |
# - choose a transition based on the value at current position | |
# if no rule given current symbol do nothing (i.e. halt) | |
# condn(read(n), { | |
# 1 => set_state(1,left(write(3,n))), | |
# 2 => set_state(2,right(write(3,n))), | |
# }, n) | |
# so an entire machine means choosing which transition to take | |
# based on state, then on input | |
# if no rules given for current state do nothing (i.e. halt) | |
# condn(state(n), { | |
# 1 => condn(read(n), { | |
# 1 => set_state(1,left(write(3,n))), | |
# 2 => set_state(2,right(write(3,n))), | |
# }, n), | |
# 2 => condn(read(n), { | |
# 1 => set_state(1,left(write(3,n))), | |
# 2 => set_state(2,right(write(3,n))), | |
# }, n) | |
# }, n) | |
# | |
# this implements https://en.wikipedia.org/wiki/Turing_machine_examples#A_copy_subroutine | |
def copy(number) | |
condn(state(number), { | |
1 => condn(read(number), { | |
0 => set_state(0, number), | |
1 => set_state(2, right(write(0, number))) | |
}, number), | |
2 => condn(read(number), { | |
0 => set_state(3, right(write(0, number))), | |
1 => right(write(1, number)) | |
}, number), | |
3 => condn(read(number), { | |
0 => set_state(4, left(write(1, number))), | |
1 => right(write(1, number)) | |
}, number), | |
4 => condn(read(number), { | |
0 => set_state(5, left(write(0, number))), | |
1 => left(write(1, number)) | |
}, number), | |
5 => condn(read(number), { | |
0 => set_state(1, right(write(1, number))), | |
1 => left(write(1, number)) | |
}, number), | |
}, number) | |
end | |
# let's use the machine to copy the string 111 | |
# By convention we start in state 1 and position 0 | |
x = n(1,0,111) | |
while x != copy(x) do | |
p [state(x), position(x), tape(x), x] | |
x = copy(x) | |
end | |
p [state(x), position(x), tape(x), x] | |
# OK - that was fun - but we were cheating, calling functions and stuff. To bring it all home | |
# I'll now build a transformer that can take a program like copy and write it as pure arithmetic | |
#We parse the code in this file using https://github.com/whitequark/parser | |
#and emit arithmetic using https://github.com/mbj/unparser | |
require 'parser/current' | |
require 'unparser' | |
#here's the main function to walk the syntax tree | |
#we do 3 transforms | |
# 1. replace function calls with the body of the function inline | |
# 2. replace variables and constants with their values | |
# 3. the replace condn with an expression builder that builds an expression computing condn for specific arguments | |
# | |
# Throughout we use the syntax tree of functions from this file - captured in the hash names | |
# The general loop is here | |
def replace_names(node, names) | |
if node.is_a?(Parser::AST::Node) | |
Parser::AST::Node.new(node.type, | |
node.children.map do |cnode| | |
if cnode.is_a?(Parser::AST::Node) | |
if cnode.type == :send | |
if cnode.children[1] == :condn | |
replace_condn(cnode, names) | |
elsif names[cnode.children[1]] | |
replace_send(cnode, names) | |
else | |
replace_names(cnode, names) | |
end | |
elsif cnode.type == :lvar | |
replace_names(names[cnode.children[0]] || cnode,names) | |
elsif cnode.type == :const | |
replace_names(names[cnode.children[1]] || cnode,names) | |
else | |
replace_names(cnode,names) | |
end | |
else | |
cnode | |
end | |
end | |
) | |
else | |
node | |
end | |
end | |
# this inlines function calls | |
def replace_send(send_node, names) | |
my_names = names.dup | |
def_node = names[send_node.children[1]] | |
arg_names = def_node.children[1].children | |
code = def_node.children[2] | |
replace_names(send_node,names).children[2..-1].each_with_index do |expression_node,i| | |
my_names[arg_names[i].children.first] = expression_node | |
end | |
replace_names(Parser::AST::Node.new(:begin, [code]), my_names) | |
end | |
# and here's the expression builder for condn | |
# it's the same loop over the condn input hash - but we output the syntax tree of the full computation | |
# instead of performing the computation | |
def replace_condn(send_node, names) | |
state = replace_names(send_node.children[2], names) | |
tests = replace_names(send_node.children[3], names) | |
default = replace_names(send_node.children[4], names) | |
# compute and add the test_results | |
std_node = tests.children.map do |pair| | |
replace_send(Parser::AST::Node.new(:send, [nil, :cond, state, pair.children.first, pair.children.last]),names) | |
end.inject do |a,b| | |
Parser::AST::Node.new(:send, [a, :+ ,b]) | |
end | |
#check if any test was satisfied by summing all test results | |
default_node = tests.children.map do |pair| | |
replace_send(Parser::AST::Node.new(:send, [nil, :equals, state, pair.children.first]),names) | |
end.inject do |a,b| | |
Parser::AST::Node.new(:send, [a, :+ ,b]) | |
end | |
# return 1 if no tests met | |
default_node = replace_send(Parser::AST::Node.new(:send, [nil, :d, default_node]),names) | |
# multiply by default | |
default_node = Parser::AST::Node.new(:send, [default_node, :* ,default]) | |
# add std branch and default | |
Parser::AST::Node.new(:send, [std_node, :+ ,default_node]) | |
end | |
# Now we're ready to parse this file and build a table of syntax trees for the functions defined here | |
def define_ast | |
definitions = Parser::CurrentRuby.parse(File.open(__FILE__).read) | |
names = {} | |
definitions.children.select {|n| n.type == :def || n.type == :casgn || n.type == :lvasgn}.each do |node| | |
if node.type == :def | |
names[node.children.first] = node | |
elsif node.type == :casgn | |
names[node.children[1]] = node.children[2] | |
else # node type is lvasgn | |
names[node.children[0]] = node.children[1] | |
end | |
end | |
names | |
end | |
# And finally we can generate a pure arithmetic version of the machine implemented by copy | |
ast = define_ast | |
puts Unparser.unparse(replace_names(ast[:copy], ast)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment