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