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>

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
*