Danny Thorne's List: Theory Of Computation

• We describe a simple Ruby program for simulating an abstract Turing machine. This demonstrates that Ruby is Turing-complete (with the caveat that limitations in word size limit the effective addressable memory).

• This is a simulator for deterministic Turing machines, following the style in J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. A simulator for non-deterministic Turing machines is being planned and will appear after the next project, which is a simulator for a non-deterministic push-down automaton. 
  Please note that there is also a finite-state machine simulator available

• the fourth (pdf file)  (ps file) describes Turing's negative solution to the decision problem in what has become known as the halting problem in computer science.
• The third in this sequence (pdf file)  (ps file) outlines the development Turing's idea of a universal computing machine (today known as a compiler or an interpreter)
• The second project, ``Turing Machines, Induction and Recursion'' (pdf file)  (ps file), explores the machine's capacity for a limited type of memory, and its use in elementary arithmetic operations.
• The first project acquaints students with the workings of a Turing machine, asks the reader to compute the output of a particular machine, and then to design a machine with a given output.
• This article presents curricular materials, based on original historical sources, designed for use in an introductory discrete mathematics course, particularly one with a significant number of computer science majors. The materials are organized into two-week written projects for students, and offer excerpts from Alan Turing's (1912--1954) original 1936 paper ``On Computable Numbers with an Application to the Entscheidungsproblem''(Das Entscheidungsproblem is German for the decision problem) [T],  a paper which outlines a logical device (a ``Turing Machine''), that is the forerunner of a modern computer program.

3 more annotations...

• What is a Universal Turing Machine? The gating  logic for circuit boards in all general computers  descends from a logical procedure known as a Universal  Turing Machine (UTM).  The logic for this  algorithm by Alan Turing (1912-54) was written in 1936  and published in 1937 in the Proceedings of the London  Mathematical Society. This paper, “On computable  numbers, with an application to the  Entscheidungsproblem", planted the seminal idea for all general computers.

• A Push Down Automata Simulator
• Turing Machine Simulator