1 Regular expressions

Interactive tools are avalaible at

2 Turing machines

A very practical Turing machine simulator is available at Turing Machine Simulator

Another one is avalaible at Online Turing Machine Simulator

A paper about Turing micros.

Is Busy Beaver the fastest growing function knwon to man?

3 Computability

A funny speech about computability by Philip Wadler.

The Halting Problem

Proof for the Halting problem https://rjlipton.wordpress.com/2016/09/19/a-proof-of-the-halting-theorem/

4 Cellular automata

Other computation formalisms can be used than the ones we talk about this course. Cellular automata are one of them. What is truly amazing is to see that you can simulate a Turing machine using some cellular automaton. Here is an example :

Turing Machine implemented in Conway's Game of Life

5 P vs NP

5.1 Deolalikar Responds To Issues About His P≠NP Proof

Vinay Deolalikar claimed having found a proof that \(P \neq NP\). His proof is incomplete. However the discussion around the proof is very interesting.

Deolalikar Responds To Issues About His P≠NP Proof | Gödel's Lost Letter and P=NP

6 Self-replicating programs or Quines :

Quine sur Wikipedia

List of Quines in many programming languages : http://www.nyx.net/~gthompso/quine.htm

The Tupper's formula is a formula that when plotted in 2D displays itself! Tupper's formula

A PDFTeX Quine: https://code.google.com/p/corkami/source/detail?r=1907