![[The TCELL Turing Machine compiler]](graphics/compiler.gif)
This document is intended to provide basic instructions for users who are new to the TCELL software package. New TCELL users should begin by creating a high-level "source code" file for use with the TCELL compiler, as described in Section 1. This source file can then be used with the Turing Machine compiler (Section 2), which will generate an output file representing an equivalent Turing Machine. This output file can then be used with both the transition table generator (Section 3) and the viewer (Section 4). The remaining sections of this document describe each of these steps in the order that they should be performed.
I have made every effort to make this guide a comprehensive one, but there are bound to be omissions. If you find that you have a question that this guide does not answer to your satisfaction, please contact the author, Michael Tashbook, at mtashbook@acm.org.
For general information and news regarding the TCELL software package, please visit the TCELL home page.
The latest version of this document can always be found online at the following URL:
http://www.cs.virginia.edu/~mst2f/tcellguide.html.
TCELL implements a simple "programming language" that can be used to specify the computation(s) that a given Turing Machine should perform. This language can be used to write "source code" files that can be submitted to the TCELL compiler, which will then generate a transition table for the equivalent Turing Machine. At present, this language supports integer arithmetic operations, assignment statements, conditional statements, and loops.
A TCELL source code file is a plain text file that specifies one or more operations for a TCELL Turing Machine to perform. A TCELL source code file contains one or more program statements. There are four kinds of statements: arithmetic statements, assignment statements, loops, and conditional statements. Each statement must be completed within a single line; it cannot be spread across multiple lines. For example,
I = K / 3
would be valid, because it fits on a single line. However,
M =
2 *
J
is not correct, because it is divided across three lines. Whitespace is also very important in TCELL source code files. Every token (variable, operator, or keyword) in a statement must be separated from the others by at least one space or tab.
Source code files can also contain comments. A TCELL comment begins with a hash mark (#) and extends until the end of the current line. Comments can begin at any point in a line. For example:
I = J + 3 # Add 3 to J and store the sum in variable I
TCELL source programs can use five variables, named I, J, K, L, and M. These variables correspond to the five variable tapes in a TCELL Turing Machine. TCELL Turing Machines also contain two temporary tapes, which may be used for "scratch space" during computations; these are not available for use by users and programmers.
A TCELL program should assign values to variables before using them. By default, all variables are assigned the value zero. This value can be changed by an explicit assignment. Starting values for Turing Machine variables can also be assigned by using the TCELL viewer application (Section 4) to edit the appropriate tapes before executing the Turing Machine's program.
TCELL programs are limited to working with non-negative integers. Subtraction is bounded by zero. That is, subtracting a large number from a smaller number will result in zero, not a negative answer.
TCELL supports five basic arithmetic operations: addition, subtraction, multiplication (*), division (/), and modulus/remainder (%). One variable's value can be assigned to another variable, and a numeric constant can be assigned to a variable. Every assignment statement has exactly three tokens, and takes the form:
<destination tape> = <source>
The source can be a numeric constant, or it can be the name of another variable tape.
Every arithmetic statement has exactly five tokens, and has the following form:
<destination tape> = <operand 1> <operator> <operand 2>
Each operand can be either a variable, or a numeric constant. The operator can be any one of the five arithmetic operations listed above.
For example, a TCELL source program might contain the statements:
I = 2 # Assign the constant 2 to variable I
J = I # Copy the value of variable I to variable J
K = I + J # Add the values of variables I and J, and store them in K
TCELL loops begin with a REPEAT statement. The
REPEAT keyword is followed by an inequality representing the
loop condition. The keyword END is used to indicate the end of
the loop body. For example:
REPEAT I < J
I = I + 1
K = 3 - I
END
In this loop, the two arithmetic statements will be repeated as long as the value of variable I is less than that of variable J. As with most programming languages, it is possible to specify a loop whose loop condition will always be true. This will produce an infinite loop when the Turing Machine program is run.
TCELL conditional statements consist of an IF clause, followed by
an optional ELSE clause. They are always terminated by the
ENDIF keyword, which is used at the end of the ELSE
clause (or the end of the IF clause, for a conditional that does
not contain an ELSE clause). The test condition takes the form of
an inequality, just like a REPEAT loop. Conditionals take the form:
IF test-condition
{one or more statements to be performed if the condition is true}
ELSE
{one or statements to be performed otherwise}
ENDIF
For example:
# IF statement # IF-ELSE statement
IF J < M IF M < J
L = 5 K = 3
ENDIF ELSE
J = 4
ENDIF
The example on the left compares the values of M and J. If M is smaller than J, then
the Turing Machine will store the value 3 on tape K. Otherwise, it will store the
value 4 on tape J. The example on the right does not have an ELSE clause.
If the value of variable J is not less than that of M, the statement contained in the
IF clause will be ignored, and the Turing Machine will do nothing.
Loops and conditional statements can be nested. For example, it is possible to invoke a loop within one of the clauses of a conditional statement. At present, the TCELL compiler only supports five levels of nesting. Attempting to exceed this limit will produce an error message and will cause the compiler to abort processing the source code file.
The TCELL Turing Machine compiler has a simple, somewhat spartan command-line
interface. When you execute the application, you will be prompted for the name
of a TCELL source code file. Type in the filename, and press
<RETURN>. If the program cannot locate a file with that
name in the current directory, you will be prompted to enter a different
filename. This input file will not be modified in any way.
When you have specified a valid input filename, you will then be asked to provide a name for the output file that the compiler will generate. If you do not enter a name for this file, the program will use the default filename "out.txt" for the output file. (WARNING: The program will automatically overwrite any existing file with the same name, so you will need to exercise care). The compiler will not allow you to enter the same name for both the source and destination files.
The compiler will then proceed to generate a Turing Machine based on the source code that you have provided. An encoded description of this Turing Machine will be stored in a text file with the filename that you specified earlier. As it works, the compiler will print messages to the screen from time to time, informing you of its progress.
If the program encounters an error in the source code file, it will abort compilation and terminate with an error message. When this happens, you may be left with a partial output file. Do not attempt to use this file in the viewer application (Section 4); you may get unexpected or incorrect results. Instead, you should delete any output files that result from aborted compilation. Alternately, you may specify the same filename when you fix and recompile your source code; when you do so, the compiler will automatically overwrite the erroneous partial output file.
The TCELL Turing Machine compiler is shown below.
The TCELL transition table generator, like the TCELL compiler, uses a simple command-line interface. Upon starting the program, you will be prompted for the name of a TCELL output file. Type in the filename, and press <RETURN>. If the program cannot locate a file with that name in the current directory, you will be prompted to enter a different filename. The transition table generator will not modify the original input file in any way.
When you have specified a valid input file, you will then be asked to provide a name for the new transition table. If you do not enter a name for this file, the program will use the default filename "table.txt" for this output file. The program will automatically overwrite any existing file with the same name, so you will need to exercise care. As with the compiler (Section 2), you cannot enter the same name for both the source and destination files.
This program will not display anything more to the screen, with the exception of a few messages reporting its progress. When the program terminates, the transition table will be stored in a text file with the filename that you specified. The TCELL transition table generator application is shown below.
![[The TCELL Transition Table Generator]](graphics/tablegen.gif)
The TCELL viewer is a standalone Java application that allows users to trace the execution of Turing Machines generated by the TCELL compiler. As the Turing Machine program executes, the program will update its display of the seven variable and temporary tapes and highlight the currently-active tape in blue. Square brackets are used to indicate the location of the tape head on each tape. The viewer interface also shows the transition table entries for the current state, along with a counter that displays the number of program steps that have been executed so far.
The "Load New TM" button can be used at any time to load a new TCELL Turing Machine description into the viewer. Loading a new Turing Machine will clear the contents of the Turing Machine tapes. At this point, you can use the "Advance TM" button to begin executing the Turing Machine program, or you can enter starting values for any or all of the Turing Machine variable tapes (those labeled I, J, K, L, or M).
Each Turing Machine tape can store up to 50 characters. The first (leftmost) character on a tape must be a HOME symbol (#). The final character on a tape must be an END symbol ($). In between, there may be any number of value symbols (symbolized by X). Before executing a Turing Machine program, the viewer application checks the contents of its tapes. Illegal values (i.e., any symbols other than the three described above) are discarded, and the remaining tape contents are stored in memory as the original tape contents.
The button labeled "Advance TM" can be used to execute the current Turing Machine program. Clicking on this button will advance the program by the number of steps indicated in the text box labeled "# of TM steps to advance." For lengthy computations, you may wish to set this value to a high number, like 50 or 100. Once you begin to execute a Turing Machine program, you will not be able to edit the values stored on the tapes. If you wish to change the tape contents, you will need to reset the Turing Machine using the "Reset TM" button, and then execute the Turing Machine program again with your new tape values.
As the Turing Machine program executes, the viewer will display pertinent information regarding its status. This information includes the current content of all seven tapes, the total number of program steps performed, the current state and input symbol, and the next Turing Machine state. The currently active tape will be highlighted in blue. The viewer will also display the transition table entries for the current Turing Machine state, along with the steps that will be performed next. The TCELL viewer application is shown below.
![[The TCELL viewer application]](graphics/viewer.gif)
The current version of the TCELL viewer application does not provide a "history" feature. This means that program execution is one-way; there is no way to backtrack to review the execution of previous program steps. In addition, the length of each Turing Machine tape is limited to 50 characters. This significantly limits the size of the computations that can be performed using the viewer. Both of these issues will be fixed in a future version of the viewer application.
As a Turing Machine program executes, the viewer application will highlight the tape that is currently active. Sometimes, when the viewer is set to advance by several program steps at a time, the current Turing Machine tape will not be colored properly. I am still investigating solutions for this problem, but I do not know exactly when it will be fixed.
Finally, the current design of the TCELL software package requires the user to work with three separate applications. In the near future, the software will be rewritten as a single, integrated Java application. This will provide a consistent user interface for all three programs and eliminate the need to recompile the compiler and transition table generator for multiple platforms.
TCELL is © 2000 by Michael S. Tashbook.
Back to the TCELL Home Page | Back to my home page
This document was last updated on February 28, 2004 by Michael S. Tashbook (mtashbook@acm.org).