Differential Analytic Turing Automata

Post   : Differential Analytic Turing Automata : 1
URL    : http://inquiryintoinquiry.com/2013/10/14/differential-analytic-turing-automata-1/
Posted : October 14, 2013 at 10:24 am
Author : Jon Awbrey

Re: Proving Cook's Theorem
At: http://rjlipton.wordpress.com/2013/10/10/proving-cooks-theorem/

Synchronicity Rules❢

I just started reworking an old exposition of mine on Cook's Theorem, where I borrowed the
Parity Function example from Wilf (1986), ''Algorithms and Complexity'', and translated it
into the cactus graph syntax for propositional calculus that I developed as an extension of
Peirce's logical graphs.

☞ Turing Machine Example
☞ http://intersci.ss.uci.edu/wiki/index.php/Differential_Analytic_Turing_Automata#Turing_Machine_Example

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

-- 

academia: http://independent.academia.edu/JonAwbrey
my word press blog: http://inquiryintoinquiry.com/
inquiry list: http://stderr.org/pipermail/inquiry/
mwb: http://www.mywikibiz.com/Directory:Jon_Awbrey
oeiswiki: http://www.oeis.org/wiki/User:Jon_Awbrey
facebook page: https://www.facebook.com/JonnyCache
_______________________________________________
Inquiry mailing list
[email protected]
http://stderr.org/cgi-bin/mailman/listinfo/inquiry