[Arisbe] Peirce's Cook's Turing
Jon Awbrey
arisbe@stderr.org
Mon, 15 Jan 2001 01:23:02 -0500
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Arisbeans, Conceptual Graphists, SemioComrades,
A certain momentum of thought compels me to continue
this essay, in spite of every obstacle that has been
tossed in its path. Though it arise from a labor of
love, and thus in a way is sufficient to itself, its
own reward, as they say, still it cannot be complete
until it receives the reception that it seeks in the
receipt-book of its due receiver, to coin a pharisee,
and just because it is a labor of love does not mean
that I would be able to see it lost with any measure
of cool equanimity or respite of a phlegmatic temper.
I am posting this result to the Arisbe and the CG Lists
because of their common and continuing reference to the
work of Peirce on Logical Graphs, but I imagine that my
excuse to each of these two companies for attempting to
engage their several attentions would have to be just a
little bit different. But the near continuous offering
of excuses for why "your own work" (YOW) might be worth
the consideration of another living soul who happens to
be laboring away in roughly the same domain of interest,
as though your lifelong dedication to the task were not
already some kind of silent testimony -- well, you hate
that, too, don't you? -- so let us put it off for a day
in the future, and spend the precious time that we have
on what is more fun and more useful to boot. If nobody,
after a reasonable interval, sees the excuse for it all
abiding already in the process or in the product itself,
then that will be the time for making our humble excuse.
On to the work!
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
By way of providing a simple illustration of Cook's Theorem,
that "Propositional Satisfiability is NP-Complete", here is
an exposition of one way to translate Turing Machine set-ups
into propositional expressions, employing the RefLog Syntax
for Prop Calc that I described in a couple of earlier notes:
Notation:
Stilt<k> = Space and Time Limited Turing Machine,
with k units of space and k units of time.
Stunt<k> = Space and Time Limited Turing Machine,
for computing the parity of a bit string,
with Number of Tape cells of input equal to k.
I will follow the pattern of the discussion in the book of
Herbert Wilf, 'Algorithms & Complexity' (1986), pages 188-201,
but translate into RefLog, which is more efficient with respect
to the number of propositional clauses that are required.
Parity Machine:
-------------------------------------------------------
| State | Symbol | Next Symbol | Ratchet | Next State |
| Q | S | S' | dR | Q' |
-------------------------------------------------------
| 0 | 0 | 0 | +1 | 0 |
| 0 | 1 | 1 | +1 | 1 |
| 0 | # | # | -1 | # |
| 1 | 0 | 0 | +1 | 1 |
| 1 | 1 | 1 | +1 | 0 |
| 1 | # | # | -1 | * |
-------------------------------------------------------
1/1/+1
------->
/\ / \ /\
0/0/+1 ^ 0 1 ^ 0/0/+1
\/|\ /|\/
| <------- |
#/#/-1 | 1/1/+1 | #/#/-1
| |
v v
# *
The TM has a "finite automaton" (FA) as its component.
Let us refer to this particular FA by the name of "M".
The "tape-head" (that is, the "read-unit") will be called "H".
The "registers" are also called "tape-cells" or "tape-squares".
In order to consider how the finitely "stilted" rendition of this TM
can be translated into the form of a purely propositional description,
one now fixes k and limits the discussion to talking about a Stilt<k>,
which is really not a true TM anymore but a finite automaton in disguise.
In this example, for the sake of a minimal illustration, we choose k = 2,
and discuss Stunt<2>. Since the zeroth tape cell and the last tape cell
are occupied with bof and eof marks "#", this amounts to only one digit
of significant computation.
To translate Stunt<2> into propositional form we use
the following collection of propositional variables:
For the "Present State Function" QF : P -> Q,
{ p0_q#, p0_q*, p0_q0, p0_q1,
| p1_q#, p1_q*, p1_q0, p1_q1,
| p2_q#, p2_q*, p2_q0, p2_q1,
| p3_q#, p3_q*, p3_q0, p3_q1
}
The propositional expression of the form "pi_qj" says:
| At the point in time p<i>,
| the finite machine M is in the state q<j>.
For the "Present Register Function" RF : P -> R,
{ p0_r0, p0_r1, p0_r2, p0_r3,
| p1_r0, p1_r1, p1_r2, p1_r3,
| p2_r0, p2_r1, p2_r2, p2_r3,
| p3_r0, p3_r1, p3_r2, p3_r3
}
The propositional expression of the form "pi_rj" says:
| At the point in time p<i>,
| the tape-head H is on the tape-cell r<j>.
For the "Present Symbol Function" SF : P -> (R -> S),
{ p0_r0_s#, p0_r0_s*, p0_r0_s0, p0_r0_s1,
| p0_r1_s#, p0_r1_s*, p0_r1_s0, p0_r1_s1,
| p0_r2_s#, p0_r2_s*, p0_r2_s0, p0_r2_s1,
| p0_r3_s#, p0_r3_s*, p0_r3_s0, p0_r3_s1,
| p1_r0_s#, p1_r0_s*, p1_r0_s0, p1_r0_s1,
| p1_r1_s#, p1_r1_s*, p1_r1_s0, p1_r1_s1,
| p1_r2_s#, p1_r2_s*, p1_r2_s0, p1_r2_s1,
| p1_r3_s#, p1_r3_s*, p1_r3_s0, p1_r3_s1,
| p2_r0_s#, p2_r0_s*, p2_r0_s0, p2_r0_s1,
| p2_r1_s#, p2_r1_s*, p2_r1_s0, p2_r1_s1,
| p2_r2_s#, p2_r2_s*, p2_r2_s0, p2_r2_s1,
| p2_r3_s#, p2_r3_s*, p2_r3_s0, p2_r3_s1,
| p3_r0_s#, p3_r0_s*, p3_r0_s0, p3_r0_s1,
| p3_r1_s#, p3_r1_s*, p3_r1_s0, p3_r1_s1,
| p3_r2_s#, p3_r2_s*, p3_r2_s0, p3_r2_s1,
| p3_r3_s#, p3_r3_s*, p3_r3_s0, p3_r3_s1
}
The propositional expression of the form "pi_rj_sk" says:
| At the point in time p<i>,
| the tape-cell r<j> bears the mark s<k>."
The propositional description of a Stunt<2>
which starts with the following tape contents:
{"#" in cell 0, "0" in cell 1, "#" in cell 2}
is the conjunction of the following clauses:
¤~~~~~~~~~¤~~~~~~~~~¤~PROPOSITION~¤~~~~~~~~~¤~~~~~~~~~¤
Initial Conditions:
p0_q0
p0_r1
p0_r0_s# p0_r1_s0 p0_r2_s#
Mediate Conditions:
( p0_q# ( p1_q# ))
( p0_q* ( p1_q* ))
( p1_q# ( p2_q# ))
( p1_q* ( p2_q* ))
Terminal Conditions:
(( p2_q# )( p2_q* ))
State Partition:
(( p0_q0 ),( p0_q1 ),( p0_q# ),( p0_q* ))
(( p1_q0 ),( p1_q1 ),( p1_q# ),( p1_q* ))
(( p2_q0 ),( p2_q1 ),( p2_q# ),( p2_q* ))
Register Partition:
(( p0_r0 ),( p0_r1 ),( p0_r2 ))
(( p1_r0 ),( p1_r1 ),( p1_r2 ))
(( p2_r0 ),( p2_r1 ),( p2_r2 ))
Symbol Partition:
(( p0_r0_s0 ),( p0_r0_s1 ),( p0_r0_s# ))
(( p0_r1_s0 ),( p0_r1_s1 ),( p0_r1_s# ))
(( p0_r2_s0 ),( p0_r2_s1 ),( p0_r2_s# ))
(( p1_r0_s0 ),( p1_r0_s1 ),( p1_r0_s# ))
(( p1_r1_s0 ),( p1_r1_s1 ),( p1_r1_s# ))
(( p1_r2_s0 ),( p1_r2_s1 ),( p1_r2_s# ))
(( p2_r0_s0 ),( p2_r0_s1 ),( p2_r0_s# ))
(( p2_r1_s0 ),( p2_r1_s1 ),( p2_r1_s# ))
(( p2_r2_s0 ),( p2_r2_s1 ),( p2_r2_s# ))
Interaction Conditions:
(( p0_r0 ) p0_r0_s0 ( p1_r0_s0 ))
(( p0_r0 ) p0_r0_s1 ( p1_r0_s1 ))
(( p0_r0 ) p0_r0_s# ( p1_r0_s# ))
(( p0_r1 ) p0_r1_s0 ( p1_r1_s0 ))
(( p0_r1 ) p0_r1_s1 ( p1_r1_s1 ))
(( p0_r1 ) p0_r1_s# ( p1_r1_s# ))
(( p0_r2 ) p0_r2_s0 ( p1_r2_s0 ))
(( p0_r2 ) p0_r2_s1 ( p1_r2_s1 ))
(( p0_r2 ) p0_r2_s# ( p1_r2_s# ))
(( p1_r0 ) p1_r0_s0 ( p2_r0_s0 ))
(( p1_r0 ) p1_r0_s1 ( p2_r0_s1 ))
(( p1_r0 ) p1_r0_s# ( p2_r0_s# ))
(( p1_r1 ) p1_r1_s0 ( p2_r1_s0 ))
(( p1_r1 ) p1_r1_s1 ( p2_r1_s1 ))
(( p1_r1 ) p1_r1_s# ( p2_r1_s# ))
(( p1_r2 ) p1_r2_s0 ( p2_r2_s0 ))
(( p1_r2 ) p1_r2_s1 ( p2_r2_s1 ))
(( p1_r2 ) p1_r2_s# ( p2_r2_s# ))
Transition Relations:
( p0_q0 p0_r1 p0_r1_s0 ( p1_q0 p1_r2 p1_r1_s0 ))
( p0_q0 p0_r1 p0_r1_s1 ( p1_q1 p1_r2 p1_r1_s1 ))
( p0_q0 p0_r1 p0_r1_s# ( p1_q# p1_r0 p1_r1_s# ))
( p0_q0 p0_r2 p0_r2_s# ( p1_q# p1_r1 p1_r2_s# ))
( p0_q1 p0_r1 p0_r1_s0 ( p1_q1 p1_r2 p1_r1_s0 ))
( p0_q1 p0_r1 p0_r1_s1 ( p1_q0 p1_r2 p1_r1_s1 ))
( p0_q1 p0_r1 p0_r1_s# ( p1_q* p1_r0 p1_r1_s# ))
( p0_q1 p0_r2 p0_r2_s# ( p1_q* p1_r1 p1_r2_s# ))
( p1_q0 p1_r1 p1_r1_s0 ( p2_q0 p2_r2 p2_r1_s0 ))
( p1_q0 p1_r1 p1_r1_s1 ( p2_q1 p2_r2 p2_r1_s1 ))
( p1_q0 p1_r1 p1_r1_s# ( p2_q# p2_r0 p2_r1_s# ))
( p1_q0 p1_r2 p1_r2_s# ( p2_q# p2_r1 p2_r2_s# ))
( p1_q1 p1_r1 p1_r1_s0 ( p2_q1 p2_r2 p2_r1_s0 ))
( p1_q1 p1_r1 p1_r1_s1 ( p2_q0 p2_r2 p2_r1_s1 ))
( p1_q1 p1_r1 p1_r1_s# ( p2_q* p2_r0 p2_r1_s# ))
( p1_q1 p1_r2 p1_r2_s# ( p2_q* p2_r1 p2_r2_s# ))
¤~~~~~~~~~¤~~~~~~~~~¤~NOITISOPORP~¤~~~~~~~~~¤~~~~~~~~~¤
Interpretation of the Propositional Description:
Initial Conditions:
p0_q0
p0_r1
p0_r0_s# p0_r1_s0 p0_r2_s#
The Initial Conditions are given by a logical conjunction
that is composed of 5 basic expressions, altogether stating:
| At p<0>, M is in the state q<0>, and
| At p<0>, H is on the cell r<1>, and
| At p<0>, cell r<0> bears the mark "#", and
| At p<0>, cell r<1> bears the mark "0", and
| At p<0>, cell r<2> bears the mark "#".
Mediate Conditions:
( p0_q# ( p1_q# ))
( p0_q* ( p1_q* ))
( p1_q# ( p2_q# ))
( p1_q* ( p2_q* ))
In RefLog, an expression of the form "( X ( Y ))"
expresses an implication or an if-then proposition:
"Not X without Y", "If X then Y", "X => Y", etc.
A text string expression of the form "( X ( Y ))"
parses to a graphical data-structure of the form:
X Y
o---o
|
@
All together, these Mediate Conditions state:
| If at p<0> M is in state q<#>, then at p<1> M is in state q<#>, and
| If at p<0> M is in state q<*>, then at p<1> M is in state q<*>, and
| If at p<1> M is in state q<#>, then at p<2> M is in state q<#>, and
| If at p<1> M is in state q<*>, then at p<2> M is in state q<*>.
Terminal Conditions:
(( p2_q# )( p2_q* ))
In RefLog, an expression of the form "(( X )( Y ))"
expresses a disjunction "X or Y", and it parses to:
X Y
o o
\ /
o
|
@
In effect, the Terminal Conditions state:
| At p<2> M is in state q<#>, or
| At p<2> M is in state q<*>.
State Partition:
(( p0_q0 ),( p0_q1 ),( p0_q# ),( p0_q* ))
(( p1_q0 ),( p1_q1 ),( p1_q# ),( p1_q* ))
(( p2_q0 ),( p2_q1 ),( p2_q# ),( p2_q* ))
In RefLog, an expression of the form "(( X<1> ),( X<2> ),( ... ),( X<k> ))"
states it as a fact that "exactly one of the X<j> are true, for j = 1 to k".
Expressions of this form are called "universal partition" expressions, and
they parse into a type of graph called a "painted and rooted cactus" (PARC):
X<1> X<2> ... X<k>
o o o
| | |
o-----o--- ... ---o
\ /
\ /
\ /
\ /
\ /
\ /
\ /
\ /
@
The State Partition expresses the conditions that:
| At each of the points-in-time p<i>, for i = 0 to 2,
| M can be in exactly one state q<j>, for j in the set {0, 1, #, *}.
Register Partition:
(( p0_r0 ),( p0_r1 ),( p0_r2 ))
(( p1_r0 ),( p1_r1 ),( p1_r2 ))
(( p2_r0 ),( p2_r1 ),( p2_r2 ))
The Register Partition expresses the conditions that:
| At each of the points-in-time p<i>, for i = 0 to 2,
| H can be on exactly one cell r<j>, for j = 0 to 2.
Symbol Partition:
(( p0_r0_s0 ),( p0_r0_s1 ),( p0_r0_s# ))
(( p0_r1_s0 ),( p0_r1_s1 ),( p0_r1_s# ))
(( p0_r2_s0 ),( p0_r2_s1 ),( p0_r2_s# ))
(( p1_r0_s0 ),( p1_r0_s1 ),( p1_r0_s# ))
(( p1_r1_s0 ),( p1_r1_s1 ),( p1_r1_s# ))
(( p1_r2_s0 ),( p1_r2_s1 ),( p1_r2_s# ))
(( p2_r0_s0 ),( p2_r0_s1 ),( p2_r0_s# ))
(( p2_r1_s0 ),( p2_r1_s1 ),( p2_r1_s# ))
(( p2_r2_s0 ),( p2_r2_s1 ),( p2_r2_s# ))
The Symbol Partition expresses the conditions that:
| At each of the points-in-time p<i>, for i in {0, 1, 2},
| In each of the tape-registers r<j>, for j in {0, 1, 2},
| There can be exactly one sign s<k>, for k in {0, 1, #}.
Interaction Conditions:
(( p0_r0 ) p0_r0_s0 ( p1_r0_s0 ))
(( p0_r0 ) p0_r0_s1 ( p1_r0_s1 ))
(( p0_r0 ) p0_r0_s# ( p1_r0_s# ))
(( p0_r1 ) p0_r1_s0 ( p1_r1_s0 ))
(( p0_r1 ) p0_r1_s1 ( p1_r1_s1 ))
(( p0_r1 ) p0_r1_s# ( p1_r1_s# ))
(( p0_r2 ) p0_r2_s0 ( p1_r2_s0 ))
(( p0_r2 ) p0_r2_s1 ( p1_r2_s1 ))
(( p0_r2 ) p0_r2_s# ( p1_r2_s# ))
(( p1_r0 ) p1_r0_s0 ( p2_r0_s0 ))
(( p1_r0 ) p1_r0_s1 ( p2_r0_s1 ))
(( p1_r0 ) p1_r0_s# ( p2_r0_s# ))
(( p1_r1 ) p1_r1_s0 ( p2_r1_s0 ))
(( p1_r1 ) p1_r1_s1 ( p2_r1_s1 ))
(( p1_r1 ) p1_r1_s# ( p2_r1_s# ))
(( p1_r2 ) p1_r2_s0 ( p2_r2_s0 ))
(( p1_r2 ) p1_r2_s1 ( p2_r2_s1 ))
(( p1_r2 ) p1_r2_s# ( p2_r2_s# ))
In briefest terms, the Interaction Conditions merely express
the circumstance that the sign in 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 that we have to do is to see how they manage to say this.
In RefLog, an expression of the following form:
"(( p<i>_r<j> ) p<i>_r<j>_s<k> ( p<i+1>_r<j>_s<k> ))",
and which parses as the graph:
p<i>_r<j> o o p<i+1>_r<j>_s<k>
\ /
p<i>_r<j>_s<k> o
|
@
can be read in the form of the following implication:
| If
| At the point-in-time p<i>, the tape-cell r<j> bears the mark s<k>,
| But it is not the case that
| At the point-in-time p<i>, the tape-head is on the tape-cell r<j>.
| Then
| At the point-in-time p<i+1>, the tape-cell r<j> bears the mark s<k>.
Folks among us of a certain age and a peculiar manner of acculturation will
recognize these as the "Frame Conditions" for the change of state of the TM.
Transition Relations:
( p0_q0 p0_r1 p0_r1_s0 ( p1_q0 p1_r2 p1_r1_s0 ))
( p0_q0 p0_r1 p0_r1_s1 ( p1_q1 p1_r2 p1_r1_s1 ))
( p0_q0 p0_r1 p0_r1_s# ( p1_q# p1_r0 p1_r1_s# ))
( p0_q0 p0_r2 p0_r2_s# ( p1_q# p1_r1 p1_r2_s# ))
( p0_q1 p0_r1 p0_r1_s0 ( p1_q1 p1_r2 p1_r1_s0 ))
( p0_q1 p0_r1 p0_r1_s1 ( p1_q0 p1_r2 p1_r1_s1 ))
( p0_q1 p0_r1 p0_r1_s# ( p1_q* p1_r0 p1_r1_s# ))
( p0_q1 p0_r2 p0_r2_s# ( p1_q* p1_r1 p1_r2_s# ))
( p1_q0 p1_r1 p1_r1_s0 ( p2_q0 p2_r2 p2_r1_s0 ))
( p1_q0 p1_r1 p1_r1_s1 ( p2_q1 p2_r2 p2_r1_s1 ))
( p1_q0 p1_r1 p1_r1_s# ( p2_q# p2_r0 p2_r1_s# ))
( p1_q0 p1_r2 p1_r2_s# ( p2_q# p2_r1 p2_r2_s# ))
( p1_q1 p1_r1 p1_r1_s0 ( p2_q1 p2_r2 p2_r1_s0 ))
( p1_q1 p1_r1 p1_r1_s1 ( p2_q0 p2_r2 p2_r1_s1 ))
( p1_q1 p1_r1 p1_r1_s# ( p2_q* p2_r0 p2_r1_s# ))
( p1_q1 p1_r2 p1_r2_s# ( p2_q* p2_r1 p2_r2_s# ))
The Transition Conditions merely serve to express,
by means of 16 complex implication expressions,
the data of the TM table that was given above.
Jon Awbrey
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤