Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page
Search the Web


                  Visitors : 6521 since Dec 19, 2003

                                   
        [ Last Modification : 2003/12/19]
        ---------------------------------
  Here is C++ Simulator of a Universal Turing Machine (UTM).
  The algorithm has been written by Alex Vinokur.
  Programming Language : C++.
  Any and all comments would be appreciated.
       Message Board 

        Alex Vinokur
        -----------------------------------
        alexvn@connect.to
        http://up.to/alexvn
        -----------------------------------
Also
C++ Simulator of a Turing Machine
A Turing Machine with faults, failures and recovery
C++ Simulator of a Post Machine
  Content.
  1. Algorithm
  2. Classes
  3. Program Files
  4. Demo Program
  5. Compiling
  6. Running
  7. Download

====================================================
=================== 1. Algorithm ===================
                               
The program simulates a Universal Turing Machine (UTM).

  The UTM used is a three-tape Turing Machine:
  * Tape#0 contains transition table and initial instantaneous description
    of a Particular Turing Machine (TM);
  * Tape#1 and Tape#2 are working UTM-tapes.

  The UTM can simulate the behavior of a Multitape TM.

  Detailed log file is generated.
  Resources used (input size, output size, UTM-space, UTM-time) are computed as well.

  The package consists of two executable files :
  * t2u - compiler TM-to-UTM 
    which translates description and input of TM to UTM-language;
  * utm - the simulator itself.


  Testsuites. Two Turing Machines are used to create inputs for UTM.
  Each of them is an addition program which adds two numbers:
  * TM-1 is one-tape TM,
  * TM-2 is two-tape TM.


====================================================

====================================================
================ 2. List Of Classes ================

Main classes used in the algorithm are as following :
  1. CurSituation
  2. NextSituation
  3. Tape
  4. UniversalTuringMachine
  5. Run
  6. TM-to-UTM-Compiler
====================================================

==========================================================================
============================= 3. Program Files ===========================

The package contains the following files :
  1. license.gpl (GNU GENERAL PUBLIC LICENSE)
  2. readme --- Sources ---
  3. version.h Version Info (Declaration)
  4. macro.h Various Macro
  5. common.h Common Function etc (Declaration)
  6. service.h Auxiliary Classes/Functions (Declaration)
  7. defs.h Common Definitions
  8. tape.h Class Tape (Definition)
  9. rules.h Classes CurSituation & NextSituation (Definition)
  10. turing-u.h Class UniversalTuringMachine (Definition)
  11. run.h Class Run (Definition)
  12. codes.h Coding Related Functions (Declaration)
  13. comp-t2u.h Class TM_to_UTM_Compiler (Definition)
  14. version.cpp Version Info (Definition)
  15. common.cpp Common Function etc (Implementation)
  16. service.cpp Auxiliary Classes/Functions (Implementation)
  17. tape.cpp Class Tape (Implementation)
  18. rules.cpp Classes CurSituation & NextSituation (Implementation)
  19. turing-u.cpp Class UniversalTuringMachine (Implementation)
  20. run.cpp Class Run (Implementation)
  21. codes.cpp Coding Related Functions (Implementation)
  22. comp-t2u.cpp Class TM_to_UTM_Compiler (Implementation)
  23. main-t2u.cpp Main Program for Conversion TM-to-UTM
  24. main-utm.cpp Main Program for UTM Simulator --- Data Files ---
  25. states.utm UTM States
  26. symbols.utm UTM Symbols
  27. rules.utm UTM Rules (Transition Table) --- Makefile ---
  28. Makefile --- Demo Input Data Files --- Various demo data files.
====================================================

==========================================================================
============================= 4. Demo Programs ===========================

Two (ordinary) Turing Machines are used 
  to create inputs for Universal Turing Machine.
Each of them is an addition program which adds two numbers.

A number 'n' is represented by n 1-s.
Sample :
  5 is represented as  1 1 1 1 1
  3 is represented as  1 1 1

Note. Blank symbol is 'e'.


1. An addition program-1 (Turing Machine No.1).
   ============================================

   Number of TM-tapes used : 1

   Input  : Two numbers separated by symbol '*'
   Output : Resulting number without '*'

   Sample.
     Input
     * TM-Tape#0 :  1 1 1 * 1 1

     Output
     * TM-Tape#0 :  1 1 1 1 1


   Testsuites (input words) :
   -------------------------- 
   Test-1.1 : 
     * TM-Tape#0 :  [1] 1 1 * 1 1
   
   Test-1.2 : 
     * TM-Tape#0 :  [e] e 1 1 1 * 1 1

   Test-1.3 : 
     * TM-Tape#0 :  e [e] 1 1 1 * 1 1

   Test-1.4 : 
     * TM-Tape#0 :  e e [1] 1 1 * 1 1

   Test-1.5 : 
     * TM-Tape#0 :  [*] 1 1 1 1



2. An addition program-2 (Turing Machine No.2).
   ============================================

   Number of TM-tapes used : 2

   Input  : Two numbers separated by symbol '*' on the input tape
   Output : Resulting number on the output tape

   Sample.
     Input
     * TM-Tape#0 :  1 1 1 * 1 1
     * TM-Tape#1 is empty

     Output
     * TM-Tape#0 :  1 1 1 * 1 1
     * TM-Tape#1 :  1 1 1 1 1


   Testsuites (input words) :
   -------------------------- 
   Test-2.1 : 
     * TM-Tape#0 :  [1] 1 1 * 1 1
     * TM-Tape#1 :  [e]

   Test-2.2 : 
     * TM-Tape#0 :  [e] e 1 1 1 * 1 1
     * TM-Tape#1 :  [e]

   Test-2.3 : 
     * TM-Tape#0 :  e [e] 1 1 1 * 1 1
     * TM-Tape#1 :  [e]

   Test-2.4 : 
     * TM-Tape#0 :  e e [1] 1 1 * 1 1
     * TM-Tape#1 :  [e]

   Test-2.5 : 
     * TM-Tape#0 :  [1] 1 1 * 1 1 e e
     * TM-Tape#1 :  [e]

   Test-2.6 : 
     * TM-Tape#0 :  [1] e 1 1 * 1 1
     * TM-Tape#1 :  [e]
 
====================================================

====================================================
==================== 5. Compiling ==================
//#########################################################
//------------------- System & Compiler  ------------------
Windows 2000
CYGWIN
GNU gcc/g++ version 3.3.1
GNU Make version 3.80
//-------------------- Compiling : BEGIN ------------------
% make
  Two executable files are created:
  * t2u - TM-to-UTM Compiler,
  * utm - Simulator itself. 

//-------------------- Compiling : END --------------------

====================================================
===================== 6. Running ===================
//#########################################################
//-------------------- Running : BEGIN --------------------

% t2u foo.tm foo_in.tm
  * foo.tm     is file name which contains transition table of TM
  * foo_in.tm  is file name which contains input word(s) of TM
  t2u generates several output files including foo_in.umi 
  which is input of the utm executable.
  
% utm foo_in.umi

//-------------------- Running : END ----------------------

====================================================
===================== 7. Download ==================
//#########################################################

http://sourceforge.net/projects/turing-machine/

http://alexvn.freeservers.com/s1/utm.zip