Theory of Computation
- Syllabus
- Calendar
- Errata for Sipser, 2nd edition
- Assignment #1
- Assignment #2
- Assignment #3
- Proof that the Busy Beaver function is uncomputable
- Assignment #4 -- due May 13
- Hilbert's Problems--a summary of their status with links to the text of Hilbert's 1900 address.
- Hilbert's Tenth Problem: What Can We Do with Diophantine Equations--Yuri Matiyasevich
- Platonism, Constructivism, and Computer Proofs vs. Proofs by Hand--Yuri Gurevich
- The Dangling Else Ambiguity--also here. and Miriam's presentation.
- 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
- ABCEZ--FA Simulator, by MindSpring
- 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)
- A Short Introduction to the Lambda Calculus--Achim Jung (.pdf)
- Lecture Notes on the Lambda Calculus--Peter Selinger (.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.
- An HTML page that displays its own source--by Tom Verhoeff
- Church-Turing Thesis--Wikipedia
- 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 January 21, 2013