Simulating Turing Machines in Python

Specification

We want to specify the code of a Deterministic Turing Machine via a json document. Here is an example of a machine recognizing the words of the form \(a^*b^*\).

{
    "initial" : "qstart",
    "accept"  : ["qaccept"],
    "reject" : ["qreject"],
    
    "transition" : {
    "qstart": {
        "b": ["qreadb", "b", 1],
        "a": ["qstart", "a", 1],
        "_": ["qaccept", "_", 0]
    },

    "qreadb": {
        "a": ["qreject", "a", 0],
        "b": ["qreadb", "b", 1],
        "_": ["qaccept", "_", 0]
    }
        
    }
}

It has states qstart, qaccept, qreject and qreadb. The initial state is qstart and is specified via the key initial, qaccept is the only accepting state which is specified via the key accept containing a list of accepting states, qreject is the only rejecting state, specified via the key reject containing a list of rejecting states.

The transition table is given as a dictionnary via the key transition. Each entry of this dictionnary associates a state with its transition rule. A transition rule is a dictionnary itself associating a letter of the working alphabet to a tuple containing the next state, the new letter to write on the tape and the head movement (-1 for left, 0 to stay, 1 for right).

More formally, we encode the states of a Deterministic Turing Machine with an hashable state and the machine is specified via a dictionnary having the following structure:

There is a key initial associated to a state,
There are keys accept and reject both associated to a list of states,
There is a key transition associated to a dictionnary having the following structure:
- Each key is a state,
- It associate each state to a dictionnary whose keys are letters of the working alphabet (the input alphabet augmented with a blank letter _ and a begining of the tape letter ^ by convention) and which associates to each letter, a 3-uplet containing a state, a letter and a number in \(\{-1,0,1\}\).

We use pydantic to specify the schema corresponding to a well-typed structure describing a DTM as follows:

class DTMCode(BaseModel):
    initial:  Hashable # Initial state
    accept:   List[Hashable] # Accepting states 
    reject:   List[Hashable] # Rejecting states
    transition : Dict[Hashable, Dict[str, Tuple[Hashable, str, Literal[-1, 0, 1]]]] # Transition table

Have a look at the file tm_lib.py. It contains code to load a JSON file describing a DTM. The previous JSON example can be found here asbs.json.

Exercise

Simulating DTM

In this exercise, our goal is to implement an emulator for DTM having one semi-infinite tape (that is, infinite only to right). To be able to detect the border of the tape, we assume that there is a reserved letter “^” on the first entry of the tape and that this letter cannot be used in the input alphabet (one can use it in the transition table, but it is at your own risk).

You will find skeleton code for class DTM in the file skeleton.py. You will implement the methods according to the specification given as comments in the code. (You do not need to edit the file tm_lib.py).

Some Turing Machines

In this exercise, you will implement the following Turing Machines (using the format previously defined):

A Turing Machine recognizing words of the form \(a^nb^n\) for \(n \geq 0\).
A Turing Machine recognizing palindroms on alphabet \(\{a,b\}\).
A Turing Machine that copy its input. That is, on input \(w \in \{a,b\}^*\), it stops and accepts on the following configuration: ^w^w.

Compilation

Transforming DTM

Write a function DTM_Not(M : DTMCode[T]) : DTMCode[T] that takes the code M of a DTM and returns the code of a DTM that accepts a word w if and only if M rejects w.
Write a function DTM_And(M1 : DTMCode[T], M2 : DTMCode[T]) : DTMCode[T] that takes the codes M1 and M2 of two DTM and returns the code of a DTM that accepts a word w if and only if both M1 and M2 accepts w.

Mono, Bi-infinite tape

The goal of this exercise is to show that mono, semi-infinite tape Deterministic Turing Machine that we have defined in the previous section is as general — computation-wise at least – as bi-infinite tape.

We assume that we are given the description of a DTM with one bi-infinite tape. Concerning the input description of the DTM, we keep the same format as the one given in the specification, but that machine is now supposed to be executed on a bi-infinite tape. We however assume that the machine does not use the symbole “^”. For exemple, the following machine will reject one a semi-infinite tape machine and will run infinitely on a bi-infinite machine on empty input:

{
    "initial" : "qstart",
    "accept"  : ["qaccept"],
    "reject" : ["qreject"],
    
    "transition" : {
    "qstart": {
        "_": ["qstart", "_", -1]
        }
    }
}

Implement a function compileSemi(M : DTMCode[str]) : DTMCode[Tuple(str,int)] taking as input the code of a DTM M that is supposed to run on bi-infinite tape machine and produces a DTM code M' running on semi-infinite tape such that for every word w, M' accept w if and only if M accept w. To simplify, we assume that M does not use the letter “^” and that the states of M are encoded as strings.

Hint: we construct M' such that the entry i of the tape of M is always written on the tape of M' at position \(2i+1\) if \(i\leq 0\) and at position \(-2i\) for \(i < 0\).

Corrections

L’évaluateur est ici
Les machines sont ici:

Compiled the: mar. 17 déc. 2024 14:03:14 CET