# Gisbert Hasenjaeger

Gisbert F. R. Hasenjaeger (1er juin 1919 – 2 septembre 2006) est un mathématicien et logicien allemand. Indépendamment et simultanément avec Leon Henkin en 1949, il a développé une nouvelle preuve du théorème de complétude de Gödel pour la logique des prédicats$^,$. Il a travaillé comme assistant de Heinrich Scholz, à la section IVa de l'Oberkommando der Wehrmacht Chiffrierabteilung, et a été responsable de la sécurité de la machine Enigma.

## Vie personnelle

Gisbert Hasenjaeger étudie à l'école secondaire de Mülheim, où son père Edwin Renatus Hasenjaeger est un avocat et homme politique local. Après avoir terminé l'école en 1936, Gisbert se porte volontaire pour le service du travail. Il a été recruté pour le service militaire durant la Seconde Guerre mondiale, et a combattu comme artilleur dans la campagne de Russie, où il est grièvement blessé en janvier 1942. Après son rétablissement, en octobre 1942, Heinrich Scholz lui a obtenu un emploi dans le Département du Chiffre du Haut Commandement de la Wehrmacht (OKW/Chi), où il est alors le plus jeune membre à 24 ans. Il suit un cours de formation en cryptographie par Erich Hüttenhain, et est affecté dans la section IVa récemment fondée « Vérification de la sécurité des Procédures de Codage » sous la direction de Karl Stein, qui lui confie la vérification de sécurité de la machine Enigma$^,$. À la fin de la guerre, comme l'OKW/Chi est dissout, Hasenjaeger réussit à échapper à TICOM, l'opération des États-Unis visant à rassembler et saisir les savants et le matériel allemands capturés.
À partir de la fin de 1945, il étudie les mathématiques et en particulier la logique mathématique avec Heinrich Scholz à l'Université de Münster. En 1950, il obtient son doctorat avec une thèse intitulée Topological studies on the semantics and syntax of an extended predicate calculus puis valide son habilitation en 1953.
À Münster, il travaille comme assistant de Scholz et, plus tard, son co-auteur, pour l'écriture de l'ouvrage Fundamentals of Mathematical Logic dans la série Grundlehren de Springer (série Jaune de Springer-Verlag), qu'il publie en 1961 intégralement 6 ans après la mort de Scholz. En 1962, il devient professeur à l'université de Bonn, où il est directeur du nouveau Département de la Logique.
En 1962, le D$^r$ Hasenjaeger quitte l'Université de Münster pour prendre une chaire de professeur à l'Université de Bonn, où il est nommé Directeur du nouveau Département de la Logique et de la Recherche Fondamentale. En 1964/65, il passe un an à l'université de Princeton à l'Institute for Advanced Study. Ses étudiants en doctorat à Bonn comptent Ronald Jensen, son plus célèbre élève.
Il est devenu professeur émérite en 1984.

## Travaux
### Tests de sécurité de la machine Enigma

En octobre 1942, après le démarrage des travaux à l'OKW/Chi, Hasenjaeger est formé dans le domaine de la cryptologie, par le mathématicien Erich Hüttenhain, qui est largement considéré comme le plus important cryptologue allemand de son temps. Hasenjaeger est affecté au département nouvellement formé, dont la principale responsabilité est de tester les défenses et de contrôler la sécurité de leurs propres méthodes et appareils. Hasenjaeger est chargé, par le mathématicien Karl Stein, qui est également mobilisé à l'OKW/Chi, d'examiner si la machine Enigma possède des faiblesses cryptologiques, alors que Stein s'occupe d'examiner les machines Siemens et Halske T52 et Lorenz SZ-42. La machine Enigma qu'examine Hasenjaeger est un modèle utilisant trois rotors et n'ayant pas de tableau de fiches. L'Allemagne a vendu cette version à des pays neutres dans le but d'accumuler des devises. Hasenjaeger teste avec un message chiffré de 100 caractères pour l'analyse et constate une faiblesse qui permet l'identification du câblage des rotors et également les positions de rotor, et donc de déchiffrer les messages. Mais ses succès s'arrêtent là. Il n'a fondamentalement pas réussi à identifier la plus importante faiblesse de la machine Enigma : le manque de points fixes (lettres chiffrées en elles-mêmes) en raison du réflecteur. Hasenjaeger pourrait trouver un certain réconfort dans le fait que même Alan Turing a raté cette faiblesse. Au lieu de cela, le mérite en a été attribué à William Gordon Welchman, qui a utilisé les connaissances nécessaires pour décrypter plusieurs centaines de milliers de messages Enigma pendant la guerre. En fait des points fixes ont été précédemment utilisé par le cryptanaliste polonais, Henryk Zygalski, comme la base de sa méthode d'attaque sur le chiffrement Enigma, nommée par les Polonais les "Feuilles de Zygalski" (płachty Zygalskiego) et par les britanniques comme la "méthode Netz".

### Preuve du théorème de complétude de Gödel

C'est durant la période où Hasenjaeger travaille à l'Université de Münster de l'Université de Münster, entre 1946 et 1953, que Hasenjaeger fait un des plus étonnantes découvertes : une démonstration du théorème de complétude de Gödel pour la logique des prédicats. La preuve de Gödel de 1930 pour la logique des prédicats n'établit pas automatiquement une procédure pour le cas général. Quand il résout le problème à la fin de 1949, il est frustré de constater qu'un jeune mathématicien Américain Leon Henkin, avait également établi une preuve. Tous deux ont construit leur preuve à partir d'une extension d'un modèle de terme, qui est alors le modèle initial de la théorie. Bien que la preuve de Henkin soit considérée par Hasenjaeger et ses pairs comme étant plus flexible, celle de Hasenjaeger est considérée comme plus simple et plus transparente.
Hasenjaeger continue à affiner sa preuve jusqu'en 1953 quand il réalise une percée. Selon les mathématiciens Alfred Tarski, Stephen Cole Kleene et Andrzej Mostowski, la hiérarchie arithmétique des formules est l'ensemble des propositions arithmétiques qui sont vraies dans le modèle standard, mais pas de manière arithmétiquement définissable. Alors, que signifie le concept de vérité pour le modèle de terme, pour les résultats l'arithmétique de Peano, axiomatisée de manière récursive, grâce à la méthode de Hasenjaeger ? Le résultat est que le prédicat de vérité est bien arithmétiquement, il est même. Si loin dans la hiérarchie arithmétique, et s'applique à toutes les théories récursivement axiomatisées (dénombrable, conforme).
Cette preuve classique est une des premières et originale application de la théorie de la hiérarchie arithmétique à un problème de logique. Elle est apparue en 1953 dans le Journal of Symbolic Logic.

## Construction de machines de Turing

En 1963, Hasenjaeger construit une machine de Turing universelle (MTU) à partir de vieux relais de téléphone. Bien que le travail de Hasenjaeger sur les MTU reste en grande partie inconnue et qu'il n'a jamais publié les détails de la machine au cours de sa vie, sa famille a décidé de faire don de la machine au Musée Heinz Nixdorf de Paderborn, en Allemagne, après sa mort$^,$. Dans un article présenté à la Conférence internationale d'histoire et de philosophie de l'informatique Rainer Glaschick, Turlough Neary, Damien Woods et Niall Murphy ont examiné la machine MTU de Hasenjaeger à la demande de la famille de Hasenjaeger et ils ont constaté qu'elle était remarquablement petite et efficacement universelle. La machine MTU de Hasenjaeger contenait 3 bandes, 4 états, 2 symboles et apportait une évolution des idées de la première machine universelle d'Edward F. Moore et de la B-machine de Hao Wang. Hasenjaeger a continué en construisant un petit simulateur efficace de la B-machine de Wang. Il a de nouveau été prouvé par l'équipe constituée par Rainer Glaschick qu'il était efficacement universel.

### Commentaires sur la faiblesse de la machine Enigma

C'est seulement dans les années 1970 que Hasenjaeger apprend que la machine Enigma avait été si globalement cassée. Cela l'a impressionné qu'Alan Turing lui-même, considéré comme l'un des plus grands mathématiciens du XXe siècle, ait travaillé à casser le fonctionnement de la machine. Le fait que les Allemands avaient donc globalement sous-estimé les faiblesses de l'appareil a été vu par Hasenjaeger a cette période comme tout à fait positif. Hasenjaeger a déclaré:
    « Si cela n'avait pas été ainsi, alors la guerre aurait duré probablement plus de temps et la première bombe atomique ne serait pas tombée sur le Japon, mais sur l'Allemagne. »