This site is supported by donations to The OEIS Foundation.

Differential Analytic Turing Automata • Part 2

From OeisWiki
Jump to: navigation, search

Author: Jon Awbrey

• Overview • Part 1 • Part 2 • Document History •

Turing Machine Examples

☞ See Theme One Program for documentation of the cactus graph syntax and the propositional modeling program used below.

By way of providing a simple illustration of Cook's Theorem, namely, that “Propositional Satisfiability is NP-Complete”, I will describe one way to translate finite approximations of turing machines into propositional expressions, using the cactus language syntax for propositional calculus to be described in more detail as we proceed.

Space and time limited turing machine,
with units of space and units of time.
Space and time limited turing machine,
for computing the parity of a bit string, with number of tape cells of input equal to

I will follow the pattern of discussion in Herbert Wilf (1986), Algorithms and Complexity, pp. 188–201, but translate its logical formalism into cactus language, which is more efficient in regard to the number of propositional clauses required.

A turing machine for computing the parity of a bit string is described by means of the following Figure and Table.

Parity Machine.jpg 
Table 4.  Parity Machine
o-------o--------o-------------o---------o------------o
| State | Symbol | Next Symbol | Ratchet | Next State |
|   Q   |   S    |     S'      |   dR    |     Q'     |
o-------o--------o-------------o---------o------------o
|   0   |   0    |     0       |   +1    |     0      |
|   0   |   1    |     1       |   +1    |     1      |
|   0   |   #    |     #       |   -1    |     #      |
|   1   |   0    |     0       |   +1    |     1      |
|   1   |   1    |     1       |   +1    |     0      |
|   1   |   #    |     #       |   -1    |     *      |
o-------o--------o-------------o---------o------------o


The TM has a finite automaton (FA) as one component. Let us refer to this particular FA by the name of

The tape head (that is, the read unit) will be called The registers are also called tape cells or tape squares.

Finite Approximations

To see how each finite approximation to a given turing machine can be given a purely propositional description, one fixes the parameter and limits the rest of the discussion to describing which is not really a full-fledged TM anymore but just a finite automaton in disguise.

In this example, for the sake of a minimal illustration, we choose and discuss Since the zeroth tape cell and the last tape cell are both occupied by the character that is used for both the beginning of file and the end of file markers, this allows for only one digit of significant computation.

To translate into propositional form we use the following collection of basic propositions, boolean variables, or logical features, however one wishes to view them.

Basic Propositions

The basic propositions for describing the present state function are these:

The proposition of the form says:

At the time the finite state machine is in the state

The basic propositions for describing the present register function are these:

The proposition of the form says:

At the time the tape head is on the tape cell

The basic propositions for describing the present symbol function are these:

The proposition of the form says:

At the time the tape cell bears the mark

Initial Conditions

Given but a single free square on the tape, there are just two different sets of initial conditions for the finite approximation to the parity turing machine we are presently considering.

Initial Conditions for Tape Input "0"

The following conjunction of 5 basic propositions describes the initial conditions when is started with an input of “0” in its free square:

This conjunction of basic propositions may be read as follows:

At time machine is in the state

At time scanner is reading cell

At time cell contains the symbol

At time cell contains the symbol

At time cell contains the symbol

Initial Conditions for Tape Input "1"

The following conjunction of 5 basic propositions describes the initial conditions when is started with an input of “1” in its free square:

This conjunction of basic propositions may be read as follows:

At time machine is in the state

At time scanner is reading cell

At time cell contains the symbol

At time cell contains the symbol

At time cell contains the symbol

Propositional Program

A complete description of in propositional form is obtained by conjoining one of the above choices for initial conditions with all of the following sets of propositions, serving in effect as a simple type of declarative program which tells us everything we need to know about the anatomy and behavior of the truncated TM in question.

Mediate Conditions

Terminal Conditions

State Partition

Register Partition

Symbol Partition

Interaction Conditions

Transition Relations

Interpretation of the Propositional Program

Let us now run through the propositional specification of our truncated TM, and paraphrase what it says in ordinary language.

Mediate Conditions

In the interpretation of the cactus language for propositional logic we are using here, an expression of the form expresses a conditional, an implication, or an if-then proposition, commonly read in one of the following ways:

An expression of the form corresponds to a graph-theoretic data-structure of the following form: 

o---------------------------------------o
|                                       |
|                 p   q                 |
|                 o---o                 |
|                 |                     |
|                 @                     |
|                                       |
o---------------------------------------o
|               ( p ( q ))              |
o---------------------------------------o

Taken together, the Mediate Conditions state the following:

If at time is in state then at time is in state and

If at time is in state then at time is in state and

If at time is in state then at time is in state and

If at time is in state then at time is in state

Terminal Conditions

In cactus syntax an expression of the form expresses the disjunction   The corresponding cactus graph, here just a tree, has the following shape: 

o---------------------------------------o
|                                       |
|                 p   q                 |
|                 o   o                 |
|                  \ /                  |
|                   o                   |
|                   |                   |
|                   @                   |
|                                       |
o---------------------------------------o
|               ((p) (q))               |
o---------------------------------------o

In effect, the Terminal Conditions state the following:

At time machine is in state or

At time machine is in state

State Partition

In cactus syntax an expression of the form expresses a statement to the effect that exactly one of the expressions is true, for   Expressions of this form are called universal partition expressions.  The corresponding painted and rooted cactus (PARC) has the following shape: 

o---------------------------------------o
|                                       |
|         e_1   e_2   ...   e_k         |
|          o     o           o          |
|          |     |           |          |
|          o-----o--- ... ---o          |
|           \               /           |
|            \             /            |
|             \           /             |
|              \         /              |
|               \       /               |
|                \     /                |
|                 \   /                 |
|                  \ /                  |
|                   @                   |
|                                       |
o---------------------------------------o
|       ((e_1),(e_2),(...),(e_k))       |
o---------------------------------------o

The State Partition segment of the propositional program consists of three universal partition expressions, taken in conjunction expressing the condition that has to be in one and only one of its specified states at each point in time under consideration.  In short, we have the constraint:

At each time in the set

is in exactly one of the states

Register Partition

The Register Partition segment of the propositional program consists of three universal partition expressions, taken in conjunction saying the read head must be reading one and only one of the registers or tape cells available to it at each of the points in time under consideration.  In sum:

At each time in the set

is reading exactly one of the tape cells

Symbol Partition

The Symbol Partition segment of the propositional program for consists of nine universal partition expressions, taken in conjunction stipulating that there has to be one and only one symbol in each of the registers at each point in time under consideration.  In short, we have:

At each time in the set

each of the tape cells  

contains exactly one of the signs in

Interaction Conditions

In briefest terms, the Interaction Conditions simply express the circumstance that the mark on a tape cell cannot change between two points in time unless the tape head is over the cell in question at the initial one of those points in time.  All we have to do is see how they manage to say this.

Consider a cactus expression of the following form:

This expression has the corresponding cactus graph: 

o---------------------------------------o
|                                       |
|         t<i>_r<j>   t<i+1>_r<j>_s<k>  |
|                 o   o                 |
|                  \ /                  |
|    t<i>_r<j>_s<k> o                   |
|                   |                   |
|                   @                   |
|                                       |
o---------------------------------------o

A propositional expression of this form can be read as follows:

at the time the tape cell contains the sign and
it is not the case at the time that is on the cell
at the time the tape cell contains the sign

The eighteen clauses of the Interaction Conditions impose one such constraint on symbol changes for each combination of the times registers and symbols

Transition Relations

The Transition Relation segment of the propositional program for consists of sixteen implication statements with complex antecedents and consequents.  Taken together, these give propositional expression to the TM Figure and Table given at the outset.

Just by way of a single example, consider the clause:

This complex implication statement can be read to say:

at the time is in the state and
at the time is reading cell and
at the time the cell contains a
at the time is in the state and
at the time is reading cell and
at the time the cell contains a

Computation

The propositional program for uses the following set of basic propositions or boolean variables:

This means the propositional program itself is nothing but a single proposition or boolean function of the form

An assignment of boolean values to the above set of boolean variables is called an interpretation of the proposition and any interpretation of making the proposition evaluate to is referred to as a satisfying interpretation of the proposition   Another way to specify interpretations, instead of giving them as bit vectors in and trying to remember some arbitrary ordering of variables, is to give them in the form of singular propositions, that is, conjunctions of the form where each is either or that is, either the assertion or the negation of the boolean variable as runs from to   Even more succinctly, the same information can be communicated simply by giving the conjunction of the asserted variables, with the understanding that each of the others is negated.

A satisfying interpretation of the proposition supplies us with all the information of a complete execution history for the corresponding program, so all we have to do in order to get the output of the program is to read off the proper part of the data from the expression of this interpretation.

Output

One component of the program I developed some years ago finds all the satisfying interpretations of propositions expressed in cactus syntax.  It is not a polynomial time algorithm, as you may guess, but it is just barely efficient enough to do this example in the 500K of spare memory I had on my 1989 vintage 286 PC, so I will give you the actual outputs from those trials.

Output Conditions for Tape Input "0"

Let be the proposition obtained by conjoining the proposition specifying the initial conditions for tape input “0” with the proposition describing the truncated turing machine   As it turns out, has a single satisfying interpretation.  This interpretation is expressible in the form of a singular proposition, which can in turn be indicated by its positive logical features, as shown in the following display: 

o-------------------------------------------------o
|                                                 |
| t0_q0                                           |
|  t0_r1                                          |
|   t0_r0_s#                                      |
|    t0_r1_s0                                     |
|     t0_r2_s#                                    |
|      t1_q0                                      |
|       t1_r2                                     |
|        t1_r2_s#                                 |
|         t1_r0_s#                                |
|          t1_r1_s0                               |
|           t2_q#                                 |
|            t2_r1                                |
|             t2_r0_s#                            |
|              t2_r1_s0                           |
|               t2_r2_s#                          |
|                                                 |
o-------------------------------------------------o

The Output Conditions for Tape Input “0” can be read as follows:

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

The output of being the symbol that rests under the tape head if and when the machine reaches one of its resting states, we get the result that

Output Conditions for Tape Input "1"

Let be the proposition obtained by conjoining the proposition specifying the initial conditions for tape input “1” with the proposition describing the truncated turing machine   As it turns out, has a single satisfying interpretation.  This interpretation is expressible in the form of a singular proposition, which can in turn be indicated by its positive logical features, as shown in the following display: 

o-------------------------------------------------o
|                                                 |
| t0_q0                                           |
|  t0_r1                                          |
|   t0_r0_s#                                      |
|    t0_r1_s1                                     |
|     t0_r2_s#                                    |
|      t1_q1                                      |
|       t1_r2                                     |
|        t1_r2_s#                                 |
|         t1_r0_s#                                |
|          t1_r1_s1                               |
|           t2_q*                                 |
|            t2_r1                                |
|             t2_r0_s#                            |
|              t2_r1_s1                           |
|               t2_r2_s#                          |
|                                                 |
o-------------------------------------------------o

The Output Conditions for Tape Input “1” can be read as follows:

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time machine is in the state

At the time scanner is reading cell

At the time tape cell is marked with a

At the time tape cell is marked with a

At the time tape cell is marked with a

The output of being the symbol that rests under the tape head when and if the machine reaches one of its resting states, we get the result that

• Overview • Part 1 • Part 2 • Document History •

Retrieved from "https://oeis.org/w/index.php?title=Differential_Analytic_Turing_Automata_•_Part_2&oldid=1641101"