The 100 Punchcard Turing Machine

1111.101.00 001

1111.101.01 002

1111.101.10 003

1111.101.11 004

1111.110.00 005

1111.110.01 006

1111.110.10 007

1111.110.11 008

1111.111.00 009

1111.111.01 010

1111.111.10 011

1111.111.11 012

0000.000.00 013

0000.000.01 014

0000.000.10 015

0000.000.11 016

0000.001.00 017

0000.001.01 018

0000.001.10 019

0000.001.11 020

0000.010.00 021

0000.010.01 022

0000.010.10 023

0000.010.11 024

0000.011.00 025

0000.011.01 026

0000.011.10 027

0000.011.11 028

0000.100.00 029

0000.100.01 030

0000.100.10 031

0000.100.11 032

0000.101.00 033

0000.101.01 034

0000.101.10 035

0000.101.11 036

0000.110.00 037

0000.110.01 038

0000.110.10 039

0000.110.11 040

0000.111.00 041

0000.111.01 042

0000.111.10 043

0000.111.11 044

0001.000.00 045

0001.000.01 046

0001.000.10 047

0001.000.11 048

0001.001.00 049

0001.001.01 050

0001.001.10 051

0001.001.11 052

0001.010.00 053

0001.010.01 054

0001.010.10 055

0001.010.11 056

0001.011.00 057

0001.011.01 058

0001.011.10 059

0001.011.11 060

0001.100.00 061

0001.100.01 062

0001.100.10 063

0001.100.11 064

0001.101.00 065

0001.101.01 066

0001.101.10 067

0001.101.11 068

0001.110.00 069

0001.110.01 070

0001.110.10 071

0001.110.11 072

0001.111.00 073

0001.111.01 074

0001.111.10 075

0001.111.11 076

0010.000.00 077

0010.000.01 078

0010.000.10 079

0010.000.11 080

0010.001.00 081

0010.001.01 082

0010.001.10 083

0010.001.11 084

0010.010.00 085

0010.010.01 086

0010.010.10 087

0010.010.11 088

0010.011.00 089

0010.011.01 090

0010.100.01 094

0010.101.01 098

0010.101.10 099

0010.101.11 100

A Universal Turing Machine
in 100 Punchcards

Source Listing

To compute the first 22 evolutions takes

700 cards, 58 minutes and 20 seconds.

'------------------------------------- ' Program Info '------------------------------------- ' A Universal Turing Machine in 100 ' Punchcards. ' ' 20 May 2012 ' ' Source '------------------------------------- ' Header Cards '------------------------------------- Nop 12 '------------------------------------- ' Define Constants '------------------------------------- Assign <-- 1111 Assign --> 0001 Assign -|- 0000 Assign White 0000 Assign Yellow 0001 Assign Orange 0010 '------------------------------------- ' Define Number Of First Punchcard '------------------------------------- Origin 0000.000.00 '------------------------------------- ' Define Number Of Memory Cells '------------------------------------- StoreCells FH '------------------------------------- ' Main '------------------------------------- CardToBus 8H BusToMill Cylinder H000000896 Nop Nop MillExe MillToBus StoreSel Nop Nop Nop CardToBus -|- '------------------------------------- ' State_1 '------------------------------------- State_1 MoveTape CardToBus Rule_1 High JmpSetHigh StoreToBus CardToBus 1xxx JmpSetLow Jmp Rule_1 Cylinder H0020000A9 Cylinder H004000065 Cylinder H0000400A9 Cylinder H000800055 Cylinder H0020000AA Cylinder H0040000A5 Cylinder H0000400A6 Cylinder H0008000A9 Cylinder H0020000AA Cylinder H0040000A5 Cylinder H0000400A9 Cylinder H0008000A9 '------------------------------------- ' State_2 '------------------------------------- State_2 MoveTape CardToBus Rule_2 High JmpSetHigh StoreToBus CardToBus 1xxx JmpSetLow Jmp Rule_2 Cylinder H0020000AA Cylinder H0040000A5 Cylinder H0000400A6 Cylinder H0008000A9 Cylinder H0020000A9 Cylinder H0040000A5 Cylinder H0000400A6 Cylinder H000800055 Cylinder H0020000AA Cylinder H0040000A5 Cylinder H0000400AA Cylinder H000800055 '------------------------------------- ' Macro MoveTape '------------------------------------- Macro MoveTape BusToMill Cylinder H000000A99 Nop Nop MillExe Cylinder H000000869 ' Nop ' Nop MillExe MillToBus StoreSel Nop Nop Bell /Macro '------------------------------------- ' Trailer Cards '------------------------------------- Nop 12

A Universal Turing Machine
in 100 Punchcards

Binary Listing

To compute the first 22 evolutions takes

700 cards, 58 minutes and 20 seconds.

'------------------------------------- ' Program Info '------------------------------------- ' A Universal Turing Machine in 100 ' Punchcards. ' ' 20 May 2012 ' ' Binary Card ID | Data | Control | No '------------------------------------- ' Header Cards '------------------------------------- 1111.101.00 | | | 001 1111.101.01 | | | 002 1111.101.10 | | | 003 1111.101.11 | | | 004 1111.110.00 | | | 005 1111.110.01 | | | 006 1111.110.10 | | | 007 1111.110.11 | | | 008 1111.111.00 | | | 009 1111.111.01 | | | 010 1111.111.10 | | | 011 1111.111.11 | | | 012 '------------------------------------- ' Define Constants '------------------------------------- '------------------------------------- ' Define Number Of First Punchcard '------------------------------------- '------------------------------------- ' Define Number Of Memory Cells '------------------------------------- '------------------------------------- ' Main '------------------------------------- 0000.000.00 | 1000 | | 013 0000.000.01 | | BusToMill | 014 0000.000.10 | 0110 | MillSel | 015 0000.000.11 | | | 016 0000.001.00 | | | 017 0000.001.01 | | MillExe | 018 0000.001.10 | | MillToBus | 019 0000.001.11 | | StoreSel | 020 0000.010.00 | | | 021 0000.010.01 | | | 022 0000.010.10 | | | 023 0000.010.11 | 0000 | | 024 '------------------------------------- ' State_1 '------------------------------------- 0000.011.00 | | BusToMill | 025 0000.011.01 | 0101 | MillSel CYC | 026 0000.011.10 | | | 027 0000.011.11 | | | 028 0000.100.00 | | MillExe | 029 0000.100.01 | 1001 | MillSel | 030 0000.100.10 | | MillExe | 031 0000.100.11 | | MillToBus | 032 0000.101.00 | | StoreSel | 033 0000.101.01 | | | 034 0000.101.10 | | | 035 0000.101.11 | | Bell | 036 0000.110.00 | 0001 | | 037 0000.110.01 | | JmpSetHigh | 038 0000.110.10 | | StoreToBus | 039 0000.110.11 | 1xxx | | 040 0000.111.00 | | JmpSetLow | 041 0000.111.01 | | Jmp | 042 0000.111.10 | | | 043 0000.111.11 | | | 044 0001.000.00 | 0001 | JmpSetHigh | 045 0001.000.01 | 1011 | JmpSetLow | 046 0001.000.10 | 0001 | BusToStore | 047 0001.000.11 | 1111 | Jmp | 048 0001.001.00 | 0000 | JmpSetHigh | 049 0001.001.01 | 0011 | JmpSetLow | 050 0001.001.10 | 0010 | BusToStore | 051 0001.001.11 | 0001 | Jmp | 052 0001.010.00 | 0000 | JmpSetHigh | 053 0001.010.01 | 0011 | JmpSetLow | 054 0001.010.10 | 0001 | BusToStore | 055 0001.010.11 | 0001 | Jmp | 056 '------------------------------------- ' State_2 '------------------------------------- 0001.011.00 | | BusToMill | 057 0001.011.01 | 0101 | MillSel CYC | 058 0001.011.10 | | | 059 0001.011.11 | | | 060 0001.100.00 | | MillExe | 061 0001.100.01 | 1001 | MillSel | 062 0001.100.10 | | MillExe | 063 0001.100.11 | | MillToBus | 064 0001.101.00 | | StoreSel | 065 0001.101.01 | | | 066 0001.101.10 | | | 067 0001.101.11 | | Bell | 068 0001.110.00 | 0010 | | 069 0001.110.01 | | JmpSetHigh | 070 0001.110.10 | | StoreToBus | 071 0001.110.11 | 1xxx | | 072 0001.111.00 | | JmpSetLow | 073 0001.111.01 | | Jmp | 074 0001.111.10 | | | 075 0001.111.11 | | | 076 0010.000.00 | 0000 | JmpSetHigh | 077 0010.000.01 | 0011 | JmpSetLow | 078 0010.000.10 | 0010 | BusToStore | 079 0010.000.11 | 0001 | Jmp | 080 0010.001.00 | 0001 | JmpSetHigh | 081 0010.001.01 | 0011 | JmpSetLow | 082 0010.001.10 | 0010 | BusToStore | 083 0010.001.11 | 1111 | Jmp | 084 0010.010.00 | 0000 | JmpSetHigh | 085 0010.010.01 | 0011 | JmpSetLow | 086 0010.010.10 | 0000 | BusToStore | 087 0010.010.11 | 1111 | Jmp | 088 '------------------------------------- ' Macro MoveTape '------------------------------------- '------------------------------------- ' Trailer Cards '------------------------------------- 0010.011.00 | | | 089 0010.011.01 | | | 090 0010.011.10 | | | 091 0010.011.11 | | | 092 0010.100.00 | | | 093 0010.100.01 | | | 094 0010.100.10 | | | 095 0010.100.11 | | | 096 0010.101.00 | | | 097 0010.101.01 | | | 098 0010.101.10 | | | 099 0010.101.11 | | | 100

What Am I Looking At?

This website is about a program for a mechanical computer.

The mechanical computer is called the "Loom" (named after the punchcard controlled loom invented in 1801 by Joseph Jacquard, which revolutionized the textile industry in the early 1800's).

The program is a Turing Machine (named after the theoretical computing device invented by Alan Turing in 1936, which spawned a scientific field of study known as computer science).

Hence, Turing Loom is a contraction of Jacquard Loom and Turing Machine.

The website is also about the British mathematician Alan Turing who was born 100 years ago.

~ ~ ~

So, why write a Turing Machine for a mechanical computer? The answer is best answered by answering another question.

What tool do you need if you want to be able to solve all problems in a particular field?

If you go on a survival trip, maybe the swiss army knife is such a tool. It is actually hard to come up with many more examples, because there are not many of such tools.

There is one notable exception, however. For computation, Turing showed that this tool is the Universal Machine.

"If something can be computed in any amount of time in the physical world then it can also be computed by a Universal Machine." [1]

Turing Schematic

Turing Machine

A Turing Machine has few parts. A wheel, a head that can read and write, a control mechanism and a tape. The control is nothing more than a lookup table.

The lookup table defines if the Turing Machine is universal or not.

Clockwork Schematic

The Clockwork Computer

As can be seen in the figure above, this website is about a train of 100 punchcards that contains the program for a Universal Machine. The program must be run on a clockwork computer.

Just like the clockwork computer, the Universal Machine needs a program, too. This program is fetched from the memory, which represents the tape. If the memory contains all zeros, the result is called evolution from a blank tape.

This tiny Universal Machine is in fact very difficult to program to do anything useful. It is always easier to write a program for the clockwork computer directly than to write a program for a Turing Machine running on the clockwork computer.

So, the answer is that the program demonstrates that the system can perform any computation that can be done by any computer.

[1] The quote is from Scott Aaronson, however he used "Turing Machine", instead of "Universal Machine".

The Clockwork Computer

1913
Alan Turing is born on 23 June
1912. Turing is 1 year old.

1914

1915

1916

1917

1918
Turing attends St Michael's day school.

1919

1920

1921

1922

1923

1924

1925

1926
Turing attends Sherborne School.

1927

1928

1929

1930
His fellow student and first love, dies
from complications of bovine
tuberculosis.

1931
Turing attends King's College, Cambridge.

1932

1933

1934
Turing graduates with first class honours
in Mathematics.

1935
At the age of 22, Turing is elected a fellow
at King's College on the strength of his
dissertation.

1936
Turing submits his famous paper "On
Computable Numbers, with anApplication
to the Entscheidungsproblem".

1937
Turing studies cryptology and builds
an electro mechanical multiplier.

1938
Turing receives a PhD from Princeton.
His dissertation introduces problems that
cannot be solved by a Turing machine.

1939
Turing starts working at Bletchley Park,
where he builds "The Bombe" to decrypt
German Enigma messages.

Enigma

1941
Turing proposes Joan Clarke, a fellow
mathematician, but their engagement is
short lived.

1942
Turing travels to the United States to work
with U.S. Navy cryptanalysts on Naval
Enigma in Washington.

1943
Turing returns to Bletchley Park.

1944
More than two hundred "Bombes" are in
operation.

1945
Turing is awarded the OBE for his wartime
services.

1946
Turing presents a paper about the design
of a stored program computer.

1947
Turing returns to Cambridge for a
sabbatical year. Turing meets Konrad
Zuse in Göttingen.

1948
Turing invents the LU decomposition
method for solving matrix equations.

1949
Turing proposes the Turing test ...

... a computer could be said to be
intelligent if a human interrogator
could not tell it apart, through
conversation, from a human being.

Pawn

1952
Lacking a computer, Turing executes
his chess program with pen and paper.
The program once loses and once wins.

1953
Turing works on pattern formation in
biology.

1954
On 7 June, Turing dies after eating an
apple poisoned with cyanide.

Apple

1956

1957

1958

1959

1960

1961

1962

1963

1964

1965

1966

1967

1968

1969

1970

1971
The first commercially available
microprocessor (the 4004) is shipped.

1972

1973

1974

1975

1976

1977

1978

1979

1980

1981

1982

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992
Collected Works of A.M. Turing is
published.

1993

1994

1995

1996

1997

1998

1999

2000

2001

2002

2003

2004

2005

2006

2007

2008

2009

2010

Dates and events retrieved from
http://en.wikipedia.org

2012
Turing's papers about his cryptography
work at Bletchley Park are declassified.