import argparse import json # The Universal Turing Machine class UTM: def __init__(self, simulated_machine_description, simulated_machine_tape, simulated_machine_condition, infinity_buffer_size=2, t_buffer_size=3, implicit_quintuples=True, dangerous_quintuples=False, max_steps=float("inf"), verbosity=1, print_start_step=0): self.max_steps = max_steps self.verbosity = verbosity self.print_start_step = print_start_step self.trace = [] # Defining the UTM as presented in Minsky, Computation: Finite and infinite machines, 1967, Chapter 7. # Defining the UTMs states. self.states = [] self.states.append(None) self.states.append(State(1, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(2, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(3, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(4, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(5, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(6, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(7, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(8, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(9, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(10, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(11, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(12, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(13, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(14, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(15, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(16, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(17, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(18, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(19, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(20, "R", implicit_quintuples=implicit_quintuples)) self.states.append(State(21, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(22, "L", implicit_quintuples=implicit_quintuples)) self.states.append(State(23, "L", implicit_quintuples=implicit_quintuples)) # Defining the UTMs operations. self.states[1].define_operation('0', 'A', self.states[3], 3) self.states[1].define_operation('1', 'B', self.states[4], 3) self.states[2].define_operation('A', '0', self.states[1], 3) self.states[2].define_operation('B', '1', self.states[5], 3) self.states[2].define_operation('X', 'X', self.states[7], 2) self.states[3].define_operation('Y', 'Y', self.states[2], 3) self.states[4].define_operation('X', 'X', self.states[6], 3) self.states[4].define_operation('Y', 'Y', self.states[0], 3) self.states[5].define_operation('0', 'A', self.states[4], 3) self.states[5].define_operation('1', 'B', self.states[3], 3) self.states[6].define_operation('0', 'A', self.states[6], 3) self.states[6].define_operation('1', 'B', self.states[6], 3) self.states[6].define_operation('Y', 'Y', self.states[2], 3) self.states[7].define_operation('0', 'A', self.states[9], 3) self.states[7].define_operation('1', 'B', self.states[8], 3) self.states[8].define_operation('Y', 'Y', self.states[10], 3) self.states[9].define_operation('Y', 'Y', self.states[11], 3) self.states[10].define_operation('0', 'B', self.states[12], 3) self.states[10].define_operation('1', 'B', self.states[12], 3) self.states[10].define_operation('X', 'X', self.states[13], 2) self.states[11].define_operation('0', 'A', self.states[12], 3) self.states[11].define_operation('1', 'A', self.states[12], 3) self.states[11].define_operation('X', 'X', self.states[14], 2) self.states[12].define_operation('X', 'X', self.states[7], 3) self.states[13].define_operation('M', 'B', self.states[15], 3) self.states[14].define_operation('M', 'A', self.states[15], 3) self.states[15].define_operation('A', '0', self.states[15], 3) self.states[15].define_operation('B', '1', self.states[15], 3) self.states[15].define_operation('X', 'X', self.states[16], 3) self.states[16].define_operation('0', '0', self.states[17], 3) self.states[16].define_operation('1', '1', self.states[17], 3) self.states[17].define_operation('0', 'S', self.states[22], 2) self.states[17].define_operation('1', 'S', self.states[23], 2) self.states[17].define_operation('A', '0', self.states[17], 3) self.states[17].define_operation('B', '1', self.states[17], 3) self.states[18].define_operation('S', 'A', self.states[6], 1) self.states[19].define_operation('S', 'B', self.states[6], 1) self.states[20].define_operation('0', 'M', self.states[18], 3) self.states[20].define_operation('1', 'M', self.states[19], 3) self.states[21].define_operation('0', 'M', self.states[18], 3) self.states[21].define_operation('1', 'M', self.states[19], 3) self.states[22].define_operation('A', '0', self.states[21], 3) self.states[22].define_operation('B', '0', self.states[20], 3) self.states[23].define_operation('A', '1', self.states[21], 3) self.states[23].define_operation('B', '1', self.states[20], 3) # Explicit quintuples self.states[1].define_operation('A', 'A', self.states[1], 4) self.states[1].define_operation('B', 'B', self.states[1], 4) self.states[1].define_operation('X', 'X', self.states[1], 4) self.states[2].define_operation('0', '0', self.states[2], 4) self.states[2].define_operation('1', '1', self.states[2], 4) self.states[3].define_operation('0', '0', self.states[3], 4) self.states[3].define_operation('1', '1', self.states[3], 4) self.states[3].define_operation('A', 'A', self.states[3], 4) self.states[3].define_operation('B', 'B', self.states[3], 4) self.states[3].define_operation('X', 'X', self.states[3], 4) self.states[4].define_operation('0', '0', self.states[4], 4) self.states[4].define_operation('1', '1', self.states[4], 4) self.states[5].define_operation('A', 'A', self.states[5], 4) self.states[5].define_operation('B', 'B', self.states[5], 4) self.states[5].define_operation('X', 'X', self.states[5], 4) self.states[6].define_operation('A', 'A', self.states[6], 4) self.states[6].define_operation('B', 'B', self.states[6], 4) self.states[6].define_operation('X', 'X', self.states[6], 4) self.states[7].define_operation('A', 'A', self.states[7], 4) self.states[7].define_operation('B', 'B', self.states[7], 4) self.states[7].define_operation('X', 'X', self.states[7], 4) self.states[8].define_operation('0', '0', self.states[8], 4) self.states[8].define_operation('1', '1', self.states[8], 4) self.states[8].define_operation('A', 'A', self.states[8], 4) self.states[8].define_operation('B', 'B', self.states[8], 4) self.states[8].define_operation('X', 'X', self.states[8], 4) self.states[9].define_operation('0', '0', self.states[9], 4) self.states[9].define_operation('1', '1', self.states[9], 4) self.states[9].define_operation('A', 'A', self.states[9], 4) self.states[9].define_operation('B', 'B', self.states[9], 4) self.states[9].define_operation('X', 'X', self.states[9], 4) self.states[10].define_operation('A', 'A', self.states[10], 4) self.states[10].define_operation('B', 'B', self.states[10], 4) self.states[11].define_operation('A', 'A', self.states[11], 4) self.states[11].define_operation('B', 'B', self.states[11], 4) self.states[12].define_operation('0', '0', self.states[12], 4) self.states[12].define_operation('1', '1', self.states[12], 4) self.states[13].define_operation('0', '0', self.states[13], 4) self.states[13].define_operation('1', '1', self.states[13], 4) self.states[13].define_operation('A', 'A', self.states[13], 4) self.states[13].define_operation('B', 'B', self.states[13], 4) self.states[13].define_operation('Y', 'Y', self.states[13], 4) self.states[14].define_operation('0', '0', self.states[14], 4) self.states[14].define_operation('1', '1', self.states[14], 4) self.states[14].define_operation('A', 'A', self.states[14], 4) self.states[14].define_operation('B', 'B', self.states[14], 4) self.states[14].define_operation('Y', 'Y', self.states[14], 4) self.states[15].define_operation('0', '0', self.states[15], 4) self.states[15].define_operation('1', '1', self.states[15], 4) self.states[15].define_operation('Y', 'Y', self.states[15], 4) self.states[16].define_operation('A', 'A', self.states[16], 4) self.states[16].define_operation('B', 'B', self.states[16], 4) self.states[16].define_operation('X', 'X', self.states[16], 4) self.states[16].define_operation('Y', 'Y', self.states[16], 4) self.states[17].define_operation('X', 'X', self.states[17], 4) self.states[17].define_operation('Y', 'Y', self.states[17], 4) self.states[18].define_operation('0', '0', self.states[18], 4) self.states[18].define_operation('1', '1', self.states[18], 4) self.states[18].define_operation('Y', 'Y', self.states[18], 4) self.states[19].define_operation('0', '0', self.states[19], 4) self.states[19].define_operation('1', '1', self.states[19], 4) self.states[19].define_operation('Y', 'Y', self.states[19], 4) self.states[22].define_operation('0', '0', self.states[22], 4) self.states[22].define_operation('1', '1', self.states[22], 4) self.states[22].define_operation('Y', 'Y', self.states[22], 4) self.states[23].define_operation('0', '0', self.states[23], 4) self.states[23].define_operation('1', '1', self.states[23], 4) self.states[23].define_operation('Y', 'Y', self.states[23], 4) # Dangerous quintuples. These are accepted implicitly in Minsky's machine, but if disabled will all mitigate exploitation. if dangerous_quintuples: self.states[7].define_operation('Y', 'Y', self.states[7], 4) self.states[8].define_operation('S', 'S', self.states[8], 4) self.states[9].define_operation('S', 'S', self.states[9], 4) self.states[10].define_operation('S', 'S', self.states[10], 4) self.states[11].define_operation('S', 'S', self.states[11], 4) self.states[12].define_operation('S', 'S', self.states[12], 4) self.states[13].define_operation('S', 'S', self.states[13], 4) self.states[14].define_operation('X', 'X', self.states[14], 4) self.states[14].define_operation('S', 'S', self.states[14], 4) self.states[16].define_operation('S', 'S', self.states[16], 4) self.states[17].define_operation('S', 'S', self.states[17], 4) self.states[18].define_operation('A', 'A', self.states[18], 4) self.states[18].define_operation('B', 'B', self.states[18], 4) self.states[18].define_operation('X', 'X', self.states[18], 4) self.states[19].define_operation('A', 'A', self.states[19], 4) self.states[19].define_operation('B', 'B', self.states[19], 4) self.states[19].define_operation('X', 'X', self.states[19], 4) self.states[20].define_operation('A', 'A', self.states[20], 4) self.states[20].define_operation('B', 'B', self.states[20], 4) self.states[20].define_operation('S', 'S', self.states[20], 4) self.states[20].define_operation('X', 'X', self.states[20], 4) self.states[20].define_operation('Y', 'Y', self.states[20], 4) self.states[21].define_operation('A', 'A', self.states[21], 4) self.states[21].define_operation('S', 'S', self.states[21], 4) self.states[21].define_operation('B', 'B', self.states[21], 4) self.states[21].define_operation('X', 'X', self.states[21], 4) self.states[21].define_operation('Y', 'Y', self.states[21], 4) self.step = 0 # This is the initial state self.state = self.states[6] # The tape is composed of a buffer to represent the infinite number of zeros of the UTM, the simulated machine's tape. it's internal machine condition, and the actual program describing that simulated machine. self.tape = Tape(list("0"*infinity_buffer_size + simulated_machine_tape + "M" + "0"*t_buffer_size + "Y" + simulated_machine_condition + simulated_machine_description + "Y" + "0"*infinity_buffer_size), infinity_buffer_size + len(simulated_machine_tape) + 1 + t_buffer_size + 1 + len(simulated_machine_condition)) # Run the UTM def execute(self): self.print_all(ignore_verbosity=True) while self.step < self.max_steps: self.step += 1 symbol = self.tape.scan() self.print_before_operation() operation = self.state.get_operation(symbol) try: self.state = operation.execute(self.tape) except EndOfTapeException: if self.verbosity >= 0: print('Reached the end of the infinite tape. Increase buffer size to proceed further.') break break except HaltException: if self.verbosity >= 0: print("Found halting state. Halting.") break break self.print_after_operation() self.append_trace(operation) self.print_all(ignore_verbosity=True) json_trace = json.dumps(self.trace) with open("trace.json", "w") as outfile: outfile.write(json_trace) return self.step def print_all(self, ignore_verbosity=False): self.print_before_operation(ignore_verbosity) self.print_after_operation(ignore_verbosity) # Printing the output def print_before_operation(self, ignore_verbosity=False): if self.step >= self.print_start_step: if self.verbosity >= 0: operation = self.state.get_operation(self.tape.scan()) self.current_verbosity = operation.verbosity if self.current_verbosity <= self.verbosity or ignore_verbosity: print("State " + self.state.id_string(), end = ' ') print("reading " + self.tape.scan(), end = ' ') print("writing " + operation.print_symbol, end = ' ') if operation.target_state: if operation.target_state.direction == "R": print("shifting right", end = ' ') if operation.target_state.direction == "L": print("shifting left ", end = ' ') else: print("stopping ", end = ' ') def print_after_operation(self, ignore_verbosity=False): if self.step >= self.print_start_step: if self.verbosity >= 0: if self.current_verbosity <= self.verbosity or ignore_verbosity: print("resulting in: " + "".join(self.tape.tape), end = ' ') print("Step " + str(self.step)) print(" "*59 + " "*self.tape.head_location + "A") def append_trace(self, operation): self.trace.append({ "state" : self.state.id, "head" : self.tape.head_location, "reading" : self.tape.scan(), "writing" : operation.print_symbol, "direction" : operation.target_state.direction, "tape" : "".join(self.tape.tape), "step" : self.step }) # The tape of the UTM class Tape: def __init__(self, initial_tape, head_location): self.tape = initial_tape self.head_location = head_location def scan(self): return self.tape[self.head_location] def shift_left(self): self.head_location -= 1 if self.head_location < 0: raise EndOfTapeException() def shift_right(self): self.head_location += 1 if self.head_location >= len(self.tape): raise EndOfTapeException() def write(self, print_symbol): self.tape[self.head_location] = print_symbol class EndOfTapeException(Exception): pass class HaltException(Exception): pass # An operation of the UTM class Operation: def __init__(self, print_symbol, target_state, verbosity): self.print_symbol = print_symbol self.target_state = target_state self.verbosity = verbosity def execute(self, tape): tape.write(self.print_symbol) r = False if self.target_state: if self.target_state.direction == "R": tape.shift_right() if self.target_state.direction == "L": tape.shift_left() return self.target_state else: raise HaltException() # A state of the UTM class State: def __init__(self, id_num, direction, implicit_quintuples=True): self.id = id_num self.direction = direction self.operations = dict() self.implicit_quintuples = implicit_quintuples def id_string(self): if self.id < 10: return "0" + str(self.id) else: return str(self.id) def define_operation(self, scan_symbol, print_symbol, target_state, verbosity): self.operations[scan_symbol] = Operation(print_symbol, target_state, verbosity) def get_operation(self, scan_symbol): try: return self.operations[scan_symbol] except KeyError: if self.implicit_quintuples: # As specified on page 123 of the Minsky book, the most common quintuples, of the form (qi, sj, qi, sj, dij) are implicit. return Operation(scan_symbol, self, 4) else: # In order to make exploitation harder, we may restrict input to valid symbols. raise HaltException()