Introduction

We are going to simulate deterministic Turing machines and nondeterministic Turing machines in Python. Open a file named prog3_turing.py.

1 -- Deterministic Turing Machines

The goal of this problem is to write a function that simulates the execution of a Turing machine. A Turing Machine is formally defined as a 6-tuple (Q, Σ, δ, q0, qaccept, qreject). We first need to define a data-structure to encode Turing machines. Without loss of generality, we can assume that Q is modelled with integers and Σ with characters, which are both primitive types in Python. The transition function δ is usually defined as a function δ: Q x Σ -> Q x Σ x {L,R}. Strictly, this definition corresponds to a complete Turing machine, analoguous to complete-DFA. In practice, it will be more convenient to work with transition functions that are not necessarily complete. Therefore, a more adequate representation for a partial function δ is a list of transitions, where each transition is encoded as a quintuple: { (q,a,q',b,m) | δ(q,a) = (q',b,m) }. In Python, we encode δ as a list containing lists of 5 elements. To interpret this list of transitions as the function δ, we define a function delta() that takes a list of transitions lst, a pair q,a, and returns the triple (q',b,m) when (q,a,q',b,m) is in the list lst. A move instruction is encoded by the strings "Left" , "Right", or "Stay". We assume that the list lst does not contain several 5-tuples starting with q and a because the Turing machine is deterministic. Complete the following skeleton code for delta() and notice that the function is recursive, it returns the empty list when no transition is found, and a list of three elements otherwise:


def delta(lst,q,a):
  if lst == []:
    return []
  else:
    ...
    if ... :
      return [q', b, m]
    else:
      return delta(lst[1:],q,a)

A Turing machine is encoded using a class:


class TM:
  def __init__(self,transitions,qstart,qaccept, qreject):
    self.transitions = transitions
    self.qstart = qstart
    self.qaccept = qaccept
    self.qreject = qreject

Next, to encode the tape with the head, let us use the mathematical specification we used in class, that is a tape with its head is an element of (Σ * x Σ x Σ *). This will prove to be efficient when dealing with nondeterminisitic Turing machines in the next section.


class TapeHead:
  def __init__(self, left = [], head = '_', right = []):
    self.left = left
    self.head = head
    self.right = right

The three types of operations that can be performed on a tape by a Turing machine is replace the symbol pointed by the head with another symbol, and moving the head left or right. For example, the tape (abc, d, efg) is encoded as TapeHead(['a','b','c'], 'd', ['e','f','g']). Moving the head to the right would produce a TapeHead(['a','b','c','d'], 'e', ['f','g']). Moving the head to the left would produce a TapeHead(['a','b'], 'c', ['d','e','f','g']). Do not forget the special cases when the head is at the leftmost position of the tape or when the head is at the rightmost position of the tape.

Problem 1

Implement these tape operations, making sure that the TapeHead is a persistent data structure, which means that the operations should not modify in place each field but instead create a new TapeHead object with modified fields. In practice, to make it persitent, you simply have to use the following basic operations on strings: concatenation +, selecting the head of a list with lst[0], get the tail of a list lst[1:], and get a list without its last element lst[:-1]. Implement functions moveLeft(), moveRight() and replace() that take as input a tape with its head, and returns the new tape with head according to the operation.
```
def moveLeft(tapehead):
  ...
  return TapeHead(u,a,v)

def moveRight(tapehead):
  ...
  return TapeHead(u,a,v)

def replace(tapehead,b):
  ...
  return TapeHead(u,a,v)
```
A configuration from (Q x TapeHead) can simply be encoded with a list containing with two elements, the current state and the current tapehead. Write a function init() that returns the initial configuration for an input Turing machine and a given input string w.
```
def init(tm,w):
  ...
```
Write a function onestep() that simulates a single step of computation of a Turing machine given a configuration. The function onestep() must return the next configuration.
```
def onestep(tm,q,tapehead):
  ...
```
Using the previous function onestep(), write a function called allsteps() that computes iteratively all the steps until it reaches an halting state, that is the accept state or the reject state. This function should be recursive and return a halting configuration if the machine halts, or loop forever if that is what the machine is intended to do.
```
def allsteps(tm,q,tapehead):
  ...
```
Finally, define a function simulation() that takes as input a Turing machine and an input string and executes the machine on the input string. The function simulation() uses init() and allsteps and returns a boolean indicating if the input string is accepted or rejected, or it loops forever.
```
def simulation(tm,w):
  ...

    
```

2 -- Nondeterministic Turing Machines

For nondeterministic Turing machines the encoding of the transition function, tape and configurations are the same as for deterministic machines. Therefore, we can reuse the classes TM and TapeHead.

Problem 2

Extends the functions defined previously to be able to deal with nondeterministic Turing machines.

The function delta() becomes deltaNTM() and returns a list of triples (q',b,m).
The function onestep() becomes onestepNTM() and returns now a list of configurations according to the possible transitions returned by deltaNTM(). Notice, that it is key here to have a persistent data-structure for configurations, in order to make sure that the list of configurations after one step of computation are correct.
I let you figure out how to extend simulation() to simulationNTM() in order to finally implement a recognizer for nondeterministic Turing machines. At first, you may consider to adapt the idea we discussed in class that consists of listing all the possible sequences of transitions, and simulating each sequence of transitions until one reaches the accept state. This solution is acceptable when the programming language available for the simulation is a Turing machine, but since we are in Python we may consider more advanced data-strucuture, and in particular using trees for the underlying computation tree of NTM. So instead, consider doing the simulation by build a tree of computation by iterative deepening which is an efficient search at the intersection of depth-first search and breadth-first search. The recognizer should be a function that returns true is the input is recognized and otherwise returns false or is allowed to loop forever (until a stack overflow exception occurs).
```
def recognizer(ntm,w):
  ...

    
```

3 Test your work

Problem 3

Encode a deterministic turing machine deciding the language {a^n b^n c^n}
```
tm1 = TM(..., ..., ..., ...)

    
```
Make sure the simulation function simulation() is correct for 6 different, well chosen, input strings (3 accepted strings and 3 rejected strings).
```
b1 = simulation(tm1,w1)
b2 = simulation(tm1,w2)
...
b6 = simulation(tm1,w6)

    
```
Encode a nondeterministic turing machine recognizing the language {a^i b^j c^k | i = j or j = k}. To answer correctly the question your machine must solve the problem in a nondeterministic manner.
```
ntm1 = TM(..., ..., ..., ...)

    
```
Make sure the simulation function simulationNTM() works correctly by testing it on 6 different input strings (3 strings that accept and 3 strings that rejects or loop forever).
```
c1 = simulationNTM(ntm1,v1)
c2 = simulationNTM(ntm1,v2)
...
c6 = simulationNTM(ntm1,v6)

    
```

Make sure that if I run your program, it will print clearly all the tests, such that I can quickly evaluate your work, thanks!

4 Submit your work

Copy your file to the csci341 git folder. Add, commit and push your work.