# I can't believe it's a universal computer!

Seriously, how is that a universal computer.

"It is beneath the dignity of excellent men to waste their time in calculation when any peasant could do the work just as accurately with the aid of a machine."
Gottfried Leibniz's Stepped Reckoner (1672 - 1694).
Charles Babbage's Analytical Engine (1871- ).

## Definitions

By universal computer, I mean a model of computation which is Turing complete.

A model of computation is Turing complete if it can simulate any single-taped Turing machine.

A Turing machine $M$ looks like this:

$M = \langle Q,\Gamma,b,\Sigma,\delta,q_0,F \rangle.$

with:

• $Q$, a set of states,
• $\Gamma$, an alphabet of symbols,
• $b$, a blank symbol,
• $\Sigma \subseteq \Gamma$, a set of input symbols,
• $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$, a (partial) transition map,
• $q_0$, an initial state,
• $F$, a set of terminal states.

Turing machines can compute any computable function.

What that looks like in practice is this:

Alan Turing.
The government chemically castrated him because he was TOO COOL FOR SCHOOL.
(actually it was because he was really really gay)

## Sensible Turing complete models of computation

• Church's $\lambda$-calculus. The $\lambda$-calculus deals entirely with functions; there are no numbers.
• Automata theory deals with machines a bit more general than Turing machines.
• Most programming languages.
• Turing machines.
• Formal languages and grammars.
• Rewriting systems.
• The $\operatorname{NAND}$ gate.  $x$ $y$ $x \operatorname{NAND} y$ $0$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$
$\begin{eqnarray} x \operatorname{AND} y &=& (x \operatorname{NAND} y) \operatorname{NAND} (x \operatorname{NAND} y), \\ x \operatorname{OR} y &=& (x \operatorname{NAND} x) \operatorname{NAND} (y \operatorname{NAND} y). \end{eqnarray}$
• The combinators $S$ and $K$. $\begin{eqnarray}Ix &\rightarrow& x, \\ Kxy &\rightarrow& x, \\ Sxyz &\rightarrow& xz(yz). \\ \\ I &=& (SKK). \end{eqnarray}$
• Babbage's analytical engine.
• DNA.
• LaTeX.

## Silly Turing-complete models of computation

BrainF*** simulates a simple Turing machine, but can do it with just eight commands.

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.
A BrainF*** program which outputs, "Hello World!"

Ook is equivalent to BrainF***, but is in Orangutan syntax.

Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook.Ook! Ook. Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook?Ook! Ook! Ook? Ook! Ook? Ook. Ook. Ook. Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook! Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook! Ook. Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook. Ook! Ook.Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook? Ook. Ook. Ook.Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook. Ook? Ook! Ook! Ook? Ook! Ook? Ook. Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.Ook? Ook. Ook? Ook. Ook? Ook. Ook? Ook. Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook.Ook! Ook. Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!Ook! Ook. Ook. Ook? Ook. Ook? Ook. Ook. Ook! Ook.
An Ook program which outputs, "Hello World!"

Unlambda is based on the $S$ and $K$ combinators and is practically impossible to understand.

					dkkki.2krksiiskskskissksskskssskssksksskskskssskssksksskskskssksskssksksskskdskskkskdsiiskskskisskssksksskssksskdskkssikkkkikkkskskskdskskskksskssksksskssksssksssksskdskksskssksssikkkkikkkskskdskskkssksskdsksiisskssksksskssksssksskdskksikkkkikskdkskskskdskskskkssksskskssksksssikkkkikkkkskskskdskskskksskssksksskskdskskkssksskdskksiiksikkikksikkikkkkkkkkssikkkkikkkkkikkkskdsksiisskssksksskssksssksskdskksikkkkikskdkskskskdskskskkssksskskssksksssikkkkikkkkskskskdskskskksskssksksskskdskskkssksskdskksiiksikkikksikkikkkkkkkkssikkkkikkkkskskskdskskskkssksskskssskssksksskskskssskssksksskskskssksksksssssssssikkkkikkskdskkssikkikkkkikkkikkkkikkskskskdskskskkskskskdskskskkskskdssksskdskksiiksikkikkkkkkikkkkkkssksskssiisskssksksskssksskdskkssssssikkikkkkiskdskksssikkkkikkkkkikkskdskkskssikssikkikkkkskskskdskskskkskskskisskssksksssksskskssksksksskssksskdskksksskssssikkikkikkkkiskdskkskdskkskssikssikkikkkkskskskskdskskskskksksksksssksskskssksksiskskkssksskdskkskskskissksskdsiissksskskssksksksskskskdskskskksksksksskssksiskksikkskskskskkssksskskssksksksskssksskskssskssksksssksskskssskssksksskskssssikkikkikkskskdskskkskskdskskkssksssksssksskdskkssikkikkkkikskdskkssikkikkkkikkkkikkkkkkkkikkkkkkkkkkskskskskdskskskskkssksskskssksksksskskskdskskskksskssksksskskdskskkssksskdskksiikskssssikkkkikkssikkikkkskdkkksikkikkskssssikkkkikkssikkikkkskdkkksikkikkksikkikkkkkkssksskskssskssksksssksskdskksksskdskksikkkskskdskskkssksssksssksskdskksikkkskdskksskssksikkkkkskdskksskssksiskkssikkikkkkkkkskskdskskkssksssksssksskdskksikkkskdskksskssksiskkssikkikkkkskdskksskssksikkkkikkkkkkkkkkissikkikkksikkkskksikkisskssksksskskdskskksksksssksskdskksksskdskksiikssksssksskdskkskskskiskskskssssikkkkikkssikkikkkskdkkksskssksksssksskdskksksskssksiissksskdskkskssksksskskdskskksksksskskdskskkskskkissksssksskssikkkkiskdskkskdskkssikksikkikkikkkkssksskskssksksksskskskdskskskksksksksskssksssksssksssksssksskssikkkkiskdskkskdskkssikkikkkkkkikkkkkkkkskskdskskkssksskdskkskssksikkkkkksikkssksskskssksksksskssksskdskksksssksssksssksskssssikkikkikkskdskkskdskkssikkikkkkikkkkikkkkkkkkskskskskdskskskskkssksskskssksksksskskskdskskskksskssksksskskdskskkssksskdskksiiksikkikkskssssikkkkikkssikkikkkskdkkksikkikkksikkikkkkkksskssksksssksskskssksksiskskdskskkskskdskskkssksssksssksskdskksikkkskdskksskssksiskksikkskksikkkskdskksskssksiskksssikkkkikkkkkkkkskskdskskkskskdskskkssksssksssksskdskksikkkskdskksskssksiskksssikkkkikkkkkikskdskksskssksiskksikkskksikkkkkkkkkkkkkkkkikssikkikkiksskssksiskksikkskkskssikkkskksskssksiskkskssssikkkkikkssikkikkkskdkkksssikkikkkkiskksssssssikkikkkkikkkkikkkkskdskksssikkikkikkikkkkkkkkkkkskskcsksksskssksikskskdskskkskskkssksssksskdsiissksskskssksksksskskskskssskssksksskskskssksksksksskskssksskdskksksskdskksikkkkiskskskskskdskskskskskksskssksksskskskssksksksksskssksskdskkskssksksssksskdskksksskdskksikkkkikskskdskskkssksskdskkskssksikkkskskskskskdskskskskskksskssksksskskskssksksksksskskskskdskskskskkssksskskssksksksskskskdskskskkskskdssksskdskksiiksikkikkkskssikkikkkkkskssikkikkkkkkkskskskskskdskskskskskksskssksksskskskssksksksksskssksskdskksksskdskksksskdskkssikkkkikkssikssikkikkkkkkskskskskskdskskskskskkskskskskdskskskdsskssksksskskdskskkssksskdskksiiksikkikksikkikkkkkkkkkkkkkkssikkkkkkikkkkskdskksikkkkkikkkkkkkkskskskskdskskskskksdksdkssksskdskksskkkidskisksiissksskskkisskssskssksssssikkikkkkikkikkskskdskskkssksskdskksiiksikkikkikkkkssikkkkdsiissksskdskksdksskssksiskkssssssikkikkikkkkiskdskksssssikkikkdkdk.1dkdk.0kkskdskksssssssikkikkikkikkkkiskdskksssssikkikkdkdk.3dkdk.2kkskdskkssssssssikkikkikkikkikkkkiskdskkssssssikkikkikkskdskksssssikkikkdkdk.7dkdk.6kkskdskksssssikkikkdkdk.5dkdk.4kkkkskdskksssssikkikkdkdk.9dkdk.8kkkkkkkkskskksskssksssssssssikkkkkkikkskdskksssikkkkikkkkikkkikkkkkkskskdskskkssksskdskksiiksikkkkkkssiisskssksksskssksskdskkssssssikkikkkkiskdskksssikkkkikkkkkikkskdskkskssikssikkikkkkskskskdskskskkskskskisskssksksssksskskssksksksskssksskdskksksskssssikkikkikkkkiskdskkskdskkskssikssikkikkkkskskskskdskskskskksksksksssksskskssksksiskskkssksskdskkskskskissksskdsiissksskskssksksksskskskdskskskksksksksskssksiskksikkskskskskkssksskskssksksksskssksskskssskssksksssksskskssskssksksskskssssikkikkikkskskdskskkskskdskskkssksssksssksskdskkssikkikkkkikskdskkssikkikkkkikkkkikkkkkkkkikkkkkkkkkkskskskskdskskskskkssksskskssksksksskskskdskskskksskssksksskskdskskkssksskdskksiikskssssikkkkikkssikkikkkskdkkksikkikkskssssikkkkikkssikkikkkskdkkksikkikkksikkikkkkkkssksskskssskssksksssksskdskksksskdskksikkkskskdskskkssksssksssksskdskksikkkskdskksskssksikkkkkskdskksskssksiskkssikkikkkkkkkskskdskskkssksssksssksskdskksikkkskdskksskssksiskkssikkikkkkskdskksskssksikkkkikkkkkkkkkkissikkikkksikkkskksikkisskssksksskskdskskksksksssksskdskksksskdskksiikssksssksskdskkskskskiskskskssssikkkkikkssikkikkkskdkkksskssksksssksskdskksksskssksiissksskdskkskssksksskskdskskksksksskskdskskkskskkissksssksskssikkkkiskdskkskdskkssikksikkikkikkkkssksskskssksksksskskskdskskskksksksksskssksssksssksssksssksskssikkkkiskdskkskdskkssikkikkkkkkikkkkkkkkskskdskskkssksskdskkskssksikkkkkksikkssksskskssksksksskssksskdskksksssksssksssksskssssikkikkikkskdskkskdskkssikkikkkkikkkkikkkkkkkkskskskskdskskskskkssksskskssksksksskskskdskskskksskssksksskskdskskkssksskdskksiiksikkikkskssssikkkkikkssikkikkkskdkkksikkikkksikkikkkkkksskssksksssksskskssksksiskskdskskkskskdskskkssksssksssksskdskksikkkskdskksskssksiskksikkskksikkkskdskksskssksiskksssikkkkikkkkkkkkskskdskskkskskdskskkssksssksssksskdskksikkkskdskksskssksiskksssikkkkikkkkkikskdskksskssksiskksikkskksikkkkkkkkkkkkkkkkikssikkikkiksskssksiskksikkskkskssikkkskksskssksiskkskssssikkkkikkssikkikkkskdkkksssikkikkkkiskksssssssikkikkkkikkkkikkkkskdskksssikkikkikkikkkkkkkkkkkskskcsksksskssksikskskdskskkskskkssksssksskdsiissksskskssksksksskskskskssskssksksskskskssksksksksskskssksskdskksksskdskksikkkkiskskskskskdskskskskskksskssksksskskskssksksksksskssksskdskkskssksksssksskdskksksskdskksikkkkikskskdskskkssksskdskkskssksikkkskskskskskdskskskskskksskssksksskskskssksksksksskskskskdskskskskkssksskskssksksksskskskdskskskkskskdssksskdskksiiksikkikkkskssikkikkkkkskssikkikkkkkkkskskskskskdskskskskskksskssksksskskskssksksksksskssksskdskksksskdskksksskdskkssikkkkikkssikssikkikkkkkkskskskskskdskskskskskkskskskskdskskskdsskssksksskskdskskkssksskdskksiiksikkikksikkikkkkkkkkkkkkkkssikkkkkkikkkkkssikkikssikkkssikkikssikkkkkdkrkskskskdssksskdskksksskdskksiikskssiisskssksksskssksskssikkkkiskdskkskdskksskssksikkkkkskskskdskskskksksksskssksiskksikkskskskksskssksksskskdskskkskdsiikksikkikkkkkskskdskskkskskskdskskskkskskdskdsiikkkkkkksskskissksskdsiissksskskssksksksskskskdskskskksksksksskssksiskksikkskskskskkssksskskssksksksskssksskskssskssksksssksskskssskssksksskskssssikkikkikkskskdskskkskskdskskkssksssksssksskdskkssikkikkkkikskdskkssikkikkkkikkkkikkkkkkkkikkkkkkkkkkskskskskdskskskskkssksskskssksksksskskskdskskskksskssksksskskdskskkssksskdskksiikskssssikkkkikkssikkikkkskdkkksikkikkskssssikkkkikkssikkikkkskdkkksikkikkksikkikkkkkkssksskskssskssksksssksskdskksksskdskksikkkskskdskskkssksssksssksskdskksikkkskdskksskssksikkkkkskdskksskssksiskkssikkikkkkkkkskskdskskkssksssksssksskdskksikkkskdskksskssksiskkssikkikkkkskdskksskssksikkkkikkkkkkkkkkikssikkikssikkkkkkkssikkkssikkkkkk

An Unlambda program which computes the prime numbers.

Befunge is a finite state automaton with a stack, but it works in two dimensions.

#1#3#5#7#9#b#d#f; init ;a8+y00p>:00gg' -v   v        +1_:20p:1+*1-00g\-30p00g1+v
1              1               ^      +1_10p>:00g1-g'|-^  vp06:+g01p05:+g01p04:<
2              2v ; build lists ;  p0a0p09+1p08:+1p07:+g01<
3              3>01p11p>01g:20g/+11g:20g/+30g+g:' -!v
4123456789abcde4   >   ^          _v#p10:%g01+1g10<v_ ; identify symbol ; 021p:v
v17z'p16 ; main ; _^#!p11:%g01+1g11< vp+g11g05g12;  mark in lists ; $_21g1+21p:v p >1g:20g/+11g:20g/+30g+g' -v >21g60g01g+p2 1g40g01g20g/+11gv ^!-gg00g12< 8 0 v># _v ^ p+*g02/g02< >1p51p^ 0 > 60g01g+g51g40 g01g20g/+11g20v >a0g+v 6 v< ^ ^g15g+g11g05g15< g ^$p0a<
p  ;^;^_#;<    |p15:%g01+1g15pg09g15!0**g+*g02/<
1>:11p ^   >   >  51g90ggv 1<
7^%g01 +1g<|p15:%g01+1g15_1+^ v                                  <
z>01p#^_11^>:!v             11<               > ; long ; 2+71g\!|
'^:%g01+1g10<$_ ; -> process symbol list ; :1-| > ; copy ; 078v ; ^ ; <- go to next point ;p1< > ; append ;$61g67              v
> ; -> finished scan ; 61g!v   >ga1g^ v1pg0g19\g11:+1pg0g19\g10:g1bp1bp1ap19<
^               _'z71p1    v   1>    ;>+b1p#;51g90ggv1p1b+1g1b   <
^-2g17p160<    b|p15:%g01+1g15      _51gb1g91g0gp^
> ; backtrack ;a0g!#@_0#@}kp^    ^<                     >51g70gg91p51g1+70gga1v
|!-z'g17 ; do long list <- ; _ ; -> do 1 list ; >51g61g-|vg1ag05p1b:gg07+2g15p<
^ ; <- scan again ;                                      <>+pb1g60g91g+pb1g40g9v
> ; recurse! ; >01g40g11g+g01g40g11g+01g50g11g+v v9gg00g1bp+*g02/g02g1a+/g02g1<
v11g06g10g+g11g06g10+g11g05g10g< >1g:20g/+a1g:20g/+30g+p51g3+5v
|>g+01g:20g/+11g:20g/+30g+g01g:2v^ p163 ;*HAX*;      p0a-1g0ap1<
| p11:%g01+1g11] p10:%g01+1g10+g03+/g02:g11+/g0<
>080gg91p180gga1p71g1-80gg:b1p0\50ga1g+p0b1g60g91g+p0b1g40g91g20g/+a1g20g/20g*v
v0ap0a-1:g0a17p17:-1g17p+g03+/g02:g1a+/g02:g19gg00g1bp+<
>61g80gg61g80g61g1+:61p71g-v
^                       ^                          _10g:*4*71g+1+0{{2u2-u}


A Befunge program which solves Sudoku puzzles.

Chef is a programming language whose programs read like recipes.

Fibonacci Numbers with Caramel Sauce.

This recipe prints the first 100 Fibonacci numbers. It uses an auxiliary recipe for caramel sauce to define Fibonacci numbers recursively. This results in an awful lot of caramel sauce! Definitely one for the sweet-tooths.

Ingredients.
100 g flour
250 g butter
1 egg

Method.
Sift the flour. Put flour into mixing bowl. Serve with caramel sauce. Stir for 2 minutes. Remove egg. Rub the flour until sifted. Stir for 2 minutes. Fold the butter into the mixing bowl. Pour contents of the mixing bowl into the baking dish.

Serves 1.

Caramel Sauce.

Ingredients.
1 cup white sugar
1 cup brown sugar
1 vanilla bean

Method.
Fold white sugar into mixing bowl.
Put white sugar into mixing bowl.
Fold brown sugar into mixing bowl.
Clean mixing bowl.
Put white sugar into mixing bowl.
Remove vanilla bean.
Fold white sugar into mixing bowl.
Melt white sugar.
Put vanilla bean into mixing bowl.
Refrigerate.
Heat white sugar until melted.
Put white sugar into mixing bowl.
Remove vanilla bean.
Fold white sugar into mixing bowl.
Caramelise white sugar.
Put vanilla bean into mixing bowl.
Refrigerate.
Cook white sugar until caramelised.
Put white sugar into mixing bowl.
Serve with caramel sauce.
Fold brown sugar into mixing bowl.
Put white sugar into mixing bowl.
Serve with caramel sauce.
Add brown sugar.`
Fibonacci Numbers with Caramel Sauce.

## Implementations

A Turing machine made out of LEGO.
A Turing-complete music sequencer for poncy iPhone owners.
A Turing machine in Conway's Game of Life.
A Turing machine constructed in LittleBigPlanet.
Conway's Game of Life in LittleBigPlanet.