Tasty » Adam Sampson's theory bookmarks

Shtetl-Optimized » Blog Archive » The Power of the Digi-Comp II: My First Conscious Paperlet edit / delete

"I study the Digi-Comp II, a wooden mechanical computer whose only moving parts are balls, switches, and toggles. I show that the problem of simulating (a natural abstraction of) the Digi-Comp, with a polynomial number of balls, is complete for CC (Comparator Circuit)". A nice short example, with some interesting discussion on what the Digi-Comp can and can't compute and why.

to complexity computability cs digicomp mechanica retrocomputing theory ... on 11 July 2014

P-versus-NP page edit / delete

A list of work proving or disproving P=NP.

to amusements cs research theory ... on 16 November 2008

You Can't Get There From Here edit / delete

A neat little guide to the concept of NP-completeness.

to cs research teaching theory ... on 20 May 2006

Epsilon-Delta: Mathematics and Computer Programming » Modeling a Resource Pool edit / delete

to concurrency cs maths research server theory ... on 20 May 2006

Lambda Calculus edit / delete

An Oxford course for beginners to the lambda calculus.

to functional lambda-calculus research theory ... on 20 March 2006

Logical Methods in Computer Science edit / delete

An open-access TCS journal.

to cs journal open-access research theory ... on 27 October 2005