Create a gist now

Instantly share code, notes, and snippets.

@clausd /turing.rb
Last active Dec 3, 2015

Turing machines in ruby arithmetic
# 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