TMSL TURING MACHINE SIMULATION LANGUAGE Language Manual and Project Report Isaac McGarvey iam2108 Joshua Gordon jbg2109 Keerti Joshi kj2217 Snehit Prabhu sap2131 Table of Contents 1 Introduction 1 1 1 Overview 1 1 2 Example 01 01 2 Language Tutorial 2 1 Compilation and Execution 02 3 Language Manual 3 1 Lexical Conventions 3 2 Declarations 3 3 Statements 03 04 04 4 Project Plan 4 1 Process 4 2 Programming Style 4 3 Project Timeline 4 4 Roles and Responsibilities 4 5 Development Environment 4 6 Project Log 09 09 09 10 10 10 5 Architectural Design 5 1 Block Diagram of Translator 5 2 Description of Architecture 11 11 6 Testing Plan 6 1 Compiler tests 6 2 Machine tests 6 3 End to end tests 6 4 Examples 13 13 13 13 7 Lessons Learned 18 8 Appendix 19 1 Introduction 1 1 1 Overview A Turing Machine is a simple but powerful computer It is useful in thinking about the nature and limits of computability because its method of computation is about as simple as can be imagined Important theoretical results about what can be computed that are expressed in the terms of Turing Machines are clearer to intuition than the same results expressed in other terms The Turing Machine is an automaton whose temporary storage is a tape This tape is divided into cells each of which is capable of holding one symbol Associated with the tape is a read write head that can travel left of write on the tape and that can read or write a single symbol on each move The automaton that we use as a Turing Machine will have neither an input file nor any special output mechanism Whatever input and output is necessary will be done on the machine s tape The Turing Machine Simulation Language TMSL is a programming language that is designed allow users to write programs that will be compiled into a Turing Machine that can execute the program Because Turing Machines are very different from normal computers and also far more restrictive in terms of the number of available operations TMSL is very different from a typical imperative programming language Programming a Turing Machine by specifying states and transitions is analogous to programming a modern computer in assembly at best We hope that TMSL will be a high level language relatively speaking for Turing Machines 1 1 2 Example As an example program we begin with the following which demonstrates unsigned addition Comments and bracketing are c style Notice that the alphabet is specified on the first line of the program This is mandatory and serves the purpose of describing those symbols which may be written to and read from the tape The empty symbol is included by default alphabet specification 0 1 true while the symbol under the tape head is 1 while 1 move the tape head one position to the right right if the symbol under the tape head is 0 if 0 move the tape head one position to the right right if the symbol under the tape head is 1 if 1 write 0 replace the current symbol under the tape head with 0 left move the tape head one position to the left write 1 replace the current symbol under the tape head with 1 1 2 Language Tutorial This chapter represents a tutorial for a novice to get started with TMSL 2 1 Compilation and Execution A TMSL program consists initially of a plain text tmsl file which contains the user defined program For now let us consider the example program of 1 1 3 unsigned addition Let us call this file unsignedAdd tmsl While this file alone is a complete specification of a TMSL program typically the user must also specify 1 the input tape for the Turing machine which is to execute the program and 2 the output tape file which is a blank target file overwriten with the final state of the tape when a Turing machine executes its program As a convention the input and output tape are given the extensions tape The input tape is a plain text file of format L where L is a symbol in the alphabet specified in the user program followed by a space repeated zero or more times For instance to add the numbers four and two we specify an input tape file as 1 1 1 1 0 1 1 the contents of the input tape are program specific For the output tape we specify a blank file output tape Compilation given unsignedAdd tmsl we compile the program by compiler compiler exe unsignedAdd tmsl transition tm where unsignedAdd tmsl is the user specified program and transition tm is the target output file to contain the resulting compiled state transition table Execution given transition tm input tape and output tape a user may execute the program on a turning machine by machine machine exe transition tm input tape output tape The output tape file will be transformed into a plain text file containing the final state of the tape For convenience we have included run bat in the root TMSL directory Run is a small batch file which automates the steps necessary to compile and execute user defined TMSL programs To compile execute and display the final state of the tape the user may command run bat unsignedAdd tmsl input tape output tape 2 3 Language Manual 3 1 Lexical Conventions 3 1 1 Tokens There are three types of tokens in this language identifiers symbols keywords and separators Tokens are whitespace delineated 3 1 2 Comments TMSL supports multi line comments A section of text beginning with and ending with is a comment An example comment is as follows this is a comment this is another comment 3 1 3 Symbols Symbols are values identifiers that can be read from and written to the tape A symbol is represented by a sequence of letters and digits Letters are not case sensitive symbol a z A Z 0 9 The only only special symbol is the symbol keyword to represent a blank All uninitialized cells of the tape contain the blank symbol As with any other symbol the symbol can also be read from or written to the tape The set of all symbols a machine can read and write excluding the symbol is called its alphabet 3 1 4 Symbol Lists A symbol list is a sequence of symbols separated by commas comma symbol list symbol comma symbol 3 3 1 5 Keywords The following are reserved for use as keywords and may not be used as identifiers if else unless while until left right write exit 3 1 6 Separators The following are used to indicate separators 3 1 7 Datatypes The only data type in TMSL is that of the set of symbols that the machine can process Each of the implicit variables in TMSL that is the cells on the tape are of this data type by definition 3 1 8 Variables TMSL does not have any explicit variables The cells of the tape act
View Full Document
Unlocking...