TuME help

Contents

1. Introduction
2. General description
3. Program edition
4. Emulation
5. TML syntax
6. Limitations

Introduction

TuME stands for "Turing machine emulator" and this is what it is actually aimed to do. The Turing machine is a mathematical model of an idealized digital computer, described by English scientist Alan Turing in 1936. Almost every modern book about algorithm theory contains a thorough, formal description of the Turing machine, so here I will give only a brief overview, enough to start your experience with TuME. The Turing machine consists of an infinite length tape divided into cells, each containing a symbol from a finite set. The latter set is called the machine's external alphabet. One of its symbol is reserved and called empty symbol. There is also a head over the tape, able to move in both directions (namely right and left), read a symbol from cell below it and write a symbol to it. When head attempts to move behind the last cell of the tape, a new cell is attached to the corresponding end of the tape, and it is filled with an empty symbol. That is how tape becomes infinite. Machine always reside in a state from a finite state set and operates in a discrete time. There are two elements of state set with a special meaning: an initial and final states. The head's behavior is determined by a set of commands, each of which specifies the conditions that must be met at the time (i), and actions undertaken at (i+1). Previously mentioned initial state is supposed to appear only in the conditional part of the commands, whilst final state - only in the actions part. Other states can appear anywhere. Combination of an external alphabet, state set, tape with a word on it and a head located somewhere on it, and current machine state is called configuration. A set of commands is called the machine's program.
During the execution step (i), machine compares currently observed symbol on tape and current state with those of commands from its program. When a command matches, it is executed (which means, its actions are performed at the step (i+1)). Now current symbol/state are compared with the program data and the process continues... It halts due to one of the following conditions:

1. Current state is the final state. As long as it is not supposed to be met in conditional part of any command, it will always lead to the end of execution. Such end can be called "successful". Machine is then called applicable to the word on tape in initial configuration.
2. Current state is not the final state but, still, there is no command in program for machine's current configuration. It's a faulty situation and it means that program is incorrect. (The same is true for those programs that put machine in an infinite loop).

General description

TuME is a fast, easy to use tool for running Turing machine programs on multiple platforms, both desktop and mobile. Amongst its features are the following:

• Ability to run in automatic mode, - that is, once the program & configuration for machine are specified, emulator continuously executes commands until it meets a halt condition. You cannot intervene in machine execution in automatic mode, but You can suspend execution and continue in step-by-step mode. (However, this is an unusual case, because an average execution session finishes in a twinkle of an eye).
• Ability to run in step-by-step mode. In each step You can observe current configuration and command that will be picked from the program. Step size can vary from 1 to any number of machine time units. You can even change current symbol below the head and current machine state.
• Tracing of every step that is done (and interventions performed by user).
• A handy visualization of the tape.
• Ability to save/load Turing machine configuration & program description to/from plain text file (in TML format).
• Clear, error-prone configuration & program editor.

Program edition

Once You have loaded TuME, You can see two tabs at the top of main window, corresponding to "Emulation" and "Program" sections of the application. Select the "Program" tab. Now, at the left side of main window You should see three tabs relating to  “Sets”, “Commands” and “Tape” subsections of editor. Their content relates to edition of the corresponding aspects of machine. Note that, as far as word on tape and program commands depend on external alphabet and state set elements, this aspect should be edited before the other two.

Sets edition

Select the "Sets" subsection in the "Program" section, You will see two lists corresponding to state set and external alphabet edition. Below each of them there is a line of control elements. To add a new element of the set, write its name into text field below the corresponding list and press button. To rename the element, select it in the list, enter new name into text field and press button. Once the element is renamed in the sets editor, it will be renamed everywhere it is already in use. To remove last element, simply press button. You cannot delete an element that is in use somewhere in the program or tape, so alter or remove relative commands and tape cells first.
Note: restriction to delete only the last element might seem inconvenient, but remember, that You can achieve same effect by removing some elements from the tail of the list and then renaming the others.

Commands edition

On the "Commands" subsection You shall see a big table in the center and four buttons below it. The table describes program of the machine. Each row refers to a command. There are 6 columns in the table:

To edit a command, select the corresponding cell in the table and switch to edit mode (it is platform-dependent, e. g., pressing a space for desktop, pressing a command hard button on a Symbian device, etc.). From a drop-down list select an appropriate item and leave edit mode. To add a new row, press button. Newly added rows are highlighted with gray, so that You could easily identify them. Once such row has been altered, it is no longer highlighted. To remove a row, select a row You wish to remove (if You won't do, the last one will be removed) and press button.
Once You have finished the edition, press button to push the program into machine, or to erase the changes You have made and pull the program from machine to editor.
Note: unlike the other editor subsections, changes made in this one need to be explicitly confirmed by user. If You won't press button after edition is completed, machine will still run an obsolete set of commands (although changes won't be dropped until button is pressed).

Tape edition

Tape edition subsection allows You to specify initial word on tape and initial head position relative to the first symbol on tape. Word on tape is presented in the list at the left side of main window. Unlike tape view in the emulation section, symbols here are aligned vertically, leftmost being at the top of the list and rightmost – at the end. To add a new symbol to the end of the tape, select appropriate symbol from the drop-down list at the right part of the window, and press button. To change a symbol somewhere on the tape, select it in the list, select new symbol from drop-down list and press button. To remove a symbol from the tape, select it in the list and press button.
When You need to change initial offset of head from the beginning of the tape, enter it manually to the text field with a spinner at the right side of the window ("0" points to the first symbol, "1" to the second and so on). Or You can simply pick the symbol You wish head to point to, and press button.

Load and save current program and configuration

Machine configuration and program can be saved to and load from a single file. Current TuME version supports only text-based TML format, but there will be an option in the future to save/load binary files as well. TML files can be easily edited from the simplest external text editor, if You dislike the way TuME editor does.

• To load a machine (meant, to load its configuration and program) from a TML file, select menu item "File > Open" (marked with icon), select the file from Your local file system and open it. In case of error, current program and configuration remain intact. If an error occurs during TML parsing process, You will be given a message with the reason of failure and source file line number, where the error resides.
  Note, that TuME menu is platform-dependent, so "menu items" mentioned here relate to a common menu items for a desktop platform, or a soft button items for mobile platforms.
  
• To save the machine to a TML format file, select menu item "File > Save" (marked with icon). Current program and configuration will be saved in the current file, if any, otherwise You will be asked to select new file name and location. Menu item "File > Save as" works similar way, but it confirms You regardless of whether there is a current file or not. Every file that was recently successfully opened or saved is assumed current.
  Beware that application will always save current machine configuration, even if You have already initiated its execution. If You need to save the program in its initial configuration, do so right after edition is completed!
• To create an empty machine, select menu item "File > New" (marked with  icon). Empty machine has no commands in its program, empty symbol in external alphabet, initial and final states in state set and a word of a single empty symbol on tape. Right after TuME have been launched, its machine is also empty.
  

Once the machine have been saved or loaded, a corresponding restore point is created (or overwritten, if any). Each time the machine is reset, its configuration and program will be set to those from restore point.

Emulation

To begin emulation, go to "Emulation" section by selecting the corresponding tab at the top of main window. Now You shall see the emulation screen. Here is a list of components that You shall see here from top to bottom of the screen:

• tape view, displayed as a row of a few (typically 7) cells with an image (typically this: ) below the cell being currently observed by the head. Cells that are really in the tape are displayed white, cells that are potentially available, are displayed light gray (didn't You forget that the tape is infinite?). When in focus, tape view is navigable with the keyboard (or hard buttons):
  
  • right key scrolls view 1 cell rightwards;
  • left key scrolls view 1 cell leftwards;
  • up key scrolls view until the rightmost real cell appears at the right side of the view;
  • down key scrolls view until the leftmost real cell appears at the left side of the view;
  • escape (or clear for mobiles) centers the view around the cell currently being observed by the machine's head.
• navigation pane with the following controls:
  
  • scrolls view until the leftmost real cell appears at the left side of the view;
  • scrolls view 1 cell leftwards;
    
  • centers the view around the cell currently being observed by the machine's head;
  • (opt.) reverts the machine state to the most recent restore point;
  • (opt.) when automatic execution process is in progress, pauses it, switching to the step-by-step execution mode;
  • (opt.) starts execution in automatic mode;
  • (opt.) executes machine for the one step (step is not the same as machine time unit, see below);
  • number input field sets the number of machine time units corresponding to one step (typically 1);
  • scrolls view 1 cell rightwards;
  • scrolls view until the rightmost real cell appears at the right side of the view.
• monitoring row, displaying (from left to right) current machine state, symbol on tape, observed by the head, and a command that matches their combination. This row is used mainly during execution in step-by-step mode. Current state and symbol are editable and displayed as currently selected values in drop-down lists. You can change them by choosing another values there. Such changes affect only current execution session and are not saved when the configuration and program are saved or when reset is performed.
• execution trace, a read-only table with a respective label at the top. Each of its rows relates to a command executed by the machine. Commands are show in chronological order with the first executed command at the top of the table. If a sequence of a few similar commands appears in a trace, they are jammed into two rows: the first displays the command itself, and the second has all of its columns set to "..." (ellipsis), assuming "and so on". When at the machine time unit, corresponding to some row, there was a manual change of current state or symbol observed by the head, such row is highlighted with red color ( like this ).
  Here is a detailed description of the table columns:
  
  1. Time – a machine time unit, at which a commands was executed.
     
  2. State – in this state machine resided at the Time time unit.
     
  3. Symbol – this symbol was observed by the machine's head at the Time time unit.
     
  4. Chosen command – the command that was executed, because it matched a combination of State and Symbol.
  Note, that You can stop tracing of the the execution by checking "Emulation > Disable log" (icon: ) menu item. If You do, execution trace will disappear from the screen.
• status bar, although is not part of emulation screen, is especially important here. It contains three (for desktops) or two (for mobile platforms) sections, from left to right:
  
  • Current time, in machine time units. After application is loaded or reset performed, displays zero value. When machine is executed in step-by-step mode, data visible in the monitoring row relates to the machine time displayed here. After machine has completed execution in automatic mode, displays (last command execution time + 1).
  • Machine execution status (desktop TuME versions only). Displays the reason of the last machine execution termination. On mobile platforms, this kind of information is placed in Current status section, along common application notifications.
  • Current status. Displays various application-wide information: errors, notifications, etc. On mobile platforms it also shows execution status messages, as execution events happen, prefixed with "Exec:". As far as mobile screen is small, some messages do not fit in this section. For this reason, on mobile platforms it is performed as button. Press this button to see the whole message in a separate dialog box.

Execution control is based on the following menu items in "Emulation" menu:

• "Reset" – reverts the machine state to the most recent restore point.
• "Start" – resets the machine (see above) and begins its executions in automatic mode.
  
• "Pause" – interrupts hanged machine execution, for example, if it entered an infinite loop.
• "Step forward" – executes machine for a specified count of time units from the current configuration.
  

If TuME is running on desktop platform, these items have equivalent buttons in navigation pane.

Running in automatic mode

Running the machine in automatic mode allows You to test quickly, whether it is applicable to the word on tape in initial configuration, and acquire results of its execution.

1. Ensure the machine is properly configured, program is entered and tape contains proper word.
   
2. Activate menu item "Emulation > Start" (or press button, if present). During the execution, most of the application functions are disabled. Execution will stop if there is no matching commands in the program or if execution time limit reached ^{this feature is not yet implemented}.
3. If execution hangs (maybe, same command is being chosen infinitely), You can always stop it by activating menu item "Emulation > Pause" (or pressing button, if present).

Execution sessions that are finished due to appearance of the final state in machine configuration are the only that considered successful. Information in the status bar can help You to determine execution status. If execution trace was not disabled at the moment of execution start, it will be available in the emulation screen after the execution is finished.

Running in step-by-step mode

In step-by-step mode You can manually trace the execution, even if it is disabled. Be aware that You cannot enter this mode explicitly – machine always resides in it, except for the periods of automatic execution. Even when the machine is empty, it stays in step-by-step execution mode. There are two main actions to control execution  in this mode: step forward (menu item "Emulation > Step forward") and reset ("Emulation > Reset"). To execute machine in this mode, do the following:

1. Optionally, change a step size (in machine time units) in the "Stride size for step" number input field at the navigation pane in "Emulation" section, if You are not satisfied with the default one, which is 1.
2. Optionally, change current machine state and / or currently observed symbol on tape in the monitoring row.
3. Activate "Emulation > Step forward" menu item (or press button, if present) one or more times. If You have already debugged programs, it might resemble You "Step over" debugger command.
4. Look at the monitoring row, execution trace (if not disabled) and status bar to see the results.

These actions can be undertaken continuously, until You find that the program execution finished.
When machine execution finished, You can reset it to the most recent restore point by activating "Emulation > Reset" menu item (or pressing button, if present).

TML syntax

TML stands for Turing machine Markup Language. It has nothing in common with the SGML and its derivatives. It is used for textual representation of TuME configuration and program, and is not knows to be used elsewhere.
The TML file consists of three types of lexical elements:

• Directives, that instruct TuME to set a particular machine property to a particular value. Their syntax is simple:
  <directive> ::= <directive-name> ":" <directive-value>
  <directive-name> ::= states | alphabet | state0 | state1 | empty | tape | offset
  <directive-value> ::= <single-value> | <directive-value> "," <single-value>
  <single-value> is an arbitrary string of alphanumeric characters. Spaces withing strings allowed for symbol values (symbol set elements, tape symbols) but prohibited for state values.
  ":" and "," symbols allow arbitrary number of spaces or tabulations around them.
  
• Commands, that constitute machine's program. Their syntax is:
  <command> ::= <condition> "->" <action>
  <condition> ::= <single-state-value> "(" <single-symbol-value> ")"
  <action> ::= "(" <single-symbol-value> ")" <movement-dir> "." <single-state-value>
  <movement-dir> ::= L | S | R
  <condition> is a combination of machine current state and observed symbol on the tape that are used to test the command for its applicability.
  <action> describes changes in machine that will come to power in case this command is selected.
  <single-state-value> is an arbitrary string of alphanumeric characters without spaces.
  <single-symbol-value> is an arbitrary string of alphanumeric characters.
  <movement-dir> value describes movement direction of the head: left ("L"), right ("R") or stand still ("S").
  "->" symbol allow arbitrary number of spaces or tabulations around it.
• Comments, that allow author to leave notes in code.
  <comment> ::= "#" <text-line>
  <text-line> is an arbitrary text ended with a newline symbol.

Here is a sample TML code that, when executed, replaces all "0" symbols with "1" from the beginning of the tape until the first "1" is under machine's head:

Limitations

As it was written in introduction, Turing machine operates with an infinite tape. It is also well-known that computers operate with finite numbers located in finite memory. This limitation is especially sensible for mobile devices. TuME tape size is limited by amount of memory available for a user application on the target platform. Also, as far as TuME counts machine time and traces execution process, execution time is limited by the value 2⁶⁴. It's a reasonable high value, but it's a divergence from formal definition given by A. Turing. That's why I'm not sure the application would fit for all tasks that engage Turing machines.

That's all for now. Your bug reports about TuME are welcome (see below).

TuME v1.0 documentation. Copyright © 2011, Dmitriev K. S.
Send Your notes and bug reports to kulhatzkergmail.com.