Differential Analytic Turing Automata : 1

Re: R.J. Lipton and K.W. ReganProving 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 that I developed as an extension of Peirce’s logical graphs.

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.

This entry was posted in Automata, Boolean Functions, C.S. Peirce, Cactus Graphs, Computational Complexity, Computer Science, Cook's Theorem, Differential Analytic Turing Automata, Differential Logic, Logic, Logical Graphs, Peirce, Propositional Calculus and tagged , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to Differential Analytic Turing Automata : 1

  1. Poor Richard says:

    I’d love to go for a spin in your marvelous turing machine.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.