Written by Alvaro Gerardo Suarez.

Last week I was reading "ALGORITHMS AND AUTOMATIC
COMPUTING MACHINES" BY B.A. TRAKHTENBROT

In this book there are several chapters about Turing
Machines.

I needed a simulator of a turing machine capable of
running the examples in the book.

So , I went to my computer and wrote this simulator.

               
Version 0.2 -> Date of first public release: 2006/06/30
Version 0.3 -> 2006/07/01

Programs have TUR extension.

Program structure:

Init_state
Init_char
End_State
End_char
Movement : R or > is move to Right
           L or < is move to Left 
           S is stand on the same cell
           H or ! is Halt program

     

Underscore character is the blank character.

In order to run turing.exe
you need the Visual Fox Pro 5 Runtime installed previously.

This runtime could be found at my site:
http://www.geocities.com/algesuar


NOTES ABOUT THE EXAMPLE PROGRAMS
--------------------------------
Running palindromes.tur


In the main window:

Click [Load]
Write into the box : palindrome
Click [Load]

Be sure that initial position is 1 and current state is 1.


Write in the box "Initial characters" the following text:

_AABBBAA_


(Underscore is the space character used by the machine)

Click [Run].

Click [View Tape]


The answer "YES" is written on the tape.

So the text entered is a palindrome!.

Click [Exit]


The boxes initial time and final time are showing the time at the start
and the time at the end of the program execution.


Another example:


Put 1 into the box "Initial position".
Put 1 into the box "Current State"

Click [View Tape]
Click [Clear Tape]
Click [Exit]

Write _AABB_ into the box "Initial characters"

Click [Run]

Click [View Tape]

The answer "NO" is written on the tape. (Positions 2 and 3)

Then, the string written is not a palindrome. !


CONVERTTODECIMAL.TUR
--------------------

This program counts the characters | located at right of the
character 0 and change this number by a number with the total
of |.

If the number is not 0 then adds the number of | to the
number.


Example: If you have 0||||_ you will obtain 4 _ _ _ _


If you have another number, for example:

390||||||_  you will obtain 396 _ _ _ _ _ _

In this case the number of | is added to 390.


The initial state for the turing machine is q2 and the initial position
is at right of the last | on a underscore character.


In the simulator

1. Clear the tape

Click [ViewTape] [ClearTape] [Exit]

2. Load the program

Click [Load] , write "converttodecimal" [Load]


3. Write in the box initial characters: 0|||||||_

4. Write in the box initial position: 9

5. Write in the box current state: q2

6. Click [Run]

7. You see the message: "Program executed"

8. Click any key

9. Click [ViewTape]

10. The answer: 7 is shown on the tape.



SUBTRACTER.TUR
--------------

If you have two numbers written as a sequence of ones
in the form:

Example: 111111-1111=


(6-4=)

the program executes the operation and the answer
will be:


11



Program execution:

1. Load Subtracter


Click [Load]
Write "subtracter" and click [Load]

2. Clear the tape

Click [ViewTape]
Click [ClearTape]
Click [Exit]

3. Write initial characters:

Write: 111111-1111=


4. Be sure that

Initial position is 1
Current state is 1


5. Click [Run]


6. Click [ViewTape]


The answer shown is 11.


BUSYBEAVER COMPETITION
----------------------
The treat is to find a program for a turing
machine that write the max number of ones
on the tape.

The program must have max 5 states.

At initial state the tape must be cleared.

Infinite loops into the program are not
allowed.

Exist a competition for the best program.


BUSYBEAVER5-501.TUR
-------------------

The goal of this program is to write the number 1
501 times on the tape using a 5 state program
for a turing machine without the machine enters
into a "infinite loop."


At the beginning the tape must be cleared.


This program was found by Uwe Schult in January 1983.

Program execution:

1. Load Busybeaver5-501


Click [Load]
Write "busybeaver5-501" and click [Load]

2. Clear the tape

Click [ViewTape]
Click [ClearTape]
Click [Exit]

4. Be sure that the tape size is >=10000 cells

5. Write 5000 in the box "initial position":

6. Be sure that the current state is 1

7.  Click [Run]

You see that:

The program was executed by the simulator in 4 seconds

The end position reached was 5656 on the tape.

Non blank characters (ones) =501

Steps executed = 134493.

(In each step the complete program is searched for a match
in the character on the tape and the current state with the 
character at init_char and the state at init_state )

8. Click [View Tape] in order to view the "ones"


BUSYBEAVER5-1915.TUR
--------------------

This program writes 1915 ones on the tape before halt.

Found by George Uhing in December 1984.


Beginning at initial position = 5000 and current state=1

with the tape cleared.


Execution time in the simulator: 32 seconds

End position reached: 4997

Non blank characters ("ones") written on the tape: 1915

Steps: 2267985


BUSYBEAVER5-4098.TUR
--------------------

This program was found by Heiner Marxen and Juerguen
Buntrock in September 1989.


In order to execute this program change the tape size
to 100000.

The program writes 4098 "ones" on the tape


Steps: 47176870.

Aprox. execution time: 5 minutes.

Clear the tape first. Then, put initial position equal
 to 50000 and current state =1.



