3.
The Turing Machine
But
on the ground, there is a problem, which is looming in the thoughts
of the participants: they see problems everywhere, and there seems to
be nothing to relate them. It is a fog that no one can see their way
out of. A large part of the problem is that no one realizes that the
mechanics of a new generation are fundamentally different from those
in the past. This was the same with light and electricity, because no
one knew what the difference was. And once it was found it took 50
years to discover the means by which it was enforced by nature. Now
of course the Higgs will be known to all, but it was not that way for
decades.
In
the information space, the idea that it was a machine was not even in
people's mind. Except one, who had been working on cleaning up the
mathematics of Gödel, and he discovered a seemingly bizarre
creation. Remember that no one had thought of it as a machine, even
though the concept had turned up in Ancient Greece, in Renaissance
France, and in Victorian England. But each time it had been
dismissed, and the machines slumbered quietly until someone picked up
the pieces.4
The
man of course was Turing, who was at the right place with the right
brain power. Because there were people who saw the signs and ignored
them. As Winston Churchill said, they hit upon the truth and get up
on their way as if nothing happened. This included Included
Churchill, because Turing was a homosexual, which at the time was
illegal, and immoral, and forced by people who were – many of them
– homosexual. Such are the days the days are made of, and we can
necessarily hope that we will go forward rather than backward
(Because not only being homosexual is genetic, but it is likely that
a revulsion against homosexuality is also genetic, But spreads out
from there.)
But
Turing was working on the machines, and saw a formula, which would
work: an unlimited memory, a scanned symbol, and a simple set of
instructions. And that is all that needs to be accomplished. All of
the rest of the computer hardware that we possess is towards making
it run better. He invented this in 1936, a few years after the GN was
invented. Almost nobody else even thought of a machine for this
problem.
But
what this did is simply astonishing, partially because it solves the
riddle of the Enigma – whose German scientists thought it to be
unbreakable. Yet when the machine was perfected, that is a real
machine, it was able to break things on and enigma code machine
almost in real time. But it was a problem known to David Hilbert, and
put on his list in 1900, called, appropriately enough, the “Hilbert's
Problems”. Thus the uncrackable problem was indeed cracked by a
simple machine in real time – though not in theory, because it was
not possible. Remember that the mathematics behind this question was
quite exact: first of all was the mathematics complete, second of all
was the mathematics consistent, and third of all was the mathematics
decidable?
Then
on a day in Grantchester Turing had what he needed, because he knew
that this problem was related to a universal machine. Once he had
that concept, it was just working out what the machine had to do. And
Turing had been the one man who was determined to see that a
typewriter was far more than a mechanical device to produce letters.
All
that was to be done is calculating the equivalent of Ohms. But again
remember that the people at the time did not see this at all, because
what they thought of as problems – rather than thinking of
solutions – gripped their minds tightly. So we now move on to Nash,
and one of the most brilliant papers of all time, and one of the most
surprising.
So even as you play with Google,
realize there is a long fight from 1900 when Hilbert enunciated the
question, until you find what you are looking for by typing in a view
words into a box.
Of
course there are problems with the Turing machine – because of
course it in his original form is not quite complete. But the
problems are countable problems, and people throw themselves at
solving them. Just recently, a man by the name of Manolis Kamvysselis
granted his way to a complete schematic of the Universal Turing
Machine – and leaves a copy for others to look at. The core of the
machine is expressed in lines of code:
;; (#(_ _ _ _ _ _ _ 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s1 16) ;; (#(_ _ _ _ _ _ _ 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s1 7) ;; (#(_ _ _ _ _ _ _ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 8) ;; (#(_ _ _ _ _ _ _ 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 9) ;; (#(_ _ _ _ _ _ _ 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 10) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 11) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 12) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 13) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 14) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 15) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 16) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 - - _ _) s2 17) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 - - _ _) s2 18) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 - - _ _) s2 19) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 - - _ _) s2 20) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 - - _ _) s2 21) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 - - _ _) s2 22) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 - - _ _) s2 23) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 - - _ _) s2 24) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 - - _ _) s2 25) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - _ _) s2 26) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - - _ _) s3 25) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - - _ _) s3 7) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - - _ _) s4 8) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - - _ _) h 7) ;; (#(_ _ _ _ _ _ _ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 - - _ _) h 7)
Code responding to an idea of code. There is more written here then
the author suspects.
So how was the Turing Machine set
up? Since this is relatively one of the easiest answers, I do not
need to do anything but explain what has already come to pass. Lots
of people have described the Turing machine.
It Starts with the idea of a
non-empty set of states. He
then introduces the idea of a tape, like a recorded tape, which has a
finite number of non-empty set of symbols on it. Remember when he did
this this was a new concept, and for all practical purposes only the
Germans were actually doing anything with them. But then that is all
right because Gödel it was German. And touring was working on the
problems that Gödel had set up.
Even needed a blank symbol, which was important because only the
blank symbol could be unlimited, all of the rest of the symbols had
to be limited. Even went on to say that the tape was the only source
of input.
You then of course needs to translate the input symbols in two
output symbols, and he does so by introducing the idea that the tape
can move left, or right – though no motion at all can be
represented as a shift zero. He then begins to work on what is called
a busy beaver, which takes an input, and translates this into the
output state. It has only 7 operations:
It can move left or right, or stop.
It can write 1 or 0.
it can read 1 or 0.
it can read
the initial state.
It can halt
then it has the major trick, of computing the next operative in a
table, which is the basis of the machine. It takes the input, which
remember is only one or zero, and translates that in two a three
digit state. Now , remember, most people want to get out of this
current state as quickly as possible, they want to move back to the
two rather than the three, and this table is the key.
A B C
Tape Write Move Next Write Move Next Write Move Next
0 1 R B 1 L A 1 L B
1 1 L C 1 R B 1 R HALT
You can
see that want to get to 1 C – because that is the state where it
halts. Now most of the time, programmers want to make it easier to
build a machine, and you can look up the various topics that they
consider on your own. But we are interested in the purely
mathematical problems that this contains, if you want to go into
computer science, there are many individuals who can take you from
here. But there are few who wish to lead you into the realm of the
purely mathematical, and most of them are interested in cleaning up
the small details - which if you have not gotten it - these are
large, small details.
Remember
that recursion is already here, you can pick either the machine
level, the translation to the operating system, or you can go up the
ladder and work on the scripting language.
Machine i686
Operating System C, Go
User space C++,C#
Scripting language Ruby,
Cassandra, Perl, Python
and so on...
But
there is one point left to consider. If a Gödel is the number of
states, and the Turning is the means to operate on these states, what
confines the operating system? At which point we must reach the
limiting factor, which brings us to Nash.
