Changes

Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)

Revision as of 14:38, 13 March 2009

No change in size , 14:38, 13 March 2009

→‎Note 21: markup

Line 1,767: Line 1,767:

==Note 21==

+

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.

<pre>

−

~~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.~~

−

Notation:

Jon Awbrey

12,089

edits