12,089
edits
Changes
Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)
Revision as of 19:04, 13 March 2009
, 19:04, 13 March 2009→Note 21: markup
:: for computing the parity of a bit string, with number of tape cells of input equal to <math>k.\!</math>
:: for computing the parity of a bit string, with number of tape cells of input equal to <math>k.\!</math>
I will follow the pattern of discussion in Herbert Wilf (1986), ''Algorithms and Complexity'', pp. 188–201, but translate his logical formalism into cactus language, which is more efficient in regard to the number of propositional clauses that are required.
I will follow the pattern of discussion in the book
pp. 188-201, but translate his logical formalism into
cactus language, which is more efficient in regard to
the number of propositional clauses that are required.
A turing machine for computing the parity of a bit string
A turing machine for computing the parity of a bit string is described by means of the following Figure and Table.
is described by means of the following Figure and Table.
<pre>
o-------------------------------------------------o
o-------------------------------------------------o
| |
| |
o-------------------------------------------------o
o-------------------------------------------------o
Figure 21-a. Parity Machine
Figure 21-a. Parity Machine
</pre>
<br>
<pre>
Table 21-b. Parity Machine
Table 21-b. Parity Machine
o-------o--------o-------------o---------o------------o
o-------o--------o-------------o---------o------------o
| 1 | # | # | -1 | * |
| 1 | # | # | -1 | * |
o-------o--------o-------------o---------o------------o
o-------o--------o-------------o---------o------------o
</pre>
The TM has a "finite automaton" (FA) as one component.
The TM has a ''finite automaton'' (FA) as one component. Let us refer to this particular FA by the name of <math>\operatorname{M}.</math>
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 ''tape head'' (that is, the ''read unit'') will be called <math>\operatorname{H}.</math> The ''registers'' are also called ''tape cells'' or ''tape squares''.
The "registers" are also called "tape-cells" or "tape-squares".
==Note 22==
==Note 22==