Theory of Computation
- Syllabus
- Calendar
- Assignment #1
- Assignment #2
- Assignment #3
- Assignment #4
- Assignment #5
- Assignment #6
- Assignment #7
- The Dangling Else Ambiguity--also here.
- Sed--an introduction.
- Alan Turing
Home Page--Andrew Hodges
- Theory Blogs
- Computational Complexity --Lance Fortnow (blog)
- Mathematics and Computation
- Andrei Lopatenko (blog)
- Stetl-Optimized --Scott Aaronson (blog)
- NP-Completeness Problems --David Johnson
- Simulators
- DFA Simulation--by Carl Burch
- FSME--FA Simulator, by Matt Chapman
- ABCEZ--FA Simulator, by MindSpring
- Turing Machine Simulator--by Helmut Weber
- Turing Machine Simulator--applet by Susan Skinner
- Visual Automata Simulator--by Jean Bovet
- Turing Machine Simulator--by Del Slane (.jar file, sources here)
- Computing Fibonacci Numbers on a Turing Machine
- Busy Beavers
- Busy Beaver--Wikipedia article
- Historical Survey of Busy Beavers--Pascal Michel
- The Busy Beaver, The Placid Platypus, and Other Crazy Creatures--by James Harland (Dan)
- Heiner Marxen's Busy Beaver page (Dan)
- Lambda Calculus
- Introduction to the Lambda Calculus--Barendregt and Barendsen (.pdf)
- To Dissect a Mockingbird: A graphical Notation for the Lambda Calculus with Animated Reduction--Keenan
- Lambda Calculus--Wikipedia
- Toy Lambda Interpreter--Allison (Ian)
- Rewriting Extended Regular Expressions--Antimirov, Mosses (Tony)
- A Procedure for Checking Equality of Regular Expressions--Ginzburg (Tony)
- Post Correspondence Problem
- Tackling Post's Correspondence Problem--Ling Zhao
- Using DNA to Solve the Bounded Post Correspondence Problem--Kari, Gloor, Yu
- Post Correspondence Problem--Wikipedia
- Joy--a language for recursion theory
- Formalizing the Halting Problem in a Constructive Type Theory--Kristofer Johannisson (.pdf)
- Curry-Howard Isomorphism--Wikipedia
- Lectures on Curry-Howard Isomorphism--Sorensen (.pdf)
-
Quines--self
replicating programs, by David Madore.
- Our Java quine is here, and here is Eric's quineit.rb which turns any ruby program into a quine.
- What is Turing Reducibility?--Martin Davis (.pdf)
- Wikipedia article on Turing degrees
- Degrees of Unsolvability--Spies, Feier (.pdf) (2006)
- Computability and Complexity--from the Stanford Encyclopedia
- P-versus-NP
- The Complexity Zoo
- Turing vs. Super-Turing --Luciano Floridi
- ACM
Updated December 12, 2006