Re: R.J. Lipton and K.W. Regan • Proving Cook’s 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 I developed as an extension of Peirce’s logical graphs.
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 to be described in more detail as we proceed.
I’d love to go for a spin in your marvelous turing machine.
Well, the old Model T still runs, if you know how to coddle an antique automaton. No bells and whistles, though, so it might scare horses and passersby —
☞ Theme One Program
I can send you the PAS and EXE if you want to tinker with it.