TM VERSION 1.3 CONTENTS: 1) Introduction 2) Files 2.1) Quintuple Files 2.2) Macro Files 3) TM Command Syntax 4) Macros 5) Break Points and Watch Points 6) TM Commands 6.1) 'exit' or 'quit' 6.2) '#' 6.3) 'enter' 6.4) 'set' 6.5) 'show' 6.6) 'step' 6.7) 'go' 6.8) 'delete' 6.9) 'move' 6.10) 'read' and 'write' 6.11) 'edmacro' 6.12) 'run' 6.13) 'say' or 'echo' 6.14) 'help' 1) INTRODUCTION TM is a turing machine interpreter. With it you can create, alter and run turing machines. A turing machine is a model of a computer. It has a finite number of states, and it is capable of reading and modifying a tape. A turing machine program consists of a list of 'quintuples', each one of which is a five-symbol turing machine instruction. For example, the quintuple 'SCcsm' is executed by the machine if it is in state 'S' and is reading the symbol 'C' on the tape. In that case, the instruction causes the machine to make a transition to state 's' and to overwrite the symbol 'C' on the tape with the symbol 'c'. The last operation it performs under this instruction is to move the tape reading head one symbol to the left or right according to whether 'm' is 'l' or 'r'. The turing machine starts in state '0' reading the left-most symbol on the tape. The turing machine halts if it is in a state for which there is no quintuple telling it what to do for the symbol being read. The turing machine is said to 'halt in a final state' if there is no quintuple at all on the list with the given state symbol as a first character. If a turing machine halts in a final state for a given tape it is said to 'accept' or 'recognize' the tape. It is asserted that any effective procedure can be reproduced by a turing machine (Church-Turing Thesis). See any standard computer science text on languages or discrete mathematics for a more detailed treatment. the TM program may optionally be run with an input file of quintuples as argument, e.g., $ tm (filename). See below about quintuple files. Currently TM handles two types of files; quintuple files and macro files... see below for more information. The current version of TM is capable of managing one tape and one quintuple list at a time. Quintuple lists may be entered interactively or by means of a user-written file. Tapes are entered interactively only. A 'macro' is a sequence of TM commands that is stored and may be played back at any time. Macros may be entered interactively or by means of a user created file. 2) FILES 2.1) Quintuple Files Files containing a quintuple list and associated comments may be read and written during the execution of TM. The default extension for a quintuple file is '.tm', but other extensions may be specified on file input and output. A quintuple file may be read when TM is started by specifying it as an argument. A quintuple file consist of an optional header section which contains, perhaps, information about the quintuple list, followed by the list itself. The header section may be any ASCII text which does NOT CONTAIN a left parenthesis in any first column. The start of the quintuple list section is signaled by the first occurrence of a left parenthesis, '(', in the first column. Each following quintuple must begin with a left parenthesis in the first column. The next 5 characters are the characters of the quintuple. Any following characters on that line are interpreted as a comment for that quintuple. TM reads and writes the header section, the quintuples, and any comments that follow a quintuple on the same line. Comments may be put between lines of quintuples as long as they do not start with '(', but these are not read. Quintuples must always start with a left parenthesis in the first column. The following is an example of a TM input file: ***************************************************************** This is the header section for a well-formed parentheses string checker. It will test whether or not an input tape containing parentheses has them nested correctly. The machine is adopted from Prather, page 481. Now follows the quintuple list. (0((0R The first '(' indicates that the next 5 symbols are a quintuple. (0)A1L (0AA0R (0 2L (1(A0R this line is also a comment, but it is not read by TM. TM will signal that there are no quintuples here. (1AA1L (1 NR Prather has 0 in this quintuple instead of R (2((NR Prather has 0 in this quintuple instead of R (2AA2L (N--NR Never used. Its existence forces N to be a non-final halting state. (2 YR ************************************* If the file is read and then written, the resulting output from TM is: ************************************* This is the header section for a well-formed parentheses string checker. It will test whether or not an input tape containing parentheses has them nested correctly. The machine is adopted from Prather, page 481. Now follows the quintuple list. (0((0R The first '(' indicates that the next 5 symbols are a quintuple. (0)A1L (0AA0R (0 2L (1(A0R is. (1AA1L (1 NR Prather has 0 in this quintuple instead of R (2((NR Prather has 0 in this quintuple instead of R (2AA2L (N--NR Never used. Its existence forces N to be a non-final halting state. (2 YR ************************************************************************ Note that only the header comment, the quintuples, and comments on the same line as a quintuple are written out. 2.2) Macro Files A 'macro' is a command stream stored in memory that may be played back at any time. See the discussion below in Section 3) about command streams and the discussion in Section 4) about macros. Macros may be read from and written to files. The default extension for a macro file is '.mac', but any extension may be specified at input or output. In the file, all lines that don't start with the characters '#' or '!', which denote comment lines, are read word by word into a macro buffer. a quoted string of 80 characters or less may be read, but the quoted string must be contained all on one line. The following is a sample macro file, e.g., 'test.mac': # A couple of tapes to be tested: # say "First tape is 00" set tape 00 go show tape # # That was the first tape. Now the second: # say "second tape is 11" set tape 11 go show tape The above file is arranged to be read easily. If it is written out to a new macro file, the indentation and comments are lost. The following is the file that would be written for the above sample macro. It is also what you would see if you entered the command 'show macro'. say "First tape is 00" set tape 00 go show tape say "second tape is 11" set tape 11 go show tape 3) TM COMMAND SYNTAX TM commands are entered as streams of words. Most of the words may be abbreviated. The set of routines that handle command streams can be found in the file 'getcmd.c'. Some streams consist only of a single word, such as 'go', 'exit' or 'list'. Others consist of several words, such as 'set trace tape'. Whenever a stream is insufficient to cause an action, the user is prompted for more input. Some streams allow an optional numeric qualifier. For example, to cause the turing machine to operate, one may enter 'step' or 'step 10'. The first stream causes one quintuple instruction execution, and the second causes ten instruction executions. 'step 1' has the same effect as 'step'. Command streams may be concatenated. The following shows how one would read a quintuple file (for example, test.tm), create a tape and then run the machine to completion: tm> read tm test tm> set tape ((())) tm> go The streams may be concatenated as follows to get the same effect: tm> read tm test set tape ((())) go Commas or semi-colons may be inserted to make the line more readable: tm> read tm test, set tape ((())), go Commas and semi-colons, like white-space, are ignored by the command processor. To insert characters which are normally ignored by the processor, use double quotes. For example, tm> read tm test, set tape "aa aa aa", go sets the tape so that it consists of three instances of 'aa' separated by blanks. 4) MACROS A command stream may be entered and executed as a macro. For example, the command tm> set macro set tape 0 go, set tape 1 go exit makes it possible to execute the command stream 'set tape 0 go set tape 1 go' at any time during the current TM session by entering the command 'run'. The comma is interpreted as white-space and is just used to make the macro easier to read. Macro entry is initiated by the command 'set macro' and terminated by entering 'exit', or '.' after a space (or ^Z for VMS users). The macro may be edited. The editing mode is entered with the command 'edmacro', and exited with 'exit' or '.' (or ^Z for VMS users). Macros may be saved for future sessions by writing them to a file. Use the command stream 'write mac (filename)'. The default extension for a macro file is '.mac'. See Section 2.2) about macro files. 5) BREAK POINTS AND WATCH POINTS Break and watch points cause the machine execution to halt if any are encountered. This allows the user to examine the condition of the machine to check for any bugs in his turing machine program. Break points are set for quintuples, and cause the machine to halt just before the quintuple for which the break is set is executed. Watch points may be set for either states or tape symbols. These cause the machine to halt just before a transition is made to the state for which watch is set, for just before the symbol for which watch is set is written to tape. The user has two ways in which he can continue past a watch or break point: enter 'step' or 'step 1', or 'set debug off'. As long as debug is set 'off' break and watch points are ignored. Break and watch points are also ignored for the execution of single steps. The default at program startup is that debug be set on. The user can determine whether or not debug is on by entering 'show debug'. 6) TM COMMANDS 'help' or '?' may be entered at certain points to get help on responses that are acceptable at that point. An extended description of some of the commands is given in the subsections below. These commands can be abbreviated when they are entered. The commands that may be executed at the tm> prompt are: 'add'. Add a quintuple to the quintuple list. 'delete'. Delete a quintuple or the entire quintuple list. 'edmacro'. Enter macro editing mode. 'enter'. Enter quintuple input mode. 'exit', 'quit', '.' (or ^Z for VMS users). Halt the current session. The current quintuple list, tape and macro ARE NOT SAVED. 'go'. Execute the turing machine until it halts. 'list'. List all the quintuples. 'move'. Move the tape head on the tape a given number of cells. 'read'. Read a quintuple file or a macro file. 'run'. Run the macro. 'say' or 'echo'. Print out the next word or quoted string to be entered. 'set'. Set a number of turing machine characteristics. 'show'. Show the current state of various things. 'step'. Execute one or more cycles of the turing machine. 'write'. Write the current quintuple list or macro to a file. 6.1) 'exit', 'quit', '.' (or ^Z for VMS users) The program is exited. NO FILES ARE WRITTEN at exit time, so if the user wishes to save anything, he must issue a write command first. In the current version, tapes can not be saved. These commands are also used to exit from macro edit mode, from help, and to abort command stream entry at certain points. In the following example, the user enters the stream 'set trace'. He is prompted for more input since the stream is incomplete. The command is aborted when he responds with 'exit', 'quit', '.' (or ^Z ONLY in VMS). tm> set trace set trace 'tape', 'descriptor' or 'off'? exit tm> 6.2) '#' This informs TM that the rest of the line is a comment. '#' MUST be followed by white-space. Some examples: tm> # This is a comment tm> set tape (( # this line sets the tape to '((' The following generates an error tm> #This is a comment 6.3) 'enter' The program enters a quintuple entry mode. Enter each quintuple on a line by itself as a five character string which must be preceeded in column 1 by '('. All other characters that follow on that line are accepted as a comment for that quintuple. The input mode is exited by entering '.' in column 1. VMS users may exit at any time by entering ^Z. Commands that are entered after 'enter' are executed once the entry mode is left. For example, the command stream tm> enter; list; show tape will initiate quintuple entry mode, then once the mode is exited, the list will be shown ('list'), and then the tape will be shown ('show tape'). The semicolon ';' is not required. 6.4) 'set' To add a quintuple to the quintuple list enter 'add'. You can 'set' the following: 'set trace tape', 'set trace descriptor' or 'set trace off'. This specifies if the tape is displayed at each turing machine cycle, or if the instantaneous machine descriptor is displayed. Neither is displayed if trace is 'off'. Default at program startup is 'off'. If trace is set to 'tape' and debug is 'on' then the machine state, the quintuple that resulted in the current state, and the next quintuple to be executed are displayed as well as the tape. 'set debug on' or 'set debug off'. Setting debug 'on' causes the machine to halt at break points and watch points. When debug is set 'off' the machine will not halt at break and watch points. The default at program startup is 'on'. 'set watch state (character)' or 'set watch symbol (character)', where (character) represents a state, as in the first command, or a symbol. No checking is done to see if the state or symbol is really being used in the machine. 'set break (string)', where (string) is the first two characters of a quintuple. The user is informed if the quintuple doesn't exist, and in that case nothing is set. 'set display comments on(off)' to cause comments to be displayed (or not displayed) whenever their associated quintuples are displayed. The default at program startup is 'off'. 'set display iterations on(off)' to view (or not to view) the number of times a quintuple has been executed whenever it is displayed. The default a program startup is 'off'. 'set display none' to cause quintuples to be displayed without comments or number of iterations. 'set macro' causes macro input mode to be entered. All commands entered until 'exit' or '.' (or ^Z for VMS users) are put into storage and can be replayed by entering 'run'. 'run' is not allowed to be put in a macro. 'set max_step' sets the maximum number of steps that will be executed by the 'go' command. When that number of steps have been taken the user is giving the opportunity to halt execution. 'set tape' causes the next word or string to be input as a tape. The machine state is set to 0, the initial state, at program startup time and when a new tape is read. 'set state' followed by a character sets the machine state to that character. 'set symbol' followed by a character causes the character to be written on the tape at the location of the tape head. 'set comment' allows the user to enter a comment for a quintuple. The user is prompted for which quintuple is to get the comment. If 'exit' or '.' (or ^Z for VMS users) is entered at 'set' time, nothing is set. If 'help' or '?' is enter, help is displayed for the set command. 6.5) 'show' You can 'show' the following: 'show debug'. Whether debug mode is on or off. 'show state'. The current state of the turing machine. 'show count'. The number of executions that have been executed so far. 'show tape'. The current tape, position of the tape head on it, and the machine state. 'show length'. The current length of the tape. 'show filename'. The last quintuple file which was read into TM. 'show macro'. Show the macro command stream. 'show max_step'. Show the current value of 'max_step', which is the maximum number of steps executed by the machine when 'go' is entered. When that number of steps have been taken the user is giving the opportunity of halting the machine execution. 'show quint', then entering two characters causes the quintuple that starts with those characters to be shown if it exists. 'show header'. If a .tm file has been read, and it contains a header, then that is displayed. 'show next'. Show the next quintuple to be executed. 'show last'. Show the last quintuple that was executed. Entering 'exit' or '.' (or ^Z for VMS users) after entering 'show' causes nothing to be shown-- control is returned to the tm> prompt. Entering 'help' or '?' provides help for the show command. 6.6) 'step' Entering 'step' causes the turing machine to execute one instruction. 'step n', where n is an integer, causes it to execute n instructions. 6.7) 'go' Entering 'go' causes the turing machine to continue to execute until either the machine enters a halting state, or until a number of instructions equal to 'max_step' have been executed. In the later case, the program pauses and the user is asked if the program should continue. 'max_step' may be modified by entering 'set max_step (number)'. 6.8) 'delete' You may delete a single quintuple or 'delete all' to delete all quintuples. For example, 'del 00' will delete the quintuple starting with the string '00'. 6.9) 'move' 'move right' or 'move left' causes the tape head to move right or left one cell on the tape. You may specify a number of cells to move-- for example 'move left 10'. By the usual convention for turing machines blank cells are created as needed to prevent the head from falling off the end of the tape. 'move left end' or 'move right end' causes the tape head to be placed at the left or the right end of the tape. In this case no blank cells are created. 6.10) 'read', 'write' Causes a file of quintuples or a macro to be read or written. See section 2) on turing machine files. When reading or writing a file you must specify a filename-- you are prompted for one if you don't. If you don't specify an extension, then '.mac' or '.tm' is used as the defaults for macro files or quintuple files. You specify a macro file or a quintuple file as the following examples show. tm> read mac (filename) tm> write tm (filename) Again, the default extension for quintuple files is '.tm', and for macro files is '.mac'. 6.11) 'edmacro' Enter macro editing mode. The available commands are 'l', to list the macro, 'i' to insert words, 'd' to delete words, and 'f' to find words. 'list' -- 'l' causes the words of the macro command stream to be listed one per line, and each is numbered. 'l 7' will cause the seventh macro word to be listed as well as the twenty following it. 'delete' -- 'd' must be specified with the number of the word that is to be deleted. If two numbers are entered, then all the words between the numbers will be deleted inclusively. 'insert' -- 'i' must be specified with the number of the word that the new steam is to follow, and must also be specified with the new steam. For example 'i 7 set tape 00 go' causes the words 'set tape 00 go' to be inserted as the eighth through the eleventh words. 'find' -- 'f' must be specified with the word to be found. If the word exists on the macro stream, it will be displayed along with some of the following words on the stream. Following entries of 'f' will locate other instances of the word. 6.12) 'run' Causes the macro to be executed. The macro is kept in memory until the next macro is entered. 6.13) 'say' or 'echo' Entering 'say' or 'echo' causes the next word or quoted string to be printed. For example: tm> echo "this is to be printed." this is to be printed. tm> 'say' or 'echo' are really only useful when used in macros. 6.14) 'help' When 'help' or '?' is entered at the tm> prompt, the user enters an interactive subprogram which allows him to get information about any TM command stream. the 'help' subprogram is roughly modeled after the VMS HELP utility. Entering 'help' or '?' at some of the other prompts, such as 'show what?', will allow the user to get help for the particular command which he has entered. When 'help' is entered at the tm> prompt, the user is shown a list of subtopics on which additional help is available. Entering the name of a subtopic will show the help. The subtopic names may NOT be abbreviated when they are entered. If subtopics exist for a subtopic, they are listed, and the user may look at them. If no further subtopics exist, the previous subtopic list is shown. The user may move back through the subtopic tree by entering a carriage return, which is also used as a way of leaving the help subprogram. If '?' is entered at the 'subtopic?' prompt, the current subtopic is displayed. ************************************************************************ TM version 1.3 D. Woodruff. December 19, 1998 Suffolk University, Math and Computer Science davewoodr@aol.com