Turing for the PalmPilot

Turing is my first application for the PalmPilot. It was written with Pila and PilRC, and debugged with Copilot. Turing requires PalmOS 2.0+ to run. Installing it on earlier versions of the OS won’t crash your Pilot though, but you won’t be able to run the program. This is because I use some API calls related to scrollbars that are not present in earlier versions.

Disclaimer

Permission to use, copy, modify, and distribute this software and its documentation for any purpose, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and this paragraph and the following two paragraphs appear in all copies.

IN NO EVENT SHALL THE AUTHOR BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE AUTHOR HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE AUTHOR SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE AUTHOR HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Features

Turing is a 2D implementation of Alan Turing’s machine. It differs with the original concept in the facts that there are two dimensions instead of one, and of course the space where the machine operates is finite. You can get more information about Alan Turing’s works here. My implementation differs from Turmite (by Ken Krugler) in its purpose: Ken’s can only read two symbols in the machine space (white or black), and generates graphic patterns in a larger space. Mine uses a smaller space, but can read many more symbols.

The application supports PalmOS’s find feature. You can lookup a record by its label only.

Turing uses a database in which it can store multiple machine sets. A set has a label, an initial machine space, state and cursor position, and an instruction set that operates upon the machine space (Ken’s explanations are much better than mine, I’m afraid).

Of course, if you feel some feature is missing or should be improved/redesigned, please let me know.

How to use Turing

	When Turing is launched, it displays this form: It is a list of all records that were found in the database. A new record can be created with the " new " button. An existing record can be selected by tapping it. In both cases, you will be taken to the main form, where the Turing machine can be operated.
	There is also a menu for this form. From this menu the preferences form can be invoked:
	When ‘execution updates display’ is checked, the main form will update the machine space after each step of the execution. Of course it slows down the execution a bit. If not checked, the whole form is redrawn when execution stops. It is possible to remove, save or restore the current record from the database (in the main form). For each checked related box, an alert dialog is popped up. When the cursor moves towards a border of the machine space, it is possible either to enable or forbid cursor wrapping. The frame rate is not very accurate. In, fact, this is used to compute a delay to wait for an event in the main loop. If none is received, a step of the engine is performed. Not all values are possible (the preferences do not store this value, but the integer part of 100 / <value>. Values above 50 are not allowed, and I think that values above 10 won’t change the execution speed very much.
	Once a record is selected, the main form is opened to edit it: The upper-right circle is in fact a button that closes the form (returns to the list of machines). If the machine space was hand-modified, a save popup dialog may appear, if the preferences require a save confirmation. The top-left field is the name of the current record. You can change it at will (duplicate names are allowed). The top-right field displays the current state of the machine. It can be modified when the program executes, or you can modify it manually to set up the machine before it is run. The right field contains the instructions of the machine. Each instruction is a 5 characters string. When the instruction set is not syntaxically correct, the lower-left corner displays this symbol: . The instructions are correct when each line contains exactly 5 symbols, and the last line does not end with a carriage return. This means that the cursor in the field can go no farther than after the last character of the last line (not on the following line). Note that this field directly edits the current record : you cannot restore the original instruction set if you change it. This is not true for the machine status (that is, cursor + state + space). This means that execution does not alter the record. If at some point of the execution, no instruction matches the current state/symbol combination, it is stopped. Each line of the instruction set is interpreted as follows : If my state is the first symbol, and I read the second symbol under the cursor, change my state to third symbol, write fourth symbol under cursor, then move cursor in the direction givn by the fith symbol. The four first symbols can be anything printable, and the last one will cause a displacement only if one of UDLR, standing respectively for up down, left or right (case is insensitive). The large bordered area is a representation of the machine space. It is of course finite, and does not wrap (a left move on the left border will do nothing). The highlighted symbol is the current position of the cursor. When no field has the focus, any entered character will replace the symbol under the cursor. It is thus possible to edit your own initial machine space. The menu also offers a command to fill the machine space with the symbol unde the cursor, to reset it easily. Note that the current record will not change until you save your changes (use the save command in the menu). From left to right, the bottom buttons run, stop and step the machine. The little field contains the step count (1 is the default is the field is empty). When the machine is being run, the lower-left area displays a busy symbol: . It is of course impossible to run or step the machine when the instruction set is incorrect. In step mode, the display is always updated after each step. The run mode updates the display only if required. Leaving the run mode will cause the whole form to be redrawn.

The actions menu offers the following self-evident commands, with associated confirmation dialogs:

‘Duplicate’ will create a copy of the current record before recording the current machine space. ‘Archive’ will remove the record from the database, but a copy will be archived on the PC by the next HotSync.

What can be done with Turing

Here are some examples of what you can do with Turing:

Add/substract two integers in various notations (binary, decimal, etc.)

Find the exit of a labyrinth

An interesting (and opened if I remember well) problem is to find the machine with a finite number of states that will fill the most positions in the machine space, and then stop. (It is easy to fill an infinite number of positions with a one-state machine). Of course it is difficult to try in a finite space…

Application Changes

v1.0 beta is the first public release. It is also the first full-featured version that I dared install on my device!

Known bugs / missing features

I got once a "Overlocked field" fatal alert, but could not reproduce it. In any case this sould not cause any data loss, because a soft reset will restore everything.

When invoking menu commands through shortcuts, the invoked menu entry name ()that is displayed does not disappear after a while. I don’t know if this disappearance is subject to a PalmOS message, and did not find any information about it in the USR programming guides.

The indexes displayed in the main form may not be consecutive (they are the indexes of the valid records – archived ones will not appear in the list, but their indexes will be skipped). The main list is not yet sorted alphabetically.