Code¶

Below is some python code for manipulating Turing machines. Scroll below to the palindromes section to see how it is used.

In [4]:
import copy

def initialConf (machine, word) :
    if 'onlyWorkTape' in machine:
        return {
            'state' : machine['initial'],
            'work tape' : ['⊢']+word,
            'work head' : 0
        }
    else:
        return {
            'state' : machine['initial'],
            'input tape' : ['⊢']+word+ ['⊣'],
            'input head' : 0,
            'work tape' : ['⊢'],
            'work head' : 0
        }
        

def doesTransitionApply (trans, conf) :
    
    #wrong state
    if trans['state before'] != conf['state']:
        return False

    #questions about work tape are asked only if it exists
    if 'input tape' in conf:
        #wrong input letter
        if ('input letter before' in trans) and (trans['input letter before'] != conf['input tape'][conf['input head']]):
            return False
        #input head falls out of input tape
        if ('move input head' in trans) and ((conf['input head'] + trans['move input head'] >= len(conf['input tape'])) 
                                         or (conf['input head'] + trans['move input head'] < 0)):
            return False

    #wrong work letter
    if ('work letter before' in trans) and (trans['work letter before'] != (conf['work tape'])[conf['work head']]):
        return False
    
    #work head falls out of work tape to the left
    if ('move work head' in trans) and (trans['move work head'] + conf['work head'] < 0):
        return False
    
    return True

#applies a transitions and returns the new configuration
def applyTransition(trans,conf):
    if not doesTransitionApply(trans,conf):
        raise Exception('tried to apply transition that does not apply')

    #a special configuration that halts and just gives the result, which is typically accept/reject
    if 'halt' in trans:
        return { 'halt' : trans['halt']}
    
    newconf = copy.deepcopy(conf);
    
    newconf['state'] = trans['state after']
    
    if 'move input head' in trans:
        newconf['input head']+=trans['move input head']
    
    if 'work letter after' in trans:
        newconf['work tape'][newconf['work head']] = trans['work letter after']

    if 'move work head' in trans:
        newconf['work head']+=trans['move work head']
            
    #if the work head moved out of work tape, add a new blank symbol
    if newconf['work head'] >= len(newconf['work tape']):
        newconf['work tape'] += ['']

    return newconf

#returns the list of all avaialable transitions
def availableTransitions(machine, conf):

    retval = []

    if (conf == 'accept') or (conf == 'reject'):
        return retval

    for t in machine['transitions']:
        if doesTransitionApply(t, conf):
            retval += [t]
    return retval

#returns the list of all configurations in a run, for the given input string
#if several transitions apply, the first one is used

def run(machine, string):
    
    conf = initialConf(machine, string)

    #the return value is a list of configurations
    retval = []
    while True:
        retval += [conf]

        if 'halt' in conf:
            break

        #there is a timeout of 10k transitions
        if len(retval) > 100:
            retval+=[{'halt':'reject because run length exceeded'}]
            break
            
        transitionList = availableTransitions(machine, conf);
        
        if len(transitionList) == 0:
            retval+=[{'halt':'reject because no transition applied'}]
            break
        
        #we use first available transition
        t =transitionList[0]
        conf = applyTransition(t,conf)
        
        
    return retval

#this part of the code displays runs in HTML
from IPython.core.display import HTML

#returns HTML representation of a single cell
def cellHTML(content, head) :
    if head:
        return '<span style="background-color:red; padding: 5px; margin: 3px">' +  content + '</span>'
    else:
        return '<span style="background-color:lightgrey; padding: 5px; margin: 3px">' +  content + '</span>'

#returns HTML representation of a tape, which can be the input or work tape
def tapeHTML(string, head) :
    if (head < 0 or head >= len(string)):
        raise Exception('head out of bounds')
    index = 0
    retval = '<span style="margin:20px">'
    for x in string:
        retval += cellHTML(x, index == head)
        index += 1
    return retval + '</span>'

#returns HTML representation of an entire configuration
def confHTML(conf) :
    retval = '<div style="padding:20px">'
    if ('halt' in conf):
        retval += conf['halt']
    else:
        retval +='<span style="display:inline-block; width:100px"> state:' + conf['state'] + '</span>'
        #if the machine is two tape, then it has a separate input tape
        if ('input tape' in conf):
            retval += 'input tape:'
            retval += tapeHTML(conf['input tape'], conf['input head'])
            retval += 'work tape:'
        #both one and two tape machines have a work tape
        retval += tapeHTML(conf['work tape'], conf['work head'])
    
    retval += '</div>'
    return retval 

def displayConf(conf) :
    HTML(confHTML(conf))
    
def displayRun(machine,string):
    retval = ''
    for conf in run(machine, string):
        retval += confHTML(conf)
    return HTML(retval)

The syntax of Turing machines is explained below, on the example of a machine for palindromes

Palindromes¶

We give two example machines for palindromes. One is the (default) two tape machine, and the other is a one tape machine.

Two tape palindromes¶

Here is a (two tape) Turing machine with input alphabet ['a','b'] that accepts exactly the palindromes.

In [2]:
machine = { 'initial' : 'p',
          'transitions' : [
           {'state before' : 'p', 'state after' : 'p', 'input letter before' : '⊢','move input head' : 1,'move work head' : 1,'work letter after' : '⊢'},
              {'state before' : 'p', 'state after' : 'p', 'input letter before' : 'a', 'move input head' : 1, 'move work head' : 1,'work letter after' : 'a'},
              {'state before' : 'p', 'state after' : 'p', 'input letter before' : 'b', 'move input head' : 1, 'move work head' : 1, 'work letter after' : 'b'},
              {'state before' : 'p', 'state after' : 'q', 'input letter before' : '⊣', 'move input head' : -1},
              {'state before' : 'q', 'state after' : 'q', 'input letter before' : 'a','move input head' : -1},
              {'state before' : 'q', 'state after' : 'q', 'input letter before' : 'b', 'move input head' : -1},
              {'state before' : 'q', 'state after' : 'r', 'input letter before' : '⊢','move input head' : 1,'move work head' : -1},
              {'state before' : 'r', 'state after' : 'r', 'input letter before' : 'a','work letter before' : 'a' ,'move work head' : -1, 'move input head' : 1},
              {'state before' : 'r', 'state after' : 'r', 'input letter before' : 'b','work letter before' : 'b' ,'move work head' : -1, 'move input head' : 1},
            {'state before' : 'r', 'input letter before' : '⊣','halt' : 'accept' },
           ]
          }

A machine consists of an initial state, and a list of transitions. The states are implicit – these are the states that appear in the transitions, and also the work and input alphabet are implicit. The states are strings (and not just letters), the same is true for letters of the input and work alphabet, i.e. each such letter is a string. A transition is a record that has the following fields: 'state before', 'state after', 'input letter before', 'work letter before', 'move input head', 'move work head', 'input letter after', 'work letter after'. The fields concerning the letters (both input and work, both before and after) are optional. Omitting a '* letter before' field means the transition applies to all letters, omitting a '* letter after' field means the cell keeps its old value and is not overwritten.

In [6]:
displayRun(machine,['a','a','b','a','a'])
Out[6]:
state:pinput tape:⊢aabaa⊣work tape:⊢
state:pinput tape:⊢aabaa⊣work tape:⊢
state:pinput tape:⊢aabaa⊣work tape:⊢a
state:pinput tape:⊢aabaa⊣work tape:⊢aa
state:pinput tape:⊢aabaa⊣work tape:⊢aab
state:pinput tape:⊢aabaa⊣work tape:⊢aaba
state:pinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:qinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
state:rinput tape:⊢aabaa⊣work tape:⊢aabaa
accept

One tape palindromes¶

Here is a one tape machine that recognizes the palindromes, again over the alphabet 'a' and 'b'. In the one tape variant, there is a flag 'onlyWorkTape' : true, which is not used in the default two tape format. The work tape is the only tape.

In [4]:
oneTapeMachine = { 'onlyWorkTape' : True,
                  'initial' : 'init',
                  'transitions' : [
                      {'state before' : 'init', 'state after' : 'q', 'move work head' : 1},
                      {'state before' : 'q', 'state after' : 'senda', 'work letter before': 'a', 'move work head' : 1,'work tape after' : ''},
                      {'state before' : 'senda', 'state after' : 'senda', 'work letter before': 'a', 'move work head' : 1},
                      {'state before' : 'senda', 'state after' : 'senda', 'work letter before': 'b', 'move work head' : 1},
                      {'state before' : 'senda', 'state after' : 'checka', 'work letter before': '', 'move work head' : -1},
                      {'state before' : 'checka', 'state after' : 'return', 'work letter before': 'a', 'move work head' : -1, 'work tape after' : ''},
                      {'state before' : 'q', 'state after' : 'sendb', 'work letter before': 'b', 'move work head' : 1,'work tape after' : ''},
                      {'state before' : 'sendb', 'state after' : 'sendb', 'work letter before': 'a', 'move work head' : 1},
                      {'state before' : 'sendb', 'state after' : 'sendb', 'work letter before': 'b', 'move work head' : 1},
                      {'state before' : 'sendb', 'state after' : 'checkb', 'work letter before': '', 'move work head' : -1},
                      {'state before' : 'checkb', 'state after' : 'return', 'work letter before': 'b', 'move work head' : -1, 'work tape after' : ''},
                      {'state before' : 'return', 'state after' : 'return', 'work letter before': 'a', 'move work head' : -1},
                      {'state before' : 'return', 'state after' : 'return', 'work letter before': 'b', 'move work head' : -1},
                      {'state before' : 'return', 'state after' : 'q', 'work letter before': '', 'move work head' : 1},
                      {'state before' : 'q', 'work letter before': '', 'halt' : 'accept'},                  
                      {'state before' : 'checka', 'work letter before': '', 'halt' : 'accept'}, 
                      {'state before' : 'checkb', 'work letter before': '', 'halt' : 'accept'}, 
                  ]
          }
In [7]:
displayRun(oneTapeMachine,['a','b','b','b'])
Out[7]:
state:init⊢abbb
state:q⊢abbb
state:senda⊢abbb
state:senda⊢abbb
state:senda⊢abbb
state:senda⊢abbb
state:checka⊢abbb
reject because no transition applied