# Copyright (c) 2009 Tim Freeman # # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included in # all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN # THE SOFTWARE. # # (This is the standard MIT License, copied from # http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.) #desc Rudimentary assembler for Turing machines. import bits from constants import left, right, end, done, truncate def normalize_action(action): if type(action) == tuple or type(action) == list: return action elif action == done: return (done, left, None) else: raise Exception("Could not interpret %r as a Turing machine action" % ( action,)) # Get rid of lists in the key to an actions list. # See unit test asserts below for examples. def normalize_actions(actions): result = {} for k in actions: if type(k) == tuple: for kelem in k: result[kelem] = normalize_action(actions[k]) else: result[k] = normalize_action(actions[k]) return result assert normalize_actions({(0,1,end):done}) == \ {0:(done, left, None), 1:(done, left, None), end:(done, left, None)} assert normalize_actions({(0,1):done, end:(1, left, "foo")}) == \ {0:(done, left, None), 1:(done, left, None), end:(1, left, "foo")} # actions maps 0, 1, and end to descriptions of what to do in that # case. # state_numbers maps state names to state numbers. # compile_actions returns all the bits for the description of this state. def compile_actions(actions, state_numbers, bits_per_stateno, state): try: if actions == done: actions = {(0,1,end):done} actions = normalize_actions(actions) # action is something like [0, left, "haszero"]. # Return the bits for this action. def compile_action(action_pos): action = actions[action_pos] result = {0:0, 1:1, truncate:2, done:3}[action[0]] result = bits.setbits(result, start=2, bits={left:0, right:1}[action[1]]) next_state = action[2] if next_state is None: # None means the current state. next_state = state return bits.setbits(result, start=3, bits=state_numbers[next_state]) bits_per_action = bits_per_stateno + 3 result = compile_action(0) result = bits.setbits(result, start=bits_per_action, bits=compile_action(1)) return bits.setbits(result, start=bits_per_action*2, bits=compile_action(end)) except: print "Error when compiling state %r" % (state,) raise class Turing_abstract_syntax(object): __slots__ = ["states", "start"] def __init__(self, start, states): self.start = start self.states = states # turing_program(start_state, state1=transition1, state2=transition2, ...) # is the abstract syntax for a Turing machine program with the # start state start_state and the states state1, state2, ... # We have an odd variable name for the initial positional argument. # I used to call it "start" but then I couldn't have a state named # start because all the keyword arguments have to have different names. def turing_program(the_initial_state_is_passed_by_position, **states): return Turing_abstract_syntax(start=the_initial_state_is_passed_by_position, states=states) class Compiled_turing_program(object): __slots__=["program", "statemap"] def __init__(self, program, statemap): self.program = program self.statemap = statemap # turing_compile compiles something a human can write into a large # integer which is a Turing machine program, plus some extra # information so we can show meaningful state names when tracing the # execution of the thing. # The inputs are: # program -- The abstract syntax of the program. Make one of these by # calling turing_program. # pretty_octal -- False by default. If this is True, then force the # size of the state numbers to be a multiple of 3 bits so you can # print the program in octal and perhaps make some sense of it. # The output is a dict with keys: # "program", which is a large integer and is the Turing machine program, and # "statemap", which maps state numbers to the names they had def turing_compile(program, pretty_octal=False): assert type(program) == Turing_abstract_syntax states = program.states start = program.start state_count = len(states.keys()) # If you want to be able to read the programs in octal, add 3. # Otherwise add 1 to get smaller programs if pretty_octal: bits_per_stateno_increment = 3 else: bits_per_stateno_increment = 1 bits_per_stateno = bits_per_stateno_increment while ((1 << bits_per_stateno) < state_count): bits_per_stateno += bits_per_stateno_increment bits_per_state = 3 * (bits_per_stateno + 3) result = (1 << (bits_per_stateno-1)) - 1 state_numbers = {start:0} numbers_to_state = [start] next_state_number = 1 keys = states.keys() keys.sort() # States in alphabetical order. for state in keys: if state not in state_numbers: # Don't put the start state in again. state_numbers[state] = next_state_number numbers_to_state.append(state) next_state_number += 1 for stateno in range(len(numbers_to_state)): state_name = numbers_to_state[stateno] result = bits.setbits( result, start = bits_per_stateno + bits_per_state * stateno, bits = compile_actions(states[state_name], state_numbers, bits_per_stateno, state_name)) return Compiled_turing_program(program= result, statemap = numbers_to_state)