Turing Machine with faults, failures and recovery

    In contrast to practical situation an ordinary Turing Machine never fails.
    An attempt to describe some Turing Machine that may fail was made.
    Here is brief description of
    * Turing Machine with faults, failures and recovery
        and
    * its C++ Simulator (Beta version).
    http://alexvn.freeservers.com/s1/turing-s.html
    http://groups.google.com/groups?th=738ab622a7586f42




    CONTENT.
    1. Informal definition
          1.1. Tapes, alphabets
          1.2. Controlling components, states and rules
                    1.2.1. States
                    1.2.2. Rules
                    1.2.3. Transitions
                    1.2.4. Faults and failures
          1.3. Computational process
                    1.3.1. Program phase
                    1.3.2. Failure phase
                    1.3.3. Repairs phase
    2. Formalized definition (fragments)
          2.1. Basic Turing Machine
          2.2. Expanded Turing Machine
                    2.2.1. Program states
                    2.2.2. Transition functions (the sets of the rules)
    3. C++ Simulator






            1. Informal definition
            =====================


    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>.


    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 ---> <set of subsets of 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
            ================




    C++ Simularor (Beta version) of a Turing Machine with faults, failures and recovery can be seen at :


    --------- Download ---------
    http://alexvn.freeservers.com/s1/turing-s.html
    http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=5881&lngWId=3


    --------- Sources ---------
    http://groups.google.com/groups?th=738ab622a7586f42




    The C++-program 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.




      =================================
      Alex Vinokur
          mailto:alexvn@connect.to
          http://www.simtel.net/pub/oth/19088.html
      =================================

Return to the comp.compilers page.
Search the comp.compilers archives again.