Differential Analytic Turing Automata • Discussion 2

Re: Scott AaronsonThe Busy Beaver Frontier

Dear Scott,

This discussion inspired me to go back and look at some of the work I did in the late 80s when I was trying to understand Cook’s Theorem.  One of the programs I wrote to explore the integration of sequential learning and propositional reasoning had a propositional calculus module based on an extension of C.S. Peirce’s logical graphs, so I used that syntax to write out the clauses for finite approximations to Turing machines, taking the 4-state parity machine from Herbert S. Wilf’s Algorithms and Complexity as an object example.  It was 1989 and all I had was a 289 PC with 600K heap, but I did manage to emulate a parity machine capable of 1 bit of computation.  Here’s a link to an exposition of that.

It may be quicker to skip to Part 2 and refer to Part 1 only as needed.

I’ll work up the case of a 2-state Busy Beaver when I get a chance.
I always learned a lot just from looking at the propositional form.

cc: CyberneticsOntolog ForumPeirce ListStructural ModelingSystems Science

This entry was posted in Algorithms, Boolean Functions, C.S. Peirce, Cactus Graphs, Computational Complexity, Differential Analytic Turing Automata, Differential Logic, Logic, Logical Graphs, Peirce, Propositional Calculus, Turing Machines and tagged , , , , , , , , , , , . Bookmark the permalink.

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 )

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.