Mind Of Minsky - oder der eigenartige Professor

German summary below

So, I wrote in my last articles or posts about the universal computation and simple paradigms or programs which can do so.
Unfortunately at Halloween I stumbled upon tag systems or something Emil Post - a professor at Princeton - discovered, researched and then gave up on it.

Decades later, Alan Turing invented the Turing machine and it is not known whether or not he got inspired by Post - probably not -
but anyway I like to write about another guy here.

Marvin Minsky or the guy who probably would respond with "count the legs and then divide by six" when it comes to being asked "how many bees are there in a bee hive?".

One of his proposals for which he was known for was to propose a machine which should turn itself off after being turned on - called the useless machine.

tag systems

So Minsky was aware of the Universal Turing Machine and other great inventions of that time and he did not gave up on tag systems. He found out that so called counter machines which consists of two counters or registers could simulate the tape of a turing machine.

Given that there are only two symbols allowed on the tape - either one or zero - he mentally cut the tape into two and proposed to store the resulting two binary numbers in two different registers.

So adding a symbol or digit means just to multiply with two and then either add one or zero while removing a symbol or digit means just to divide by two and then cut the rest. The funny thing about this is that it can be done with unary numbers.

Let's take a look at the unary number system:

100 iiii , 101 iiiii

or just as many symbols as the value of the number.

Thus adding and subtracting is just adding or removing symbols and doubling is just adding two symbols for every symbol already present.
Dividing by two is just the opposite of doubling or in other words removing two symbols and adding one.

Tag system or a special kind of them called 2-tag systems can do that very easily.

Here's a rule for doubling: .->....
Here's a rule for halfing: .->.

A 2-tag system always reads one symbol on the left side, removes it and the next one and then adds symbols on the right end according to the rules.

So Minsky said 2-tag system can do unary arithmetics and in order to proof universality and that 2-tag systems can emulate Turing machines , well
the tape is just represented as two unary numbers.

Thus said an lot of brain melting difficult papers and explanations later he came up on how to construct a Universal Turing Machine. Thus 2-tag systems
are turing complete and universal and in order to proof that something is turing-complete -- might it be your toaster or the card game "Magic The Gathering" -- you just are done with showing that it can simulate any tag system.

Zusammenfassung

In den zwanziger Jahren des vorigen Jahrtausends verzweifelte Professor Emil Post an den von ihm erfundenen Tag-Systemen. Tag-Systeme sind Zeichenketten, die von links nach rechts gelesen werden. Immer das ganze linke Symbol oder Zeichen wird gelesen, dann werden ein oder mehrere Zeichen gelöscht und dann können abhängig vom ersten gelesenen Zeichen keines, eines oder mehrere Zeichen an das rechte Ende hinzugefügt werden. Wie gesagt Emil ist daran verzweifelt.

Die Tag-System gerieten in ziemliche Vergesseneheit bis sich Minsky - noch nicht geklärt ob er mehr Schelm oder Mathematik war - sich ihrer annahm und bewaffnet mit dem was Kollegen vor ihm geleistet hatten bewies er, das sich eine universelle Turingmaschine mit Tag-Systemen verwirklichen lässt.

Wie es seine Art war schlug er das Unärsystem vor, welches auch heute noch in Form von sogenannten Strichlisten gebräuchlich ist ..
z.B. um zu notieren wieviel Bier man gesoffen bzw. konsumiert hat.

Weiters ist der Minsky auch bekannt für die Erfindung und Popularisierung der sogenannten useless machine - einer Maschine, die sich beim Einschalten automatisch ausschaltet.