Gisbert Hasenjaeger

Gisbert F. R. Hasenjaeger
Gisbert F. R. Hasenjaeger
	Picture of Gisbert Hasenjaeger in his identity papers during his time at OKW/Chi
Born	June 1, 1919; Hildesheim
Died	September 2, 2006 (aged 87); Münster, Westphalia
Citizenship	German
Alma mater	Münster University
Known for	Testing the Enigma encryption machine for cryptographic weaknesses.; Developing a proof of the completeness theorem in 1949.
	Scientific career
Fields	Mathematics; Logic
Institutions	Münster University; University of Bonn ; University of Princeton
Doctoral advisor	Heinrich Scholz
Doctoral students	Alexander Prestel; Ronald Jensen
Influences	Alan Turing

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.[1][2] He worked as an assistant to Heinrich Scholz at Section IVa of Oberkommando der Wehrmacht Chiffrierabteilung, and was responsible for the security of the Enigma machine.[3]

Personal life

Gisbert Hasenjaeger went to high school in Mülheim, where his father Edwin Renatus Hasenjaeger was a lawyer and local politician. After completing school in 1936, Gisbert volunteered for labor service. He was drafted for military service in World War II, and fought as an artillerist in the Russian campaign, where he was badly wounded in January 1942. After his recovery, in October 1942 Heinrich Scholz[4] got him an employment in the Cipher Department of the High Command of the Wehrmacht (OKW/Chi), where he was the youngest member at 24. He attended a cryptography training course by Erich Hüttenhain, and was put into the recently founded Section IVa "Security check of own Encoding Procedures" under Karl Stein, who assigned him the security check of the Enigma machine.[5][6] At the end of the war as OKW/Chi disintegrated, Hasenjaeger managed to escape TICOM, the United States effort to roundup and seize captured German intelligence people and material.[5]

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.[2]

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.[2]

In 1962, Dr. 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 at the Institute for Advanced Study[7] His doctoral students at Bonn included Ronald B. Jensen, his most famous pupil.[2]

He became professor emeritus in 1984.

Work

Safety Testing the Enigma Machine

In Oct 1942, after starting work at OKW/Chi, Hasenjaeger was trained in cryptology, given by the mathematician, 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.[5][8] 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.[8] 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 honour was attributed to Gordon Welchman, who used the knowledge to decrypt several hundred thousand Enigma messages during the war.[5][8] 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" (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.[2] 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.[2] 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.[2]

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 $\Delta _{2}^{0}$ .[2] 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 $\Pi _{1}^{0}$ 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.[9]

Construction of Turing Machines

In 1963, Hasenjaeger built a Universal Turing machine out of old telephone relays. Although Hasenjaeger's work on UTMs was largely unknown and he never published any details of the machinery during his lifetime, his family decided to donate the machine to the Heinz Nixdorf Museum in Paderborn, Germany, after his death.[10][11] In an academic paper presented at the International Conference of History and Philosophy of Computing[12] 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.

Comments on the Enigma Machine weakness

It was only in the 1970s that Hasenjaeger learned that the Enigma Machine had been so comprehensively broken.[5] 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.[5]

gollark: Unfortunately, your proof required the axiom of determinacy, which is bad.

gollark: We could always deploy multiplication by -1™ technology.

gollark: Besides, you don't have infinite *computers*.

gollark: Those don't work ever since we proved they couldn't work.

gollark: Ours don't waste compute on that.

References

"Past Professors at Münster University" (PDF). wwmath.uni-muenster.de. Retrieved 6 January 2014.
"Laudatio anläßlich der Erneuerung der Doktorurkunde". WWU Münster Mathematik: Logik. Retrieved 17 February 2014.
Schmeh, Klaus (15 September 2009). "Enigma's Contemporary Witness: Gisbert Hasenjaeger". Cryptologia. 33 (4): 343–346. doi:10.1080/01611190903186003. ISSN 0161-1194.
Hasenjaeger knew Scholz since his school days and corresponded with him during his time as a conscript.
"Enigma Contemporary Witness - Enigma Vulnerability Part 3". Heise online. Klaus Schmeh. 29 August 2005. Retrieved 2 March 2014.
Friedrich L. Bauer (2000). Entzifferte Geheimnisse — Methoden und Maximen der Kryptologie (3 ed.). Heidelberg: Springer. ISBN 978-3-540-67931-8. Cited from German Wikipedia
"IAS - Gisbert Hasenjeager". www.ias.edu. IAS. Retrieved 20 July 2016.
Cooper, S. Barry; Leeuwen, J. van (3 Jun 2013). Alan Turing: His Work and Impact: His Work and Impact. Elsevier Science. p. 936. ISBN 978-0-12-386980-7.
Hasenjaeger, G. (1953). "Eine Bemerkung zu Henkin's Beweis für die Vollständigkeit des Prädikatenkalküls der ersten Stufe". Journal of Symbolic Logic. 18 (1): 42–48. doi:10.2307/2266326. JSTOR 2266326. Gödel proof.
Neary, Turlough; Woods, Damien; Murphy, Niall; Glaschick, Rainer (October 2014). "Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy". Journal of Complexity. 30 (5): 634–646. arXiv:1304.0053. Bibcode:2013arXiv1304.0053N.
"Hasenjaeger's electromechanical small universal Turing machine is time efficient" (PDF). Department of History an Philosophy Universiteit Gent. Retrieved 18 March 2014.
http://www.computing-conference.ugent.be/