daily pastebin goal
26%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2.     Turing machine module
  3.    
  4.     Represented by:
  5.     - An alphabet of symbols
  6.     - A set of states
  7.     - A sequence of transitions
  8.     - A data tape
  9.     - A read/write head
  10.  
  11.     An instruction is a tuple (s0, a, b, d, s1)
  12.     such that:
  13.         s0, s1 are states (int)
  14.         a, b are symbols in the alphabet
  15.         d is either the left or right direction
  16. """
  17.  
  18. class TM:
  19.     """
  20.         Turing Machine class
  21.     """
  22.  
  23.     # Blank symbol
  24.     blank = None
  25.     # Directions
  26.     L = -1
  27.     R = +1
  28.  
  29.     def __init__(self, transitions = [], tape = [], start_state = 0, alphabet = {0,1}):
  30.         self.states = self.build_states(alphabet, transitions)
  31.         self.head = 0
  32.         self.tape = tape
  33.         self.cur_state = start_state
  34.         self._tape_root = 0
  35.         # Check if start state is valid
  36.         assert(self.states[start_state] != None)
  37.    
  38.     def current_state(self):
  39.         return self.states[self.cur_state]
  40.        
  41.     def head_index(self):
  42.         return self._tape_root + self.head
  43.    
  44.     def move(self):
  45.         s = self.current_state()
  46.        
  47.         # Read head and find matching transition
  48.         value = self.tape[self.head_index()]
  49.        
  50.         if value in s:
  51.             (b, d, next) = s[value]
  52.             self.cur_state = next
  53.             self.tape[self.head_index()] = b
  54.             self.head = self.head + d
  55.  
  56.             # Resize tape if head out of range, to simulate infinite tape
  57.             if self.head < 0:
  58.                 self.tape.insert(0, TM.blank)
  59.                 self._tape_root = self._tape_root + 1
  60.             elif self.head >= len(self.tape):
  61.                 self.tape.append(TM.blank)
  62.            
  63.             return True
  64.         else:
  65.             # Can't move
  66.             return False
  67.        
  68.     def build_states(self, alphabet, transitions):
  69.         """
  70.             Build the transition graph from a sequence of transitions
  71.         """
  72.         # State map
  73.         states = dict()
  74.        
  75.         # Alphabet set
  76.         t = set(alphabet)
  77.         t.add(TM.blank)
  78.        
  79.         for (s0, a, b, d, s1) in transitions:
  80.             # Create states if they do not already exist
  81.             if not s0 in states:
  82.                 states[s0] = dict()
  83.             if not s1 in states:
  84.                 states[s1] = dict()
  85.  
  86.             # Symbols must be in alphabet
  87.             assert(a in t)
  88.             assert(b in t)
  89.             # Transition for this symbol must not already exist
  90.             assert(not a in states[s0])
  91.            
  92.             # Create transition
  93.             states[s0][a] = (b, d, s1)
  94.            
  95.         return states
  96.  
  97.     def trimmed_tape(self):
  98.         return list(filter(lambda b: b != None, self.tape))
  99.  
  100.  
  101. def from_bits(bits):
  102.     x = 0
  103.     for b in bits:
  104.         x = x << 1
  105.         x = x | b
  106.     return x
  107.  
  108. if __name__ == "__main__":
  109.  
  110.     import pprint
  111.  
  112.     def clear():
  113.         return TM(            
  114.             transitions = [
  115.                 (0, 0,    1,    TM.R, 0),
  116.                 (0, 1,    1,    TM.R, 0),
  117.                 (0, None, None, TM.L, 1)
  118.             ],
  119.             tape = [0,0,1,0,1,0],
  120.             start_state = 0
  121.         )
  122.    
  123.     # S -> 1S1
  124.     # S -> 11
  125.     def halve():
  126.         return TM(
  127.             alphabet = {1},
  128.             transitions = [
  129.                 (0, 1, 1,    TM.R, 1),
  130.                 (1, 1, None, TM.R, 0)
  131.             ],
  132.             tape = [1,1,1,1,1,1],
  133.             start_state = 0
  134.         )
  135.        
  136.     def add_one():
  137.         return TM(
  138.             alphabet = {0,1},
  139.             transitions = [
  140.                 (0, 0, 0, TM.R, 0),
  141.                 (0, 1, 1, TM.R, 0),
  142.                 (0, None, None, TM.L, 1),
  143.                
  144.                 (1, 0, 1, TM.L, 3),
  145.                 (1, 1, 0, TM.L, 2),
  146.                
  147.                 (3, 0, 0, TM.L, 3),
  148.                 (3, 1, 1, TM.L, 3),
  149.                 (3, None, None, TM.R, 4),
  150.                
  151.                 (2, 0, 1, TM.L, 3),
  152.                 (2, 1, 1, TM.L, 2),
  153.                 (2, None, 1, TM.L, 5),
  154.                
  155.                 (5, None, None, TM.R, 4),
  156.             ],
  157.             tape = [0,1,1,1,1,1],
  158.             start_state = 0
  159.         )
  160.        
  161.     def rshift():
  162.         return TM(
  163.             transitions = [
  164.                 (0, 0, None, TM.R, 1),
  165.                 (0, 1, None, TM.R, 2),
  166.                    
  167.                 (1, 0, 0, TM.R, 1),
  168.                 (1, 1, 0, TM.R, 2),
  169.                 (1, None, None, TM.L, 3),
  170.                
  171.                 (2, 0, 1, TM.R, 1),
  172.                 (2, 1, 1, TM.R, 2),
  173.                 (2, None, None, TM.L, 3)
  174.             ],
  175.             tape = [1,1,1,1,1,0],
  176.             start_state = 0
  177.         )
  178.        
  179.     def q4():
  180.         return TM(
  181.             transitions = [
  182.                 (0, 0,    1, TM.R, 1),
  183.                 (1, None, 0, TM.L, 2),
  184.                 (0, 1, 1, TM.R, 3),
  185.                
  186.                 (3, None, None, TM.L, 4),
  187.                 (4, 1,    0,    TM.L, 5),
  188.                 (5, None, None, TM.R, 6),
  189.                 (3, 0, 0, TM.L, 6),
  190.                 (3, 1, 1, TM.L, 6),
  191.             ],
  192.             #tape = [0],
  193.             #tape = [1],
  194.             #tape = [1, 0, 1],
  195.             tape = [1, 0],
  196.         )
  197.        
  198.     def q5():
  199.         return TM(
  200.             transitions = [
  201.                 (0, 0, 0, TM.R, 0),
  202.                 (0, 1, 1, TM.R, 0),
  203.                 (0, None, 1, TM.L, 1),
  204.                
  205.                 (1, 1, 1, TM.L, 2),
  206.                 (1, 0, 1, TM.L, 2),
  207.                
  208.                 (2, 1, 0, TM.L, 2),
  209.                 (2, 0, 0, TM.L, 2),
  210.                 (2, None, None, TM.R, 3)
  211.             ],
  212.             tape = [0],
  213.             start_state = 0
  214.         )
  215.  
  216.     tm = q4 ()
  217.    
  218.     print("STATES:")
  219.     pprint.pprint(tm.states, width=1)
  220.    
  221.     print("RUN:")
  222.    
  223.     print("input:", from_bits(tm.trimmed_tape()))
  224.     print(tm.tape)
  225.    
  226.     while(tm.move()):
  227.         print(tm.trimmed_tape())
  228.        
  229.     print("output:", from_bits(tm.trimmed_tape()))
  230.     print("head:", tm.head_index())
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top