Peirce's Cook's Turing

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Arisbeans, Conceptual Graphists, RDF Loggers, SemioComrades,

Purpose Of This Note:

It is my intuition -- and being a pragmatician,
that is, not a Kantian but a Peircean thinker,
I regard my intuitions as but fallible guides --
that where there is graph-theoretic structure
there is already the potential for logic,
and in this inkling of how it may be so,
I do not think that it matters all that
much what languages we use to create
that structure, so long as it comes
to be, some how, some way, though
for sure a good language, in time,
would not be a bad idea to pursue.

From here in my wing off the ground floor (basement, maybe)
of Peirce's Edificial Graph Foundation for Practical Logic,
I will be trying to demonstrate for your RDF's edification
that my so-called "Reflective Extension of Logical Graphs",
or "RefLog" for short, which arose from nothing more daring
than applying a couple of design principles that I abduced
from Peirce's overall philosophy of "How To Do Mathematics"
to the graph-theoretical systems that he himself developed
for "Doing Logic", can actually be put to effective use in
analyzing and clarifying the computational facets of logic,
as we have presently come to cut and to cleave to them.

As one way of trying to impress you with the possibility
that RefLog, as a slight extension of the PropCalc level
of Peirce's Existential and Entitative Graphs, and thus
a close cousin to Conceptual Graphs, could actually be
employed with some measure of efficiency to accomplish
a real computational purpose, I set it to work on the
problem of translating the specs of a "stilted TM",
that is, a "space and time limited turing machine",
into the indicative form of a single proposition in
a language for representing true-or-false sentences.

But the aim of a TM, even a stilted TM, is not just
to loll around and to be admired for the beauty and
the elite elegance of its form of representation --
that would be just about as useful, in practice, as
we have of late found a "Democracy In Theory" (DIT)
to be, like some "Non-Elective Rex Officio" (NERO).

No, the aim of a TM, even a stunted TM, is to compute,
or "to take arms against a sea of troubles", and by
computing end them, perchance to put out an output.
So here is the program of the computation that was
described in its RefLog rendition on another stage:

http://lists.w3.org/Archives/Public/www-rdf-logic/2001Jan/0061.html

Just to refresh your memory about what was being computed there,
here is the input, as given by the Initial Conditions in RefLog:

¤~~~~~~~~~¤~~~~~~~~~¤~INPUT~¤~~~~~~~~~¤~~~~~~~~~¤

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

¤~~~~~~~~~¤~~~~~~~~~¤~TUPNI~¤~~~~~~~~~¤~~~~~~~~~¤

And here is the output of that computation,
as emulated in 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~¤~~~~~~~~~¤~~~~~~~~~¤

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.

¤~~~~~~~~~¤~~~~~~~~~¤~TUPTOU~¤~~~~~~~~~¤~~~~~~~~~¤

And Dat's Da Truth!

Jon Awbrey

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Received on Saturday, 20 January 2001 02:01:15 UTC