 |
A Turing machine M is a finite device that performs operations on a paper tape. This tape is infinite in both directions, and divided into single cells (squares). At any time, each square of the tape contains a single symbol from a fixed finite list of input symbols Σ or the blank character #. Formally, a Turing machine is defined by the ordered quintuple (Q,qa,Σ,Γ,δ), where: Q is a non-empty and finite set of states; qa is the initial state; Σ is the input alphabet; Γ is the alphabet of the tape, defined by Γ=Σ⋃#, for a special character #, called blank character; δ :Q×Γ→Q×Σ×{L,R,P} is a partial transition function. We stipulate that the machine M starts computation in the initial state qa and the reading head positioned on the first left cell which is not the blank character #. The action that M takes at any instant depends on the current state of M and on the symbol currently being scanned. This dependence is defined in M’s transition function δ. This is one of many variations on the Turing machine theme (see for example [3], [6] and [7]). It is known that all of these definitions are equivalent. For information about the Turing machine, the reader is also referred to [2], [4], [9], [10], [11]. We describe a simulation of Turing machine by means of symbolic processing, functional programming, and representation of two-dimensional graphical images which are available in the programming language Mathematica. We define elements of a Turing machine in a specific way, deterministic as well as nondeterministic. Also, our simulation is done by very simple and effective code. We use some original techniques to set configuration and executing actions on Turing machine. We considered some other simulation ([5], [15], [15], [16]) of the Turing machine and we will give some notes about that. Main criteria used in this analysis are: existence of nondeterministic part, simply usage, graphical illusrations, power in computations, and code simplicity. We prefer the symbolic computation as, generally, the most appropriate tool for all of these requirements. The simulation in [16] has two parts. In the first part, it simulates deterministic Turing machine. This simulation uses object-oriented programming, but it is not user friendly and does not use symbolic computation. Second part contains simulation of the non-deterministic Turing machine. This simulation does only recognition of the input word, but not any computation. Moreover, graphical presentation is not used. The simulation [14] is very good visual simulation with powerful tools of computation, but there is a not nondeterministic part. This simulation is, essential, very similar to the simulation [15], but more better. The simulation [5] is the specific use of the Turing machine and it is interesting as a similar work in the same Mathematica package. Programs written in procedural computer languages such as C help with computations, but are of limited value in developing understanding of included algorithms, because very little information about the intermediate steps is presented. The user interface for such programs is primitive at best and typically requires definitions of user functions and data files corresponding to a specific problem. Many researches have a need for the capability to develop a “rapid-prototype” code to test the behavior of an algorithm before investing a substantial effort in developing a code for the algorithm in a procedural language such as C. The presentation is organized as follows: In the first section we give some theoretical background. In the second section we give an implementation of the deterministic Turing machine. In the third section we consider the non-deterministic Turing machine as a parallel work of n ∈ N deterministic Turing machine.
|
|
For the newest resources, visit Wolfram Repositories and Archives »
