12,080
edits
Changes
Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)
Revision as of 20:00, 27 September 2013
, 20:00, 27 September 2013update
|+ style="height:30px" | <math>\text{Table 1.} ~~ \text{Syntax and Semantics of a Calculus for Propositional Logic}\!</math>
|+ style="height:30px" | <math>\text{Table 1.} ~~ \text{Syntax and Semantics of a Calculus for Propositional Logic}\!</math>
|- style="height:40px; background:ghostwhite"
|- style="height:40px; background:ghostwhite"
| <math>\text{Graph}\!</math>
| <math>\text{Expression}~\!</math>
| <math>\text{Expression}~\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Interpretation}\!</math>
| <math>\text{Other Notations}\!</math>
| <math>\text{Other Notations}\!</math>
|-
|-
|
| height="100px" | [[Image:Cactus Node Big Fat.jpg|20px]]
| <math>\text{True}\!</math>
| <math>~</math>
| <math>\operatorname{true}</math>
| <math>1\!</math>
| <math>1\!</math>
|-
|-
| <math>\texttt{(~)}\!</math>
| height="100px" | [[Image:Cactus Spike Big Fat.jpg|20px]]
| <math>\text{False}\!</math>
| <math>\texttt{(~)}</math>
| <math>\operatorname{false}</math>
| <math>0\!</math>
| <math>0\!</math>
|-
|-
| <math>x\!</math>
| height="100px" | [[Image:Cactus A Big.jpg|20px]]
| <math>x\!</math>
| <math>a\!</math>
| <math>x\!</math>
| <math>a\!</math>
| <math>a\!</math>
|-
|-
| <math>\texttt{(} x \texttt{)}\!</math>
| height="120px" | [[Image:Cactus (A) Big.jpg|20px]]
| <math>\text{Not}~ x\!</math>
| <math>\texttt{(} a \texttt{)}~</math>
|
| <math>\operatorname{not}~ a</math>
<math>\begin{matrix}
| <math>\lnot a \quad \bar{a} \quad \tilde{a} \quad a^\prime</math>
\tilde{x}
\\
|-
|-
| <math>x~y~z\!</math>
| height="100px" | [[Image:Cactus ABC Big.jpg|50px]]
| <math>x ~\text{and}~ y ~\text{and}~ z\!</math>
| <math>a ~ b ~ c</math>
| <math>x \land y \land z\!</math>
| <math>a ~\operatorname{and}~ b ~\operatorname{and}~ c</math>
| <math>a \land b \land c</math>
|-
|-
| <math>\texttt{((} x \texttt{)(} y \texttt{)(} z \texttt{))}\!</math>
| height="160px" | [[Image:Cactus ((A)(B)(C)) Big.jpg|65px]]
| <math>x ~\text{or}~ y ~\text{or}~ z\!</math>
| <math>\texttt{((} a \texttt{)(} b \texttt{)(} c \texttt{))}</math>
| <math>x \lor y \lor z\!</math>
| <math>a ~\operatorname{or}~ b ~\operatorname{or}~ c</math>
| <math>a \lor b \lor c</math>
|-
|-
| <math>\texttt{(} x ~ \texttt{(} y \texttt{))}\!</math>
| height="120px" | [[Image:Cactus (A(B)) Big.jpg|60px]]
| <math>\texttt{(} a \texttt{(} b \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{implies}~ b
\\
\\[6pt]
\mathrm{If}~ x ~\text{then}~ y
\operatorname{if}~ a ~\operatorname{then}~ b
\end{matrix}</math>
\end{matrix}</math>
| <math>x \Rightarrow y\!</math>
| <math>a \Rightarrow b</math>
|-
|-
| <math>\texttt{(} x \texttt{,} y \texttt{)}\!</math>
| height="120px" | [[Image:Cactus (A,B) Big ISW.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{)}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{not~equal~to}~ b
\\
\\[6pt]
a ~\operatorname{exclusive~or}~ b
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a \neq b
\\
\\[6pt]
a + b
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>\texttt{((} x \texttt{,} y \texttt{))}\!</math>
| height="160px" | [[Image:Cactus ((A,B)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{,} b \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a ~\operatorname{is~equal~to}~ b
\\
\\[6pt]
a ~\operatorname{if~and~only~if}~ b
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
a = b
\\
\\[6pt]
a \Leftrightarrow b
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>\texttt{(} x \texttt{,} y \texttt{,} z \texttt{)}\!</math>
| height="120px" | [[Image:Cactus (A,B,C) Big.jpg|65px]]
| <math>\texttt{(} a \texttt{,} b \texttt{,} c \texttt{)}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\text{Just one of}
\operatorname{just~one~of}
\\
\\
a, b, c
\\
\\
\text{is false}.
\operatorname{is~false}.
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& \bar{a} ~ b ~ c
\\
\\
\lor & a ~ \bar{b} ~ c
\\
\\
\lor & a ~ b ~ \bar{c}
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| <math>\texttt{((} x \texttt{),(} y \texttt{),(} z \texttt{))}\!</math>
| height="160px" | [[Image:Cactus ((A),(B),(C)) Big.jpg|65px]]
| <math>\texttt{((} a \texttt{),(} b \texttt{),(} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\text{Just one of}
\operatorname{just~one~of}
\\
\\
a, b, c
\\
\\
\text{Partition all}
\operatorname{is~true}.
\\[6pt]
\operatorname{partition~all}
\\
\\
\text{into}~ x, y, z.
\operatorname{into}~ a, b, c.
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& a ~ \bar{b} ~ \bar{c}
\\
\\
\lor & \bar{a} ~ b ~ \bar{c}
\\
\\
\lor & \bar{a} ~ \bar{b} ~ c
\end{matrix}</math>
\end{matrix}</math>
|-
|-
| height="160px" | [[Image:Cactus (A,(B,C)) Big.jpg|90px]]
| <math>\texttt{(} a \texttt{,(} b \texttt{,} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\texttt{((} x \texttt{,} y \texttt{),} z \texttt{)}
\operatorname{oddly~many~of}
\\
\\
a, b, c
\\
\\
\texttt{(} x \texttt{,(} y \texttt{,} z \texttt{))}
\operatorname{are~true}.
\end{matrix}</math>
\end{matrix}\!</math>
|
|
<p><math>x + y + z\!</math></p>
<p><math>a + b + c\!</math></p>
<br>
<br>
<p><math>\begin{matrix}
<p><math>\begin{matrix}
& a ~ b ~ c
\\
\\
\lor & a ~ \bar{b} ~ \bar{c}
\\
\\
\lor & \bar{a} ~ b ~ \bar{c}
\\
\\
\lor & \bar{a} ~ \bar{b} ~ c
\end{matrix}\!</math></p>
\end{matrix}</math></p>
|-
|-
| <math>\texttt{(} w \texttt{,(} x \texttt{),(} y \texttt{),(} z \texttt{))}\!</math>
| height="160px" | [[Image:Cactus (X,(A),(B),(C)) Big.jpg|90px]]
| <math>\texttt{(} x \texttt{,(} a \texttt{),(} b \texttt{),(} c \texttt{))}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
\text{Partition}~ w
\operatorname{partition}~ x
\\
\\
\text{into}~ x, y, z.
\operatorname{into}~ a, b, c.
\\[6pt]
\operatorname{genus}~ x ~\operatorname{comprises}
\\
\\
\operatorname{species}~ a, b, c.
\\
\end{matrix}</math>
\end{matrix}</math>
|
|
<math>\begin{matrix}
<math>\begin{matrix}
& \bar{x} ~ \bar{a} ~ \bar{b} ~ \bar{c}
\\
\\
\lor & x ~ a ~ \bar{b} ~ \bar{c}
\\
\\
\lor & x ~ \bar{a} ~ b ~ \bar{c}
\\
\\
\lor & x ~ \bar{a} ~ \bar{b} ~ c
\end{matrix}</math>
\end{matrix}</math>
|}
|}
A sketch of this work is presented in the following series of Figures, where each logical proposition is expanded over the basic cells <math>uv, u \texttt{(} v \texttt{)}, \texttt{(} u \texttt{)} v, \texttt{(} u \texttt{)(} v \texttt{)}\!</math> of the 2-dimensional universe of discourse <math>U^\bullet = [u, v].\!</math>
A sketch of this work is presented in the following series of Figures, where each logical proposition is expanded over the basic cells <math>uv, u \texttt{(} v \texttt{)}, \texttt{(} u \texttt{)} v, \texttt{(} u \texttt{)(} v \texttt{)}\!</math> of the 2-dimensional universe of discourse <math>U^\bullet = [u, v].\!</math>
===Computation Summary : <math>f(u, v) = \texttt{((u)(v))}</math>===
===Computation Summary for Logical Disjunction===
The venn diagram in Figure 1.1 shows how the proposition <math>f = \texttt{((u)(v))}</math> can be expanded over the universe of discourse <math>[u, v]\!</math> to produce a logically equivalent exclusive disjunction, namely, <math>\texttt{uv~+~u(v)~+~(u)v}.</math>
The venn diagram in Figure 1.1 shows how the proposition <math>f = \texttt{((} u \texttt{)(} v \texttt{))}\!</math> can be expanded over the universe of discourse <math>[u, v]\!</math> to produce a logically equivalent exclusive disjunction, namely, <math>uv + u \texttt{(} v \texttt{)} + \texttt{(} u \texttt{)} v.\!</math>
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
Figure 1.2 expands <math>\mathrm{E}f = \texttt{((u + du)(v + dv))}</math> over <math>[u, v]\!</math> to give:
Figure 1.2 expands <math>\mathrm{E}f = \texttt{((} u + \mathrm{d}u \texttt{)(} v + \mathrm{d}v \texttt{))}\!</math> over <math>[u, v]\!</math> to give:
{| align="center" cellpadding="8" width="90%"
{| align="center" cellpadding="8"
| <math>\texttt{uv~(du~dv) ~+~ u(v)~(du (dv)) ~+~ (u)v~((du) dv) ~+~ (u)(v)~((du)(dv))}</math>
|
<math>\begin{matrix}
\mathrm{E}\texttt{((} u \texttt{)(} v \texttt{))}
& = & uv \cdot \texttt{(} \mathrm{d}u ~ \mathrm{d}v \texttt{)}
& + & u \texttt{(} v \texttt{)} \cdot \texttt{(} \mathrm{d}u \texttt{(} \mathrm{d}v \texttt{))}
& + & \texttt{(} u \texttt{)} v \cdot \texttt{((} \mathrm{d}u \texttt{)} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)(} v \texttt{)} \cdot \texttt{((} \mathrm{d}u \texttt{)(} \mathrm{d}v \texttt{))}
\end{matrix}</math>
|}
|}
|}
|}
Figure 1.3 expands <math>\mathrm{D}f = f + \mathrm{E}f</math> over <math>[u, v]\!</math> to produce:
Figure 1.3 expands <math>\mathrm{D}f = f + \mathrm{E}f\!</math> over <math>[u, v]\!</math> to produce:
{| align="center" cellpadding="8" width="90%"
{| align="center" cellpadding="8"
| <math>\texttt{uv~du~dv ~+~ u(v)~du(dv) ~+~ (u)v~(du)dv ~+~ (u)(v)~((du)(dv))}</math>
|
<math>\begin{matrix}
\mathrm{D}\texttt{((} u \texttt{)(} v \texttt{))}
& = & uv \cdot \mathrm{d}u ~ \mathrm{d}v
& + & u \texttt{(} v \texttt{)} \cdot \mathrm{d}u \texttt{(} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)} v \cdot \texttt{(} \mathrm{d}u \texttt{)} \mathrm{d}v
& + & \texttt{(} u \texttt{)(} v \texttt{)} \cdot \texttt{((} \mathrm{d}u \texttt{)(} \mathrm{d}v \texttt{))}
\end{matrix}</math>
|}
|}
I'll break this here in case anyone wants to try and do the work for <math>g\!</math> on their own.
I'll break this here in case anyone wants to try and do the work for <math>g\!</math> on their own.
===Computation Summary : <math>g(u, v) = \texttt{((u,~v))}</math>===
===Computation Summary for Logical Equality===
The venn diagram in Figure 2.1 shows how the proposition <math>g = \texttt{((u,~v))}</math> can be expanded over the universe of discourse <math>[u, v]\!</math> to produce a logically equivalent exclusive disjunction, namely, <math>\texttt{uv ~+~ (u)(v)}.</math>
The venn diagram in Figure 2.1 shows how the proposition <math>g = \texttt{((} u \texttt{,~} v \texttt{))}\!</math> can be expanded over the universe of discourse <math>[u, v]\!</math> to produce a logically equivalent exclusive disjunction, namely, <math>uv + \texttt{(} u \texttt{)(} v \texttt{)}.\!</math>
{| align="center" border="0" cellpadding="10"
{| align="center" border="0" cellpadding="10"
|}
|}
Figure 2.2 expands <math>\mathrm{E}g = \texttt{((u + du,~v + dv))}</math> over <math>[u, v]\!</math> to give:
Figure 2.2 expands <math>\mathrm{E}g = \texttt{((} u + \mathrm{d}u \texttt{,~} v + \mathrm{d}v \texttt{))}\!</math> over <math>[u, v]\!</math> to give:
{| align="center" cellpadding="8" width="90%"
{| align="center" cellpadding="8"
| <math>\texttt{uv~((du,~dv)) ~+~ u(v)~(du,~dv) ~+~ (u)v~(du,~dv) ~+~ (u)(v)~((du,~dv))}</math>
|
<math>\begin{matrix}
\mathrm{E}\texttt{((} u \texttt{,~} v \texttt{))}
& = & uv \cdot \texttt{((} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{))}
& + & u \texttt{(} v \texttt{)} \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)} v \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)(} v \texttt{)} \cdot \texttt{((} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{))}
\end{matrix}</math>
|}
|}
|}
|}
Figure 2.3 expands <math>\mathrm{D}g = g + \mathrm{E}g</math> over <math>[u, v]\!</math> to yield the form:
Figure 2.3 expands <math>\mathrm{D}g = g + \mathrm{E}g\!</math> over <math>[u, v]\!</math> to yield the form:
{| align="center" cellpadding="8" width="90%"
{| align="center" cellpadding="8"
| <math>\texttt{uv~(du,~dv) ~+~ u(v)~(du,~dv) ~+~ (u)v~(du,~dv) ~+~ (u)(v)~(du,~dv)}\!</math>
|
<math>\begin{matrix}
\mathrm{D}\texttt{((} u \texttt{,~} v \texttt{))}
& = & uv \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
& + & u \texttt{(} v \texttt{)} \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)} v \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
& + & \texttt{(} u \texttt{)(} v \texttt{)} \cdot \texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}
\end{matrix}</math>
|}
|}
|
|
<math>\begin{array}{lllll}
<math>\begin{array}{lllll}
F & = & (f, g) & = & ( ~\texttt{((u)(v))}~ , ~\texttt{((u,~v))}~ ).
F
& = & (f, g)
& = & ( ~ \texttt{((} u \texttt{)(} v \texttt{))} ~,~ \texttt{((} u \texttt{,~} v \texttt{))} ~ )
\end{array}</math>
\end{array}</math>
|}
|}
To speed things along, I will skip a mass of motivating discussion and just exhibit the simplest form of a differential <math>\mathrm{d}F\!</math> for the current example of a logical transformation <math>F,\!</math> after which the majority of the easiest questions will have been answered in visually intuitive terms.
To speed things along, I will skip a mass of motivating discussion and just exhibit the simplest form of a differential <math>\mathrm{d}F\!</math> for the current example of a logical transformation <math>F,\!</math> after which the majority of the easiest questions will have been answered in visually intuitive terms.
For <math>F = (f, g)\!</math> we have <math>\mathrm{d}F = (\mathrm{d}f, \mathrm{d}g),</math> and so we can proceed componentwise, patching the pieces back together at the end.
For <math>F = (f, g)\!</math> we have <math>\mathrm{d}F = (\mathrm{d}f, \mathrm{d}g),\!</math> and so we can proceed componentwise, patching the pieces back together at the end.
We have prepared the ground already by computing these terms:
We have prepared the ground already by computing these terms:
|
|
<math>\begin{array}{lll}
<math>\begin{array}{lll}
\mathrm{E}f & = & \texttt{(( u + du )( v + dv ))}
\mathrm{E}f & = & \texttt{((} u + \mathrm{d}u \texttt{)(} v + \mathrm{d}v \texttt{))}
\\ \\
\\[8pt]
\mathrm{E}g & = & \texttt{(( u + du ,~ v + dv ))}
\mathrm{E}g & = & \texttt{((} u + \mathrm{d}u \texttt{,~} v + \mathrm{d}v \texttt{))}
\\ \\
\\[8pt]
\mathrm{D}f & = & \texttt{((u)(v)) ~+~ (( u + du )( v + dv ))}
\mathrm{D}f & = & \texttt{((} u \texttt{)(} v \texttt{))} ~+~ \texttt{((} u + \mathrm{d}u \texttt{)(} v + \mathrm{d}v \texttt{))}
\\ \\
\\[8pt]
\mathrm{D}g & = & \texttt{((u,~v)) ~+~ (( u + du ,~ v + dv ))}
\mathrm{D}g & = & \texttt{((} u \texttt{,~} v \texttt{))} ~+~ \texttt{((} u + \mathrm{d}u \texttt{,~} v + \mathrm{d}v \texttt{))}
\end{array}\!</math>
\end{array}</math>
|}
|}
As a matter of fact, computing the symmetric differences <math>\mathrm{D}f = f + \mathrm{E}f</math> and <math>\mathrm{D}g = g + \mathrm{E}g</math> has already taken care of the ''localizing'' part of the task by subtracting out the forms of <math>f\!</math> and <math>g\!</math> from the forms of <math>\mathrm{E}f</math> and <math>\mathrm{E}g,</math> respectively. Thus all we have left to do is to decide what linear propositions best approximate the difference maps <math>\mathrm{D}f</math> and <math>\mathrm{D}g,</math> respectively.
As a matter of fact, computing the symmetric differences <math>\mathrm{D}f = f + \mathrm{E}f\!</math> and <math>\mathrm{D}g = g + \mathrm{E}g\!</math> has already taken care of the ''localizing'' part of the task by subtracting out the forms of <math>f\!</math> and <math>g\!</math> from the forms of <math>\mathrm{E}f\!</math> and <math>\mathrm{E}g,\!</math> respectively. Thus all we have left to do is to decide what linear propositions best approximate the difference maps <math>{\mathrm{D}f}\!</math> and <math>{\mathrm{D}g},\!</math> respectively.
This raises the question: What is a linear proposition?
This raises the question: What is a linear proposition?
The answer that makes the most sense in this context is this: A proposition is just a boolean-valued function, so a linear proposition is a linear function into the boolean space <math>\mathbb{B}.</math>
The answer that makes the most sense in this context is this: A proposition is just a boolean-valued function, so a linear proposition is a linear function into the boolean space <math>\mathbb{B}.\!</math>
In particular, the linear functions that we want will be linear functions in the differential variables <math>du\!</math> and <math>dv.\!</math>
In particular, the linear functions that we want will be linear functions in the differential variables <math>\mathrm{d}u\!</math> and <math>\mathrm{d}v.\!</math>
As it turns out, there are just four linear propositions in the associated ''differential universe'' <math>\mathrm{d}U^\bullet = [du, dv],</math> and these are the propositions that are commonly denoted: <math>\texttt{0}, \texttt{du}, \texttt{dv}, \texttt{du + dv},</math> in other words, <math>\texttt{()}, \texttt{du}, \texttt{dv}, \texttt{(du, dv)}.</math>
As it turns out, there are just four linear propositions in the associated ''differential universe'' <math>\mathrm{d}U^\bullet = [\mathrm{d}u, \mathrm{d}v].\!</math> These are the propositions that are commonly denoted: <math>{0, ~\mathrm{d}u, ~\mathrm{d}v, ~\mathrm{d}u + \mathrm{d}v},\!</math> in other words: <math>\texttt{(~)}, ~\mathrm{d}u, ~\mathrm{d}v, ~\texttt{(} \mathrm{d}u \texttt{,~} \mathrm{d}v \texttt{)}.\!</math>
==Notions of Approximation==
==Notions of Approximation==