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


                  Visitors : 14 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