A nontrivial example
As a final example, we present the specification of a 3-tape TM that recognizes the non context-free language .
The TM nondeterministically copies the contents of the first half of the string in tape #2 and the second half in tape #3. Then, it proceeds to check if both parts match.
% 3-tape NDTM that recognizes L={ ww | w in {0, 1}* }
q0 q4 # 3
% TRANSITIONS
% put left endmarkers on tapes #2 and #3
q0 0, #, # q1 0, S $, R $, R
q0 1, #, # q1 1, S $, R $, R
% first half of string: copy symbols on tape #2
q1 0, #, # q1 0, R 0, R #, S
q1 1, #, # q1 1, R 1, R #, S
% guess second half of string: copy symbols on tape #3
q1 0, #, # q2 0, R #, S 0, R
q1 1, #, # q2 1, R #, S 1, R
q2 0, #, # q2 0, R #, S 0, R
q2 1, #, # q2 1, R #, S 1, R
% reached end of input string: switch to compare state
q2 #, #, # q3 #, S #, L #, L
% compare strings on tapes #2 and #3
q3 #, 0, 0 q3 #, S 0, L 0, L
q3 #, 1, 1 q3 #, S 1, L 1, L
% if both strings are equal switch to final state
q3 #, $, $ q4 #, S $, S $, S
Example usage. Save the above file as “3ww.tm” and run the following code:
Python3
from NDTM import NDTMtm = NDTM.parse('3ww.tm')print(tm.accepts('11001100')) |
The output produced is as intended: the TM reached the final state and the contents of the two halves of the input string are in tapes #2 and #3.
Output :
q4: ['1', '1', '0', '0', '1', '1', '0', '0']['#']
q4: []['$', '1', '1', '0', '0', '#']
q4: []['$', '1', '1', '0', '0', '#']
An interesting exercise is trying to transform this TM in a one-tape nondeterministic TM or even in a one-tape deterministic one. It is perfectly possible, but the specification will be much more cumbersome. This is the utility of having multiple tapes: no more computational power but greater simplicity.
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.