Source code of the simulator

A simulator of multitape NDTMs in Python

Excluding input/output code and comments, the simulator is less than 100 lines of code. It is a testimony of Python power and economy. It’s object oriented but also uses functional constructs like list comprehensions.

Python3

####
# NDTM.py: a nondeterministic Turing Machine Simulator
# Author: David Gil del Rosal (dgilros@yahoo.com)
#### from collections import defaultdict, deque
 
class Tape:
    # Constructor. Sets the blank symbol, the
    # string to load and the position of the tape head
    def __init__(self, blank, string ='', head = 0):
        self.blank = blank
        self.loadString(string, head)
     
    # Loads a new string and sets the tape head    
    def loadString(self, string, head):
        self.symbols = list(string)
        self.head = head
         
    # Returns the symbol on the current cell, or the blank
    # if the head is on the start of the infinite blanks
    def readSymbol(self):
        if self.head < len(self.symbols):
            return self.symbols[self.head]
        else:
            return self.blank
         
    # Writes a symbol in the current cell, extending
    # the list if necessary
    def writeSymbol(self, symbol):
        if self.head < len(self.symbols):
            self.symbols[self.head] = symbol
        else:
            self.symbols.append(symbol)
             
    # Moves the head left (-1), stay (0) or right (1)
    def moveHead(self, direction):
        if direction == 'L': inc = -1
        elif direction == 'R': inc = 1
        else: inc = 0
        self.head+= inc
         
    # Creates a new tape with the same attributes than this
    def clone(self):
        return Tape(self.blank, self.symbols, self.head)
     
    # String representation of the tape
    def __str__(self):
        return str(self.symbols[:self.head]) + \
               str(self.symbols[self.head:])
     
 
class NDTM:
    # Constructor. Sets the start and final states and
    # inits the TM tapes
    def __init__(self, start, final, blank ='#', ntapes = 1):
        self.start = self.state = start
        self.final = final
        self.tapes = [Tape(blank) for _ in range(ntapes)]
        self.trans = defaultdict(list)
 
    # Puts the TM in the start state and loads an input
    # string into the first tape
    def restart(self, string):
        self.state = self.start
        self.tapes[0].loadString(string, 0)
        for tape in self.tapes[1:]:
            tape.loadString('', 0)
                     
    # Returns a tuple with the current symbols read
    def readSymbols(self):
        return tuple(tape.readSymbol() for tape in self.tapes)
 
    # Add an entry to the transaction table
    def addTrans(self, state, read_sym, new_state, moves):
        self.trans[(state, read_sym)].append((new_state, moves))
     
    # Returns the transaction that corresponds to the
    # current state & read symbols, or None if there is not
    def getTrans(self):
        key = (self.state, self.readSymbols())
        return self.trans[key] if key in self.trans else None
         
    # Executes a transaction updating the state and the
    # tapes. Returns the TM object to allow chaining    
    def execTrans(self, trans):
        self.state, moves = trans
        for tape, move in zip(self.tapes, moves):
            symbol, direction = move
            tape.writeSymbol(symbol)
            tape.moveHead(direction)
        return self
     
    # Returns a copy of the current TM
    def clone(self):
        tm = NDTM(self.start, self.final)
        tm.state = self.state
        tm.tapes = [tape.clone() for tape in self.tapes]
        tm.trans = self.trans        # shallow copy
        return tm
         
    # Simulates the TM computation. Returns the TM that
    # accepted the input string if any, or None.
    def accepts(self, string):
        self.restart(string)
        queue = deque([self])
        while len(queue) > 0:
            tm = queue.popleft()
            transitions = tm.getTrans()
            if transitions is None:
                # there are not transactions. Exit
                # if the TM is in the final state
                if tm.state == tm.final: return tm
            else:
                # If the transaction is not deterministic
                # add replicas of the TM to the queue
                for trans in transitions[1:]:
                    queue.append(tm.clone().execTrans(trans))
                # execute the current transition
                queue.append(tm.execTrans(transitions[0]))
        return None
     
    def __str__(self):
        out = ''
        for tape in self.tapes:
            out+= self.state + ': ' + str(tape)  + '\n'
        return out
     
    # Simple parser that builds a TM from a text file
    @staticmethod
    def parse(filename):
        tm = None
        with open(filename) as file:
            for line in file:
                spec = line.strip()
                if len(spec) == 0 or spec[0] == '%': continue
                if tm is None:
                    start, final, blank, ntapes = spec.split()
                    ntapes = int(ntapes)
                    tm = NDTM(start, final, blank, ntapes)
                else:
                    fields = line.split()
                    state = fields[0]
                    symbols = tuple(fields[1].split(', '))
                    new_st = fields[2]
                    moves = tuple(tuple(m.split(', '))
                                  for m in fields[3:])
                    tm.addTrans(state, symbols, new_st, moves)
        return tm
     
if __name__ == '__main__':
    # Example TM that performs unary complement
    tm = NDTM('q0', 'q1', '#')
    tm.addTrans('q0', ('0', ), 'q0', (('1', 'R'), ))
    tm.addTrans('q0', ('1', ), 'q0', (('0', 'R'), ))
    tm.addTrans('q0', ('#', ), 'q1', (('#', 'S'), ))
    acc_tm = tm.accepts('11011101')
    if acc_tm: print(acc_tm)
    else: print('NOT ACCEPTED')    

Multitape Nondeterministic Turing Machine simulator

This article tackles both theoretical and practical issues in Computer Science (CS). It reviews Turing Machines (TMs), a fundamental class of automata and presents a simulator for a broad variant of TMs: nondeterministic with multiple tapes. Nondeterminism is simulated by a breadth first search (BFS) of the computation tree.
The simulator is written in Python 3 and takes advantage of the power and expressiveness of this programming language, combining object oriented and functional programming techniques.
The organization is as follows. First, TMs are introduced in an informal manner, highlighting its many applications in Theoretical CS. Then, formal definitions of the basic model and the multitape variant are given. Finally, the design and implementation the simulator is presented, providing examples of its use and execution.

Source code of the simulator

Python3

Multitape Nondeterministic Turing Machine simulator

Similar Reads