W3C home > Mailing lists > Public > www-rdf-logic@w3.org > January 2001

Differential Analytic Turing Automata (DATA)

From: Jon Awbrey <jawbrey@oakland.edu>
Date: Sat, 20 Jan 2001 17:34:01 -0500
Message-ID: <3A6A1259.85DAB4CF@oakland.edu>
To: Arisbe <arisbe@stderr.org>, Conceptual Graphs <cg@cs.uah.edu>, RDF Logic <www-rdf-logic@w3.org>, SemioCom <semiocom@listbot.com>
CC: Dietrich Fischer <fischer@DARMSTADT.GMD.DE>, Mary Keeler <mkeeler@u.washington.edu>, Jack Park <jackpark@VERTICALNET.COM>, John F Sowa <sowa@bestweb.net>
才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~

The Shroud Of Turing

才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~

This swatch is really just a work in progress,
and I invite you to share in shaping it with me,
as I really do not know what the upshot or even
what the medium will be, or what will be needed
to rend of it an eventual and a genuine reality.

In lieu of a proper beginning, then, let me just gather
together my partial arrays and my random samples of data,
if you wish, with me, to call it that, that I have spent
my off-times collecting for lo! so many even-odder years.

I must apologize in advance for the many bits of redundancy --
though redundancy is the essence of information, is it not? --
that I am about to inflict on you in one moment, two, three --
but it will further the aim of future reference to have all
of this skein in a close-knit neighborhood of our surrogate
backcloth for the excessive surplices of originfinite sites.

才~~~~~~~~才~~~~~~~~才ILLUSTRATION~才~~~~~~~~才~~~~~~~~

So let me make my further ado with this deferential but deturing excuse,
that I merely want to demonstrate that my RefLog rendering of a stilted,
stunted turing machine can compute a bit more than the parity of single,
trivial, unprecedented, null-valued evanishment of the lone number zero.

So here, for ease of reference in future,
is a preamble to the formal constitution
of a particular variety of logical style
for transposing a TM into a proposition:

才~~~~~~~~才~~~~~~~~才EXEGESIS~才~~~~~~~~才~~~~~~~~

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

才~~~~~~~~才~~~~~~~~才SISEGEXE~才~~~~~~~~才~~~~~~~~

So with all due further ado,
here are the Initial Conditions
for the two possible inputs to the
RefLog redaction of this Parity TM:

才~~~~~~~~才~~~~~~~~才INPUT~0~才~~~~~~~~才~~~~~~~~

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 the point-in-time p<0>, M is in the state q<0>, and
| At the point-in-time p<0>, H is on the cell  r<1>, and
| At the point-in-time p<0>, cell r<0> bears the mark "#", and
| At the point-in-time p<0>, cell r<1> bears the mark "0", and
| At the point-in-time p<0>, cell r<2> bears the mark "#".

才~~~~~~~~才~~~~~~~~才0~TUPNI~才~~~~~~~~才~~~~~~~~

才~~~~~~~~才~~~~~~~~才INPUT~1~才~~~~~~~~才~~~~~~~~

Initial Conditions:

p0_q0

p0_r1

p0_r0_s#
p0_r1_s1
p0_r2_s#

The Initial Conditions are given by a logical conjunction
that is composed of 5 basic expressions, altogether stating:

| At the point-in-time p<0>, M is in the state q<0>, and
| At the point-in-time p<0>, H is on the cell  r<1>, and
| At the point-in-time p<0>, cell r<0> bears the mark "#", and
| At the point-in-time p<0>, cell r<1> bears the mark "1", and
| At the point-in-time p<0>, cell r<2> bears the mark "#".

才~~~~~~~~才~~~~~~~~才1~TUPNI~才~~~~~~~~才~~~~~~~~

And here, yet again, just to store it nearby,
is the logical rendition of the TM's program:

才~~~~~~~~才~~~~~~~~才PROGRAM~才~~~~~~~~才~~~~~~~~

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# ))

才~~~~~~~~才~~~~~~~~才MARGORP~才~~~~~~~~才~~~~~~~~

才~~~~~~~~才~~~~~~~~才INTERPRETATION~才~~~~~~~~才~~~~~~~~

Interpretation of the Propositional Program:

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.

才~~~~~~~~才~~~~~~~~才NOITATERPRETNI~才~~~~~~~~才~~~~~~~~

And here are the outputs of the computation,
as emulated by its propositional rendition,
and as actually generated within that form
of transmogrification by the program that
I wrote for finding all of the satisfying
interpretations (truth-value assignments)
of propositional expressions in RefLog:

才~~~~~~~~才~~~~~~~~才OUTPUT~0~才~~~~~~~~才~~~~~~~~

Output Conditions:

 p0_q0
  p0_r1
   p0_r0_s#
    p0_r1_s0
     p0_r2_s#
      p1_q0
       p1_r2
        p1_r2_s#
         p1_r0_s#
          p1_r1_s0
           p2_q#
            p2_r1
             p2_r0_s#
              p2_r1_s0
               p2_r2_s#

The Output Conditions amount to the sole satisfying interpretation,
that is, a "sequence of truth-value assignments" (SOTVA) that make
the entire proposition come out true, and they state the following:

| At the point-in-time p<0>, M is in the state q<0>,       and
| At the point-in-time p<0>, H is on the cell  r<1>,       and
| At the point-in-time p<0>, cell r<0> bears the mark "#", and
| At the point-in-time p<0>, cell r<1> bears the mark "0", and
| At the point-in-time p<0>, cell r<2> bears the mark "#", and
|
| At the point-in-time p<1>, M is in the state q<0>,       and 
| At the point-in-time p<1>, H is on the cell  r<2>,       and
| At the point-in-time p<1>, cell r<0> bears the mark "#", and
| At the point-in-time p<1>, cell r<1> bears the mark "0", and
| At the point-in-time p<1>, cell r<2> bears the mark "#", and
|
| At the point-in-time p<2>, M is in the state q<#>,       and 
| At the point-in-time p<2>, H is on the cell  r<1>,       and
| At the point-in-time p<2>, cell r<0> bears the mark "#", and
| At the point-in-time p<2>, cell r<1> bears the mark "0", and
| At the point-in-time p<2>, cell r<2> bears the mark "#".

In brief, the output for our sake being the symbol that rests
under the tape-head H when the machine M gets to a rest state,
we are now amazed by the remarkable result that Parity(0) = 0.

才~~~~~~~~才~~~~~~~~才0~TUPTUO~才~~~~~~~~才~~~~~~~~

才~~~~~~~~才~~~~~~~~才OUTPUT~1~才~~~~~~~~才~~~~~~~~

Output Conditions:

 p0_q0
  p0_r1
   p0_r0_s#
    p0_r1_s1
     p0_r2_s#
      p1_q1
       p1_r2
        p1_r2_s#
         p1_r0_s#
          p1_r1_s1
           p2_q*
            p2_r1
             p2_r0_s#
              p2_r1_s1
               p2_r2_s#

The Output Conditions amount to the sole satisfying interpretation,
that is, a "sequence of truth-value assignments" (SOTVA) that make
the entire proposition come out true, and they state the following:

| At the point-in-time p<0>, M is in the state q<0>,       and
| At the point-in-time p<0>, H is on the cell  r<1>,       and
| At the point-in-time p<0>, cell r<0> bears the mark "#", and
| At the point-in-time p<0>, cell r<1> bears the mark "1", and
| At the point-in-time p<0>, cell r<2> bears the mark "#", and
|
| At the point-in-time p<1>, M is in the state q<1>,       and 
| At the point-in-time p<1>, H is on the cell  r<2>,       and
| At the point-in-time p<1>, cell r<0> bears the mark "#", and
| At the point-in-time p<1>, cell r<1> bears the mark "1", and
| At the point-in-time p<1>, cell r<2> bears the mark "#", and
|
| At the point-in-time p<2>, M is in the state q<*>,       and 
| At the point-in-time p<2>, H is on the cell  r<1>,       and
| At the point-in-time p<2>, cell r<0> bears the mark "#", and
| At the point-in-time p<2>, cell r<1> bears the mark "1", and
| At the point-in-time p<2>, cell r<2> bears the mark "#".

In brief, the output for our sake being the symbol that rests
under the tape-head H when the machine M gets to a rest state,
we are now amazed by the remarkable result that Parity(1) = 1.

才~~~~~~~~才~~~~~~~~才1~TUPTUO~才~~~~~~~~才~~~~~~~~

I am still in the process of de-tangling these
bits and pieces and odds and ends and notions
of threads, but till I do, here is a sampler
of linkages that may serve to explain a few
of the ideas that were not covered in any
suitably self-contained fashion above:

才~~~~~~~~才~~~~~~~~才REFERENCES~才~~~~~~~~才~~~~~~~~

Running Accumulation of Reference Materials:

Extensions of Logical Graphs:

http://www.virtual-earth.de/CG/cg-list/msg03351.html
http://www.virtual-earth.de/CG/cg-list/msg03352.html
http://www.virtual-earth.de/CG/cg-list/msg03353.html
http://www.virtual-earth.de/CG/cg-list/msg03354.html
http://www.virtual-earth.de/CG/cg-list/msg03376.html
http://www.virtual-earth.de/CG/cg-list/msg03379.html
http://www.virtual-earth.de/CG/cg-list/msg03381.html

In Praise of Zeroth-Order Logic:

http://ltsc.ieee.org/logs/suo/msg01406.html
http://ltsc.ieee.org/logs/suo/msg01546.html
http://ltsc.ieee.org/logs/suo/msg01561.html
http://ltsc.ieee.org/logs/suo/msg01670.html
http://ltsc.ieee.org/logs/suo/msg01966.html
http://ltsc.ieee.org/logs/suo/msg01985.html
http://ltsc.ieee.org/logs/suo/msg01988.html

Signs, Information, Logic, Inquiry:

http://ltsc.ieee.org/logs/suo/msg02534.html
http://ltsc.ieee.org/logs/suo/msg02554.html
http://ltsc.ieee.org/logs/suo/msg02570.html
http://ltsc.ieee.org/logs/suo/msg02590.html

All Liar, No Paradox:

http://ltsc.ieee.org/logs/suo/msg01739.html

Analytic Differential Ontology (ADO):

http://grouper.ieee.org/groups/ltsc/logs/ontology/msg00072.html

Shroud of Turing:

http://ltsc.ieee.org/logs/suo/msg02714.html
http://www.egroups.com/message/theory-edge/2295
http://www.virtual-earth.de/CG/cg-list/msg03669.html

Peirce's Cook's Turing:

http://www.virtual-earth.de/CG/cg-list/msg03677.html
http://stderr.org/pipermail/arisbe/2001-January/000167.html
http://semiocom.listbot.com/cgi-bin/subscriber?Act=view_message&list_id=semiocom&msg_num=673

Painted Cacti & Propositional Calculus:

http://www.egroups.com/message/theory-edge/2313
http://stderr.org/pipermail/arisbe/2001-January/000150.html

For The Sake Of The Ultimate Reckoning Graph Engine:

http://stderr.org/pipermail/arisbe/2001-January/000168.html
http://semiocom.listbot.com/cgi-bin/subscriber?Act=view_message&list_id=semiocom&msg_num=679

Where I Hang Out Most E-joyfully (WIHOME):

><> ><> ><> ><> ><> ><> ><> ><> ><> ><> ><> ><> ><>

 http://www.medialab.chalmers.se/fishcam/fish.html

<>< <>< <>< <>< <>< <>< <>< <>< <>< <>< <>< <>< <><

才~~~~~~~~才~~~~~~~~才SECNEREFER~才~~~~~~~~才~~~~~~~~

才~~~~~~~~才~~~~~~~~才NOITARTSULLI~才~~~~~~~~才~~~~~~~~

才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~

Psahmes the Scribe,
Locally, Nominally,

Jon Awbrey

Auguration Day
Year 2001 A.D.

才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~才~~~~~~~~
Received on Saturday, 20 January 2001 17:34:24 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:38 GMT