12,080
edits
Changes
Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)
Revision as of 15:30, 11 October 2013
, 15:30, 11 October 2013update
3 & 1 & 0 & 0 \\
3 & 1 & 0 & 0 \\
4 & 1 & 0 & 0 \\
4 & 1 & 0 & 0 \\
5 & {}^{\shortparallel} & {}^{\shortparallel} & {}^{\shortparallel}
5 & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel
\end{array}</math>
\end{array}</math>
|}
|}
3 & 1 & 0 & 0 \\
3 & 1 & 0 & 0 \\
4 & 1 & 0 & 0 \\
4 & 1 & 0 & 0 \\
5 & {}^{\shortparallel} & {}^{\shortparallel} & {}^{\shortparallel}
5 & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel
\end{array}</math>
\end{array}</math>
|}
|}
==Visualization==
==Visualization==
In my work on [[Differential Logic and Dynamic Systems 2.0|Differential Logic and Dynamic Systems]], I found it useful to develop several different ways of visualizing logical transformations, indeed, I devised four distinct styles of picture for the job. Thus far in our work on the mapping <math>F : [u, v] \to [u, v],\!</math> we've been making use of what I call the ''areal view'' of the extended universe of discourse, <math>[u, v, du, dv],\!</math> but as the number of dimensions climbs beyond four, it's time to bid this genre adieu, and look for a style that can scale a little better. At any rate, before we proceed any further, let's first assemble the information that we have gathered about <math>F\!</math> from several different angles, and see if it can be fitted into a coherent picture of the transformation <math>F : (u, v) \mapsto ( ~\texttt{((u)(v))}~, ~\texttt{((u, v))}~ ).</math>
In my work on [[Differential Logic and Dynamic Systems 2.0|Differential Logic and Dynamic Systems]], I found it useful to develop several different ways of visualizing logical transformations, indeed, I devised four distinct styles of picture for the job. Thus far in our work on the mapping <math>F : [u, v] \to [u, v],\!</math> we've been making use of what I call the ''areal view'' of the extended universe of discourse, <math>[u, v, \mathrm{d}u, \mathrm{d}v],\!</math> but as the number of dimensions climbs beyond four, it's time to bid this genre adieu and look for a style that can scale a little better. At any rate, before we proceed any further, let's first assemble the information that we have gathered about <math>F\!</math> from several different angles, and see if it can be fitted into a coherent picture of the transformation <math>F : (u, v) \mapsto ( ~ \texttt{((} u \texttt{)(} v \texttt{))} ~,~ \texttt{((} u \texttt{,~} v \texttt{))} ~ ).\!</math>
In our first crack at the transformation <math>F,\!</math> we simply plotted the state transitions and applied the utterly stock technique of calculating the finite differences.
In our first crack at the transformation <math>F,\!</math> we simply plotted the state transitions and applied the utterly stock technique of calculating the finite differences.
|
|
<math>\begin{array}{c|cc|cc|}
<math>\begin{array}{c|cc|cc|}
t & u & v & du & dv \\[8pt]
t & u & v & \mathrm{d}u & \mathrm{d}v \\[8pt]
0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 \\
1 & '' & '' & '' & '' \\
1 & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel
\end{array}</math>
\end{array}</math>
|}
|}
A quick inspection of the first Table suggests a rule to cover the case when <math>\texttt{u~=~v~=~1},</math> namely, <math>\texttt{du~=~dv~=~0}.</math> To put it another way, the Table characterizes Orbit 1 by means of the data: <math>(u, v, du, dv) = (1, 1, 0, 0).\!</math> Another way to convey the same information is by means of the extended proposition: <math>\texttt{u~v~(du)(dv)}.</math>
A quick inspection of the first Table suggests a rule to cover the case when <math>u = v = 1,\!</math> namely, <math>\mathrm{d}u = \mathrm{d}v = 0.\!</math> To put it another way, the Table characterizes Orbit 1 by means of the data: <math>(u, v, \mathrm{d}u, \mathrm{d}v) = (1, 1, 0, 0).\!</math> Another way to convey the same information is by means of the extended proposition: <math>u v \texttt{(} \mathrm{d}u \texttt{)(} \mathrm{d}v \texttt{)}.\!</math>
{| align="center" cellpadding="8" style="text-align:center"
{| align="center" cellpadding="8" style="text-align:center"
|
|
<math>\begin{array}{c|cc|cc|cc|}
<math>\begin{array}{c|cc|cc|cc|}
t & u & v & du & dv & d^2 u & d^2 v \\[8pt]
t & u & v & \mathrm{d}u & \mathrm{d}v & \mathrm{d}^2 u & \mathrm{d}^2 v \\[8pt]
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 \\
2 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 0 & 0 & 0 & 0 & 0 \\
3 & '' & '' & '' & '' & '' & '' \\
3 & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel & {}^\shortparallel
\end{array}</math>
\end{array}</math>
|}
|}
A more fine combing of the second Table brings to mind a rule that partly covers the remaining cases, that is, <math>\texttt{du~=~v}, ~\texttt{dv~=~(u)}.</math> This much information about Orbit 2 is also encapsulated by the extended proposition, <math>\texttt{(uv)((du, v))(dv, u)},</math> which says that <math>u\!</math> and <math>v\!</math> are not both true at the same time, while <math>du\!</math> is equal in value to <math>v\!</math> and <math>dv\!</math> is opposite in value to <math>u.\!</math>
A more fine combing of the second Table brings to mind a rule that partly covers the remaining cases, that is, <math>\mathrm{d}u = v, ~ \mathrm{d}v = \texttt{(} u \texttt{)}.\!</math> This much information about Orbit 2 is also encapsulated by the extended proposition <math>\texttt{(} uv \texttt{)((} \mathrm{d}u \texttt{,} v \texttt{))(} \mathrm{d}v, u \texttt{)},\!</math> which says that <math>u\!</math> and <math>v\!</math> are not both true at the same time, while <math>\mathrm{d}u\!</math> is equal in value to <math>v\!</math> and <math>\mathrm{d}v\!</math> is opposite in value to <math>u.\!</math>
==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.
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.
{| 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>
| |
| 1/1/+1 |
| /\ / \ /\ |
Figure 21-a. Parity Machine
</pre>
|}
|}
|
|
<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 |
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>
==Document History==
==Document History==
* 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