## 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

## 3 Computability

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 :

## 5 P vs NP

The (in)famous video : The Downfall Parody P=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.

## 6 Self-replicating programs or Quines :

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