Editing User:Anisomorphism (section)

= Algebraic Geometry of Computing =
Finite state machines appear in a variety of instantiations: mechanical, electronic, fluidic. The physical mechanisms involved necessitate that the design is described by differential equations, but ultimately the manipulation of abstracted "logical" states is the final goal. Thus we can describe the architecture of a general finite state machine with <math> \mathbb{Z}/2\mathbb{Z} </math> algebra (or other finite rings too).
=== Gates ===
Typically you will see a logic gate defined by its values on all combinations of inputs as a "truth table":
{| class="wikitable" style="margin:auto"
|+ AND
|-
! x !! y !! x AND y = AND(x,y)
|-
| 0 || 0 || 0
|-
| 0 || 1 || 0
|-
| 1 || 0 || 0
|-
| 1 || 1 || 1
|}
And statements written with logical connectives: <math> (x\and y)\or z = OR(AND(x,y),z) </math> 
<br>
Along with distributive laws: <math> (x\and y)\or z = (x\or z)\and(y\or z) </math>, <math> (x\or y)\and z = (x\and z)\or(y\and z) </math>
<br>
De Morgan's laws: <math> \neg(x\and y) = (\neg x)\or (\neg y) </math>, <math> \neg(x\or y) = (\neg x)\and (\neg y) </math>
<br>
All of which apply to more complicated sentences rather than just individual variables. These laws along with commutative and associative laws are sufficient to evaluate and simplify any general logical expression, however we contend that this is the wrong language for computing and makes other important aspects - the dynamics and algebra - obscure. 
<br>
There is one thing we can extract from logical connectives before moving on. The disjunctive normal form allows us to read truth tables and directly translate them into connective formulae which we can use later. Let us look at a different example which will help us escape the artificiality of AND and OR.
{| class="wikitable" style="margin:auto"
|+ XOR
|-
! x !! y !! XOR(x,y)
|-
| 0 || 0 || 0
|-
| 0 || 1 || 1
|-
| 1 || 0 || 1
|-
| 1 || 1 || 0
|}
XOR is only "true" or 1 when x or y but not both, are 1. Disjunctive normal form says that we can view the x, y entries as unary operators which return the input with no change, combine these as given on the lines which evaluate to 1, and take the OR of all of them for the total connective form of the truth table. Here is the third line: <math> x\and\neg y</math>. 
<br> The total is:
<math>
\begin{align*}
&(x\and\neg y)\or (\neg x\and y) \\
=&(x\or(\neg x\and y))\and(\neg y\or(\neg x\and y)) \\
=&(x\or\neg x)\and (x\or y)\and(\neg y\or\neg x)\and(\neg y\or y) \\
=&(x\or y)\and (\neg y\or\neg x) \\
=&(x\or y)\and\neg (y\and x)
\end{align*}
</math> 
<br>
This process can be viewed as a sum of "elementary functions" which are only 1 on one line each, and building a general function/table.