Gisbert Hasenjaeger

Gisbert F. R. Hasenjaeger (June 1, 1919 – September 2, 2006) was a German mathematical logician. Independently and simultaneously with Leon Henkin in 1949, he developed a new proof of the completeness theorem of Kurt Gödel for predicate logic. He worked as an assistant to Heinrich Scholz at Section IVa of Oberkommando der Wehrmacht Chiffrierabteilung at Karlstejn, and was responsible for the security of the Enigma machine.

    Personal life

    Gisbert Hasenjaeger went to high school in Mülheim. His father [de] was a lawyer and local politician. At the beginning of World War 2, he volunteered for military service and fought in the Russian campaign where he was badly injured in 1942 and served with artillery. Invalided out of the service, he worked as assistant to Heinrich Scholz, starting cryptography training in October 1942, and worked in Section IVa of Oberkommando der Wehrmacht Chiffrierabteilung (OKW/Chi) at Karlstejn, the youngest member at 24, responsible for the security of the Enigma machine. He knew Heinrich Scholz since his school days and corresponded with him during his time as a conscript. At the end of the war as OKW/Chi disintegrated, Hasenjaeger managed to escape the clutches of TICOM, the allied effort to roundup and seize captured German intelligence people and material.

    From the end of 1945, he studied mathematics and especially mathematical logic with Heinrich Scholz at the Westfälische Wilhelms-Universität University in Münster. In 1950 received his doctorate:

    Topological studies on the semantics and syntax of an extended predicate calculus

    and completed his habilitation in 1953.

    In Münster, he worked as an assistant to Scholz and later co-author, to write the textbook Fundamentals of Mathematical Logic in Springer's Grundlehren series (Yellow series of Springer-Verlag), which he published in 1961 fully 6 years after Scholz's death. In 1962 he became professor at the University of Bonn, where he was Director of the newly created Department of Logic.

    In 1962, Hasenjaeger left Münster University to take a full professorship at Bonn University, where he was established Director of the newly established Department of Logic and Basic Research. In 1964/65 he spent a year at Princeton University. His doctoral students at Bonn included Ronald B. Jensen, his most famous pupil.

    He became professor emeritus in 1984.


    Safety Testing the Enigma Machine

    In Oct 1942, after starting work at OKW/Chi, Hasenjaeger was trained in cryptology, given by the mathematician, Dr. Erich Hüttenhain, who was widely considered the most important German cryptologist of his time. Hasenjaeger was put into a newly formed department, whose principal responsibility was the defensive testing and security control of their own methods and devices. Hasenjaeger was ordered, by the mathematician Karl Stein who was also conscripted at OKW/Chi, to examine the Enigma machine for cryptologic weaknesses, while Stein was to examine the Siemens and Halske T52 and the Lorenz SZ-42. The Enigma machine that Hasenjaeger examined was a variation that worked with 3 rotors and had no plug board. Germany sold this version to neutral countries to accrue foreign exchange. Hasenjaeger was presented with a 100 character encrypted message for analysis and found a weakness which enabled the identification of the correct wiring rotors and also the appropriate rotor positions, to decrypt the messages. Further success eluded him however. He crucially failed to identify the most important weakness of the Enigma machine: the lack of fixed points (letters encrypting to themselves) due to the reflector. Hasenjaeger could take some comfort from the fact that even Alan Turing missed this weakness. Instead the honor was attributed to Gordon Welchman, who used the knowledge to decrypt several hundred thousand Enigma messages during the war. In fact fixed points were earlier used by Polish codebreaker, Henryk Zygalski, as the basis for his method of attack on Enigma cipher, referred to by the Poles as "Zygalski sheets" (płachty Zygalskiego) and by the British as the "Netz method".

    Proof of Gödel's completeness theorem

    It was while Hasenjaeger was working at Westfälische Wilhelms-Universität University in Münster in the period between 1946 and 1953 that Hasenjaeger made a most amazing discovery - a proof of Kurt Gödel's Gödel's completeness theorem for full predicate logic with identity and function symbols. Gödel's proof of 1930 for predicate logic did not automatically establish a procedure for the general case. When he had solved the problem in late 1949, he was frustrated to find that a young American mathematician Leon Henkin, had also created a proof. Both construct from extension of a term model, which is then the model for the initial theory. Although the Henkin proof was considered by Hasenjaeger and his peers to more flexible, Hasenjaeger' is considered simpler and more transparent.

    Hasenjaeger continued to refine his proof through to 1953 when he made a breakthrough. According to the mathematicians Alfred Tarski, Stephen Cole Kleene and Andrzej Mostowski, the Arithmetical hierarchy of formulas is the set of arithmetical propositions that are true in the standard model, but not arithmetically definable. So, what does the concept of truth for the term model mean, the results for the recursively axiomatized Peano arithmetic from the Hasenjaeger method? The result was the truth predicate is well arithmetically, it is even . So far down in the arithmetic hierarchy, and that goes for any recursively axiomatized (countable, consistent) theories. Even if you are true in all the natural numbers formulas to the axioms.

    This classic proof is a very early, original application of the arithmetic hierarchy theory to a general-logical problem. It appeared in 1953 in the Journal of Symbolic Logic.

    Construction of Turing Machines

    In 1963, Hasenjaeger built an Universal Turing machine out of old telephone relays. Although Hasenjaeger work on UTM's was largely unknown and he never published any details of the machinery during his lifetime, his family decided to donate the machine to the in Paderborn, Germany, after his death.In a academic paper presented at the International Conference of History and Philosophy of Computing Rainer Glaschick, Turlough Neary, Damien Woods, Niall Murphy had examined Hasenjaeger's UTM machine at the request of Hasenjaeger family and found that the UTM was remarkably small and efficiently universal. Hasenjaeger UTM contained 3-tapes, 4 states, 2 symbols and was an evolution of ideas from Edward F. Moore's first universal machine and Hao Wang's B-machine. Hasenjaeger went on to build a small efficient Wang B-machine simulator. This was again proven by the team assembled by Rainer Glaschick to be efficiently universal.

    Commenting on the Engima Machine weakness

    It was only in the 70's that Hasenjaeger learned that the Enigma Machine had been so comprehensively broken. It impressed him that Alan Turing himself, considered one of the greatest mathematicians of the 20th century, had worked on breaking the device. The fact that the Germans had so comprehensively underestimated the weaknesses of the device, in contrast to Turing and Welchmans work, was seen by Hasenjaeger today as entirely positive. Hasenjaeger stated:

    Would it not been so, then the war would have lasted probably longer and the first atomic bomb had not fallen on Japan, but on Germany.


    Further reading

    • Rebecca Ratcliffe: Searching for Security. The German Investigations into Enigma's security. In: Intelligence and National Security 14 (1999) Issue 1 (Special Issue) S.146-167.
    • Rebecca Ratcliffe: How Statistics led the Germans to believe Enigma Secure and Why They Were Wrong: neglecting the practical Mathematics of Ciper machines Add:. Brian J. angle (eds.) The German Enigma Cipher Machine. Artech House: Boston, London of 2005.

    External links