12,089
edits
Changes
Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)
Revision as of 18:40, 13 March 2009
, 18:40, 13 March 2009→Note 21: markup
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.
<pre>
:; <math>\operatorname{Stilt}(k) =</math>
:: '''Space and time limited turing machine''',
:: with <math>k\!</math> units of space and <math>k\!</math> units of time.
:; <math>\operatorname{Stunt}(k) =</math>
:: '''Space and time limited turing machine''',
:: for computing the parity of a bit string, with number of tape cells of input equal to <math>k.\!</math>
<pre>
I will follow the pattern of discussion in the book
I will follow the pattern of discussion in the book
by Herbert Wilf, 'Algorithms and Complexity' (1986),
by Herbert Wilf, 'Algorithms and Complexity' (1986),