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


                  Visitors : 4083 since Mar 13, 2003

                                   
        [ Last Modification : 2004/10/26]
        ---------------------------------
  Here is Turing Machine with faults, failures and recovery.
  http://alexvn.freeservers.com/s1/turing-s.zip
  http://sourceforge.net/project/showfiles.php?group_id=79519&package_id=85144
  The algorithm has been written by Alex Vinokur.
  Programming Language : C++.
  Any and all comments would be appreciated.


        E-print
        -----------------------------------
        alexvn@connect.to
        http://up.to/alexvn
        http://alexvn.freeservers.com/s1/turing-s.html
        -----------------------------------

  Content.
  1. Informal Definition
  2. Formalized Definition (Fragments)
  3. C++ Simulator
  4. Download

====================================================
============== 1. Informal definition ==============
                               
  In contrast to practical situation an ordinary Turing Machine never fails. 
  Here is brief description of 
  * Turing Machine with faults, failures and recovery
    and
  * its C++ Simulator (Beta version).

  Expanded Turing Machine (ETM) is (weakly) non-deterministic Turing Machine consisting of :
    a) five semi-infinite (to the right) tapes
       - Master Tape,
       - Synchro Tape,
       - Backup Tape,
       - Backup Synchro Tape,
       - User (Tester) Tape;
    b) four controlling components (sets of rules)
       - Program, 
       - Daemon,
       - Apparatus,
       - User.
  Only daemon has non-deterministic behavior.

  
      1.1. Tapes, alphabets
      ---------------------
  Master Tape corresponds to the tape of ordinary deterministic Turing Machine.
  Head of Synchro Tape is synchronized with head of Master Tape.
  Backup Tape is used to back Master Tape data up.
  Backup Synchro Tape is used to back Synchro Tape data up.
  User Tape is used to perform pure/ideal computation (without faults and failures).

  Master Tape, Backup Tape, User Tape are using the same (user-defined) alphabet.
  Synchro Tape, Backup Synchro Tape are using the same special (embedded, user-independent) alphabet.


      1.2. Controlling components, states and rules
      ---------------------------------------------
        1.2.1. States
        ^^^^^^^^^^^^^
  Program contains :
    - user-defined states (initial, internal and halting states), 
    - user-required check-point states (indirectly defined by user),
    - embedded (user-independent) shutting down state. 
      Note 1. Some of user-defined rules an user may mark as check-points.
              Check-point states are derived from these rules.
      Note 2. Shutting down state differs from user-defined halting state.

  Daemon contains three embedded (user-independent) states : 
    - passive,
    - active,
    - aggressive.

  Apparatus contains two embedded (user-independent) states : 
    - normal,
    - emergency.

  User contains two embedded (user-independent) states : 
    - tracking,
    - stabilizing.


        1.2.2. Rules
        ^^^^^^^^^^^^
  There are three sets of rules :
    a) Daemon's set of non-deterministic rules.
       The set includes only daemon states.
    b) Common set of deterministic rules
       The set includes states of all controlling components (program, daemon, apparatus, user).
       In fact, this common set consists of two subsets :
       - program rules including
         * user-defined rules,
         * user-required check-point rules;
       - outside rules including
         * deterministic daemon rules, 
         * apparatus rules, 
         * user rules. 
    c) Daemon-defined set of rules (fault rules).
      

        1.2.3. Transitions
        ^^^^^^^^^^^^^^^^^^
  Each transition step consists of two half-steps (tacts) :
    a) First tact. Daemon performs transition according to non-deterministic rule
       from passive state to {passive, active, aggressive }
    b) Second tact. One of three kinds of transitions is performed :
       - normal transition, if daemon is in passive state,
       - fault transition, if daemon is in active state,
       - failure transition, if daemon is in aggressive state.
       Note. On second tact daemon always goes into passive state.
      

        1.2.4. Faults and failures
        ^^^^^^^^^^^^^^^^^^^^^^^^^^
  The difference between fault and failure is as follows.
  - Fault transition :
    * apparatus stay in normal state.
    * illegal (daemon-defined) program rule is applied, 
      and the program continues computation.
  - Failure transition :
    * apparatus go into in emergency state.
    * the program is unable to continue computation.


      1.3. Computational process
      --------------------------
   There are three phases of computational process :
   - program phase,
   - failure phase,
   - repairs phase.


        1.3.1. Program phase
        ^^^^^^^^^^^^^^^^^^^^
   Program phase includes 7 stages.

          1.3.1.1 Stage#1. Computation proper
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   If current program state is halting program state then go to Stage#7.
   If current program state is check-point program state then go to Stage#2.
   Otherwise :
   - Computation on Master Tape is performed according to the set of program rules;
   - Head of Synchro Tape is synchronized with head of Master Tape.
          

          1.3.1.2 Stage#2. Computation check
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and User Tape to the left side.
   2) Compare data on Master Tape and User Tape.
      If the data are identical 
      * then go to Stage#3
      * else go to Stage#5.


          1.3.1.3 Stage#3. Back up
          ~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and Backup Tape to the left side.
   2) Write Master Tape to Backup Tape.
   3) Rewind Synchro Tape and Backup Synchro Tape to the left side.
   4) Write Synchro Tape to Backup Synchro Tape.
   5) Go to Stage#4.


          1.3.1.4 Stage#4. Check of back up
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and Backup Tape to the left side.
   2) Compare data on Master Tape and Backup Tape.
      If the data are not identical 
      * then go to Stage#3
   3) Rewind Master Tape, Synchro Tape and Backup Synchro Tape to the left side.
   4) Compare data on Synchro Tape and Backup Synchro Tape;
      set up the head of Master Tape to continue computation.
      If the data are identical 
      * then go to Stage#1
      * else go to Stage#3.


          1.3.1.5 Stage#5. Recovery
          ~~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and Backup Tape to the left side.
   2) Write Backup Tape to Master Tape.
   3) Rewind Synchro Tape and Backup Synchro Tape to the left side.
   4) Write Backup Synchro Tape to Synchro Tape.
   5) Go to Stage#6.


          1.3.1.6 Stage#6. Recovery check
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and Backup Tape to the left side.
   2) Compare data on Master Tape and Backup Tape.
      If the data are not identical 
      * then go to Stage#3
   3) Rewind Master Tape, Synchro Tape and Backup Synchro Tape to the left side.
   4) Compare data on Synchro Tape and Backup Synchro Tape;
      set up the head of Master Tape to continue computation.
      If the data are identical 
      * then go to Stage#1
      * else go to Stage#5.


          1.3.1.7 Stage#7. Summary check
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   1) Rewind Master Tape and User Tape to the left side.
   2) Compare data on Master Tape and User Tape.
      If the data are identical 
      * then go to shutting down state
      * else go to Stage#5.



        1.3.2. Failure phase
        ^^^^^^^^^^^^^^^^^^^^
   1) Apparatus go into emergency state.
   2) Go to Repair phase.


        1.3.3. Repairs phase
        ^^^^^^^^^^^^^^^^^^^^
   1) User goes into stabilizing state.
   2) Apparatus go into normal state.
      User goes into tracking state.


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

====================================================
====== 2. Formalized definition (fragments) ========

      2.1. Basic Turing Machine
      -------------------------
  
  Let TM = <Q, T, I, sigma, !, b, q0, qfin> be 
  (ordinary deterministic) Turing Machine with semi-infinite tape.

  Elements of the 8-tuple mean as following :
  * Q is the set of the states;
  * T is the symbol alphabet;
  * I is the alphabet of input symbols; I is a part of T;
  * sigma : Q x T ---> Q x T x {L, R, N} is the transition function (rules).
  * ! is the left-side-marker symbol; ! belongs to T, but doesn't belong to I;
  * b is the empty symbol; b belongs to T, but doesn't belong to I;
  * q0 is the initial state; q0 belongs to Q;
  * qfin is the halting state; qfin belongs to Q;
  

      2.2. Expanded Turing Machine
      ----------------------------
  
  Definition. 5-tape Expanded Turing Machine (with semi-infinite tapes)
              corresponding to Turing Machine TM is 17-tuple
  ETM = <D, U, A, P, T, I, S, sigma, delta, gamma, mu, pi, !, b, q0, qfin, qstop>.

  Note. 5-tape Expanded Turing Machine is Expanded Turing Machine with one Master Tape.
        5 tapes of Expanded Turing Machine are as follows :
          - Master Tape,
          - Synchro Tape,
          - Backup Tape,
          - Backup Synchro Tape,
          - User (Tester) Tape;
    
  Elements of the 17-tuple mean as following :
  * D = {passive, active, aggressive} is the set of the (embedded) states of the daemon;
  * U = {tracking, stabilizing} is the set of the (embedded) states of the user;
  * A = {normal, emergency} is the set of the (embedded) states of the apparatus;
  * P is the set of the all program states (see below, the next paragraph)
  * T is from TM and used as the symbol alphabets for Master Tape, Backup Tape and User Tape;
  * I is from TM;
  * S = {!, b, +} is the symbol alphabet for Synchro Tape and Backup Synchro Tape;
  * sigma is from TM;
  * delta : Q x T ---> Q x T x {L, R, N} is the set of the program rules marked (by user) as check-point rules;
    delta is a part of sigma;
  * gamma : Q x T ---> Q x T x {L, R, N} is the set of the the function of illegal (fault) program rules;
    gamma is not a part of sigma;
  * mu : D --->  is the daemon transition function (rules).
  * pi : D x U x A x P x T x S x T x S x T 
         ---> 
         D x U x A x P  x T x {L, R, N}  x S x {L, R, N}  x T x {L, R, N}  x S x {L, R, N}  x T x {L, R, N}
         is the transition function (rules).
         Note. The pi transition function depends on the sigma transition function.

  * ! is from TM;
  * b is from TM;
  * q0 is from TM;
  * qfin is from TM;
  * qstop is the shutting down state; qstop belongs to P (qstop != qfin).

  Note. Obviously, ETM with one Master Tape 
        can be generalized to ETM with several Master Tapes.


        2.2.1. Program states
        ^^^^^^^^^^^^^^^^^^^^^

  The set of the all program states (P) consists of the following subsets and states :
  * Q (from TM),
  * P1 - the set of the check-points states defined on the basis of information 
         contained in the delta transition function.
  * P2 - the set of the computation check states;
  * P3 - the set of the backup states;
  * P4 - the set of the backup check states;
  * P5 - the set of the recovery states;
  * P6 - the set of the recovery check states;
  * P7 - the set of the summary check states;
  * qstop -  the shutting down state.

  The states contained in the sets P2-P7 are embedded states, 
  They don't depend on specific basic Turing Machine TM.


        2.2.2. Transition functions (the sets of the rules)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
          2.2.2.1 mu-function
          ~~~~~~~~~~~~~~~~~~~
  mu (passive) = {active, passive, aggressive}
  mu (active) = {passive}
  mu (aggressive) = {passive}

          2.2.2.2 pi-function
          ~~~~~~~~~~~~~~~~~~~
  1) Stage#1. Computation proper
     The rules are based on the sigma and delta transition functions.

  2) Stage#2. Computation check
  3) Stage#3. Back up
  4) Stage#4. Check of back up
  5) Stage#5. Recovery
  6) Stage#6. Recovery check
  7) Stage#7. Summary check
     The rules for Stages#2-#7 are mostly TM-independent 
     (don't depend on basic Turing Machine TM).



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

==========================================================================
===================== 3. C++ Simulator (Beta Version)  ===================

  The C++-Simulator simulates a Turing Machine with faults, failures and recovery (ETM).
  ETM is defined by input files : 
  * metafile, 
  * description file, 
  * states file, 
  * alphabet file, 
  * transition file, 
  * input word(s) file(s).
  
  1) Each row of metafile contains data related to some Expanded Turing Machine :
     * name of description file, 
     * number of master tapes, 
     * name of states file,
     * name of alphabet file,
     * name of transition file, 
     * name(s) of input word(s) file(s).
  2) Description file contains verbal description of the machine [optional].
  3) States file contains list of initial, halting and internal user-defined program states.
  4) Alphabet contains list of empty, input and internal symbols.
  5) Each row of transition contains some transition rule
     - some rules may be marked as check-points;
     - illegal daemon-defined rules (fault rules) may be added.
  6) Each row of input word(s) contains input word for some tape.
  

  Known bug. Sometimes programs doesn't work if there are more than one check-point.


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

====================================================
===================== 4. Download ==================
//#########################################################

http://sourceforge.net/project/showfiles.php?group_id=79519&package_id=85144
http://alexvn.freeservers.com/s1/turing-s.zip