| Line 1,953: |
Line 1,953: |
| | | | |
| | ==Turing Machine Example== | | ==Turing Machine Example== |
| | + | |
| | + | <font size="3">☞</font> 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 that I will describe in more detail as we proceed. | | 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 that I will describe in more detail as we proceed. |
| Line 1,968: |
Line 1,970: |
| | A turing machine for computing the parity of a bit string is described by means of the following Figure and Table. | | A turing machine for computing the parity of a bit string is described by means of the following Figure and Table. |
| | | | |
| − | <br>
| + | {| align="center" border="0" cellspacing="10" style="text-align:center; width:100%" |
| − | | + | | [[Image:Parity_Machine.jpg|400px]] |
| − | {| align="center" border="0" cellpadding="10" | + | |- |
| − | |
| + | | height="20px" valign="top" | <math>\text{Figure 3.} ~~ \text{Parity Machine}\!</math> |
| − | <pre>
| |
| − | o-------------------------------------------------o
| |
| − | | | | |
| − | | 1/1/+1 | | |
| − | | --------> |
| |
| − | | /\ / \ /\ | | |
| − | | 0/0/+1 ^ 0 1 ^ 0/0/+1 |
| |
| − | | \/|\ /|\/ |
| |
| − | | | <-------- | |
| |
| − | | #/#/-1 | 1/1/+1 | #/#/-1 |
| |
| − | | | | |
| |
| − | | v v |
| |
| − | | # * |
| |
| − | | |
| |
| − | o-------------------------------------------------o
| |
| − | Figure 21-a. Parity Machine | |
| − | </pre> | |
| | |} | | |} |
| | | | |
| Line 1,996: |
Line 1,981: |
| | | | | | |
| | <pre> | | <pre> |
| − | Table 21-b. Parity Machine | + | Table 4. Parity Machine |
| | o-------o--------o-------------o---------o------------o | | o-------o--------o-------------o---------o------------o |
| | | State | Symbol | Next Symbol | Ratchet | Next State | | | | State | Symbol | Next Symbol | Ratchet | Next State | |
| Line 2,894: |
Line 2,879: |
| | | | |
| | The output of <math>\mathrm{Stunt}(2)</math> being the symbol that rests under the tape head <math>\mathrm{H}</math> when and if the machine <math>\mathrm{M}</math> reaches one of its resting states, we get the result that <math>\mathrm{Parity}(1) = 1.</math> | | The output of <math>\mathrm{Stunt}(2)</math> being the symbol that rests under the tape head <math>\mathrm{H}</math> when and if the machine <math>\mathrm{M}</math> reaches one of its resting states, we get the result that <math>\mathrm{Parity}(1) = 1.</math> |
| − |
| |
| − | ==Work Area==
| |
| − |
| |
| − | <pre>
| |
| − | DATA 20. http://forum.wolframscience.com/showthread.php?postid=791#post791
| |
| − |
| |
| − | Let's see how this information about the transformation F,
| |
| − | arrived at by eyeballing the raw data, comports with what
| |
| − | we derived through a more systematic symbolic computation.
| |
| − |
| |
| − | The results of the various operator actions that we have just
| |
| − | computed are summarized in Tables 66-i and 66-ii from my paper,
| |
| − | and I have attached these as a text file below.
| |
| − |
| |
| − | Table 66-i. Computation Summary for f<u, v> = ((u)(v))
| |
| − | o--------------------------------------------------------------------------------o
| |
| − | | |
| |
| − | | !e!f = uv. 1 + u(v). 1 + (u)v. 1 + (u)(v). 0 |
| |
| − | | |
| |
| − | | Ef = uv. (du dv) + u(v). (du (dv)) + (u)v.((du) dv) + (u)(v).((du)(dv)) |
| |
| − | | |
| |
| − | | Df = uv. du dv + u(v). du (dv) + (u)v. (du) dv + (u)(v).((du)(dv)) |
| |
| − | | |
| |
| − | | df = uv. 0 + u(v). du + (u)v. dv + (u)(v). (du, dv) |
| |
| − | | |
| |
| − | | rf = uv. du dv + u(v). du dv + (u)v. du dv + (u)(v). du dv |
| |
| − | | |
| |
| − | o--------------------------------------------------------------------------------o
| |
| − |
| |
| − | Table 66-ii. Computation Summary for g<u, v> = ((u, v))
| |
| − | o--------------------------------------------------------------------------------o
| |
| − | | |
| |
| − | | !e!g = uv. 1 + u(v). 0 + (u)v. 0 + (u)(v). 1 |
| |
| − | | |
| |
| − | | Eg = uv.((du, dv)) + u(v). (du, dv) + (u)v. (du, dv) + (u)(v).((du, dv)) |
| |
| − | | |
| |
| − | | Dg = uv. (du, dv) + u(v). (du, dv) + (u)v. (du, dv) + (u)(v). (du, dv) |
| |
| − | | |
| |
| − | | dg = uv. (du, dv) + u(v). (du, dv) + (u)v. (du, dv) + (u)(v). (du, dv) |
| |
| − | | |
| |
| − | | rg = uv. 0 + u(v). 0 + (u)v. 0 + (u)(v). 0 |
| |
| − | | |
| |
| − | o--------------------------------------------------------------------------------o
| |
| − |
| |
| − |
| |
| − | o---------------------------------------o
| |
| − | | |
| |
| − | | o |
| |
| − | | / \ |
| |
| − | | / \ |
| |
| − | | / \ |
| |
| − | | o o |
| |
| − | | / \ / \ |
| |
| − | | / \ / \ |
| |
| − | | / \ / \ |
| |
| − | | o o o |
| |
| − | | / \ / \ / \ |
| |
| − | | / \ / \ / \ |
| |
| − | | / \ / \ / \ |
| |
| − | | o o o o |
| |
| − | | / \ / \ / \ / \ |
| |
| − | | / \ / \ / \ / \ |
| |
| − | | / \ / \ / \ / \ |
| |
| − | | o o o o o |
| |
| − | | |\ / \ / \ / \ /| |
| |
| − | | | \ / \ / \ / \ / | |
| |
| − | | | \ / \ / \ / \ / | |
| |
| − | | | o o o o | |
| |
| − | | | |\ / \ / \ /| | |
| |
| − | | | | \ / \ / \ / | | |
| |
| − | | | u | \ / \ / \ / | v | |
| |
| − | | o---+---o o o---+---o |
| |
| − | | | \ / \ / | |
| |
| − | | | \ / \ / | |
| |
| − | | | du \ / \ / dv | |
| |
| − | | o-------o o-------o |
| |
| − | | \ / |
| |
| − | | \ / |
| |
| − | | \ / |
| |
| − | | o |
| |
| − | | |
| |
| − | o---------------------------------------o
| |
| − | </pre>
| |
| − |
| |
| − | ==Discussion==
| |
| − |
| |
| − | <pre>
| |
| − | PD = Philip Dutton
| |
| − |
| |
| − | PD: I've been watching your posts.
| |
| − |
| |
| − | PD: I am not an expert on logic infrastructures but I find the posts
| |
| − | interesting (despite not understanding much of it). I am like
| |
| − | the diagrams. I have recently been trying to understand CA's
| |
| − | using a particular perspective: sinks and sources. I think
| |
| − | that all CA's are simply combinations of sinks and sources.
| |
| − | How they interact (or intrude into each other's domains)
| |
| − | would most likely be a result of the rules (and initial
| |
| − | configuration of on or off cells).
| |
| − |
| |
| − | PD: Anyway, to be short, I "see" diamond shapes quite often in
| |
| − | your diagrams. Triangles (either up or down) or diamonds
| |
| − | (combination of an up and down triangle) make me think
| |
| − | soley of sinks and sources. I think of the diamond to
| |
| − | be a source which, during the course of progression,
| |
| − | is expanding (because it is producing) and then starts
| |
| − | to act as a sink (because it consumes) -- and hence the
| |
| − | diamond. I can't stop thinking about sinks and sources in
| |
| − | CA's and so I thought I would ask you if there is some way
| |
| − | to tie the two worlds together (CA's of sinks and sources
| |
| − | together with your differential constructs).
| |
| − |
| |
| − | PD: Any thoughts?
| |
| − |
| |
| − | Yes, I'm hoping that there's a lot of stuff analogous to
| |
| − | R-world dynamics to be discovered in this B-world variety,
| |
| − | indeed, that's kind of why I set out on this investigation --
| |
| − | oh, gee, has it been that long? -- I guess about 1989 or so,
| |
| − | when I started to see this "differential logic" angle on what
| |
| − | I had previously studied in systems theory as the "qualitative
| |
| − | approach to differential equations". I think we used to use the
| |
| − | words "attractor" and "basin" more often than "sink", but a source
| |
| − | is still a source as time goes by, and I do remember using the word
| |
| − | "sink" a lot when I was a freshperson in physics, before I got logic.
| |
| − |
| |
| − | I have spent the last 15 years doing a funny mix of practice in stats
| |
| − | and theory in math, but I did read early works by Von Neumann, Burks,
| |
| − | Ulam, and later stuff by Holland on CA's. Still, it may be a while
| |
| − | before I have re-heated my concrete intuitions about them in the
| |
| − | NKS way of thinking.
| |
| − |
| |
| − | There are some fractal-looking pictures that emerge when
| |
| − | I turn to "higher order propositional expressions" (HOPE's).
| |
| − | I have discussed this topic elswhere on the web and can look
| |
| − | it up now if your are interested, but I am trying to make my
| |
| − | e-positions somewhat clearer for the NKS forum than I have
| |
| − | tried to do before.
| |
| − |
| |
| − | But do not hestitate to dialogue all this stuff on the boards,
| |
| − | as that's what always seems to work the best. What I've found
| |
| − | works best for me, as I can hardly remember what I was writing
| |
| − | last month without Google, is to archive a copy at one of the
| |
| − | other Google-visible discussion lists that I'm on at present.
| |
| − | </pre>
| |
| | | | |
| | ==Document History== | | ==Document History== |
| Line 3,069: |
Line 2,910: |
| | * http://forum.wolframscience.com/archive/topic/228-1.html | | * http://forum.wolframscience.com/archive/topic/228-1.html |
| | * http://forum.wolframscience.com/showthread.php?threadid=228 | | * http://forum.wolframscience.com/showthread.php?threadid=228 |
| − | * http://forum.wolframscience.com/printthread.php?threadid=228&perpage=33 | + | * http://forum.wolframscience.com/printthread.php?threadid=228&perpage=50 |
| | # http://forum.wolframscience.com/showthread.php?postid=664#post664 | | # http://forum.wolframscience.com/showthread.php?postid=664#post664 |
| | # http://forum.wolframscience.com/showthread.php?postid=666#post666 | | # http://forum.wolframscience.com/showthread.php?postid=666#post666 |
