Alan Turings immerwährende Beiträge zu Computer, KI und Kryptografie

Links: Maschine, die wie eine altmodische Schreibmaschine in einer Kiste aussieht.  Rechts: Bild von Alan Turing zusammen mit einer Biografie.  Beide stammen aus einer Museumsausstellung.

Eine Enigma-Maschine, ausgestellt vor dem Eingang des Alan Turing Institute in der British Library, London.

Anerkennung:

©Shutterstock/William Barton

Angenommen, jemand bittet Sie, den leistungsstärksten Computer zu verwenden, der möglich ist. Alan Turing, dessen Ruf als zentrale Figur in der Informatik und der künstlichen Intelligenz seit seinem frühen Tod im Jahr 1954 nur gewachsen ist, wandte sein Genie auf Probleme wie dieses in einer Zeit an, bevor Computer, wie wir sie kennen, existierten. Seine theoretische Arbeit zu diesem und anderen Problemen bleibt eine Grundlage für Computer, KI und moderne kryptografische Standards, einschließlich der NIST-Empfehlungen.

Der Weg von der Entwicklung des leistungsstärksten Computers zu kryptografischen Standards hat einige Wendungen, ebenso wie Turings kurzes Leben.

Schwarz-Weiß-Kopfschuss von der Brust aufwärts.  Mann trägt Anzugjacke und Krawatte

Alan Turing

Anerkennung:

© National Portrait Gallery, London

Zu Turings Zeiten diskutierten Mathematiker darüber, ob es möglich sei, eine einzige Allzweckmaschine zu bauen, die alle berechenbaren Probleme lösen könne. Wir können zum Beispiel die energieeffizienteste Route eines Autos zu einem Ziel berechnen und die (im Prinzip) wahrscheinlichste Art und Weise, wie sich eine Kette von Aminosäuren zu einem dreidimensionalen Protein faltet. Ein weiteres Beispiel für ein berechenbares Problem, das für die moderne Verschlüsselung wichtig ist, ist, ob größere Zahlen als Produkt zweier kleinerer Zahlen ausgedrückt werden können oder nicht. Beispielsweise kann 6 als Produkt von 2 und 3 ausgedrückt werden, aber 7 kann nicht in kleinere ganze Zahlen zerlegt werden und ist daher eine Primzahl.

Einige prominente Mathematiker schlugen ausgefeilte Konstruktionen für universelle Computer vor, die nach sehr komplizierten mathematischen Regeln arbeiten würden. Es schien überwältigend schwierig, solche Maschinen zu bauen. Es bedurfte des Genies von Turing, um zu zeigen, dass eine sehr einfache Maschine tatsächlich alles berechnen kann, was berechenbar ist.

Sein hypothetisches Gerät ist heute als „Turing-Maschine“ bekannt. Das Herzstück der Maschine ist ein Bandstreifen, der in einzelne Kästchen unterteilt ist. Jedes Kästchen enthält ein Symbol (wie A, C, T, G für die Buchstaben des genetischen Codes) oder ein Leerzeichen. Der Bandstreifen ist analog zu den heutigen Festplatten, die Datenbits speichern. Zunächst entspricht die Symbolkette auf dem Band der Eingabe, die die Daten für das zu lösende Problem enthält. Die Zeichenfolge dient auch als Speicher des Computers. Die Turing-Maschine schreibt Daten auf das Band, auf die sie später in der Berechnung zugreifen muss.

12 Stände.  drei leer.  Nächste Kästchen ausgefüllt, ein Buchstabe pro Kästchen: T, C, A, A, G, C, T, G. Dann ein Leerzeichen.  Schwarzer Pfeil, der auf das zweite A zeigt

Anerkennung:

NIST

Das Gerät liest ein einzelnes Symbol auf dem Band und folgt den Anweisungen, ob das Symbol geändert oder in Ruhe gelassen werden soll, bevor zu einem anderen Symbol übergegangen wird. Die Anweisungen sind abhängig vom aktuellen „Zustand“ der Maschine. Wenn die Maschine beispielsweise entscheiden muss, ob das Band die Textzeichenfolge „TC“ enthält, kann sie das Band in Vorwärtsrichtung scannen, während sie zwischen den Zuständen „vorheriger Buchstabe war T“ und „vorheriger Buchstabe war nicht C“ umschaltet. Wenn es im Zustand „vorheriger Buchstabe war T“ ein „C“ liest, geht es in einen Zustand „gefunden“ und hält an. Wenn es am Ende der Eingabe auf das Leerzeichen stößt, geht es in den Zustand „nicht gefunden“ und hält an. Heutzutage würden wir den Befehlssatz als das Programm der Maschine erkennen.

Es dauerte einige Zeit, aber schließlich wurde allen klar, dass Turing Recht hatte: Die Turing-Maschine konnte tatsächlich alles berechnen, was berechenbar schien. Keine Anzahl von Ergänzungen oder Erweiterungen dieser Maschine könnte ihre Rechenleistung erweitern.

Um zu verstehen, was berechnet werden kann, ist es hilfreich zu identifizieren, was nicht berechnet werden kann. In einem früheren Leben als Universitätsprofessor musste ich einige Male Programmieren unterrichten. Studierende haben oft folgendes Problem: „Mein Studiengang läuft schon lange; steckt es fest?” Dies wird als Halteproblem bezeichnet, und die Schüler fragten sich oft, warum wir Endlosschleifen einfach nicht erkennen konnten, ohne tatsächlich in ihnen stecken zu bleiben. Es stellt sich heraus, dass ein Programm dazu unmöglich ist. Turing zeigte, dass es keine Maschine gibt, die erkennt, ob eine andere Maschine anhält oder nicht. Auf dieses bahnbrechende Ergebnis folgten viele andere Unmöglichkeitsergebnisse. Zum Beispiel mussten Logiker und Philosophen den Traum von einer automatisierten Methode aufgeben, um festzustellen, ob eine Behauptung (z. B. ob es unendlich viele Primzahlen gibt) wahr oder falsch ist, da dies nicht berechenbar ist. Wenn Sie das könnten, dann könnten Sie das Halteproblem lösen, indem Sie einfach fragen, ob die Aussage „diese Maschine hält an“ wahr oder falsch ist.

Turing leistete später grundlegende Beiträge zur KI, theoretischen Biologie und Kryptographie. Seine Beschäftigung mit diesem letzten Thema brachte ihm Ehre und Ruhm während des Zweiten Weltkriegs ein, als er eine sehr wichtige Rolle bei der Anpassung und Erweiterung kryptoanalytischer Techniken spielte, die von polnischen Mathematikern erfunden wurden. Diese Arbeit brach die deutsche Enigma-Maschinenverschlüsselung und leistete einen bedeutenden Beitrag zu den Kriegsanstrengungen.

Turing war schwul. Nach dem Krieg, 1952, verurteilte ihn die britische Regierung wegen Sex mit einem Mann. Er blieb nur aus dem Gefängnis heraus, indem er sich einer sogenannten „chemischen Kastration“ unterzog. Er starb 1954 im Alter von 41 Jahren an einer Zyanidvergiftung. was ursprünglich als Selbstmord eingestuft wurde, aber nach späterer Analyse möglicherweise ein Unfall war. Mehr als 50 Jahre sollten vergehen, bevor sich die britische Regierung entschuldigte und ihn „begnadigte“ (nach Jahren des Wahlkampfs von Wissenschaftlern auf der ganzen Welt). Heute heißt die höchste Auszeichnung in der Informatik Turing Award.

Turings Arbeit zur Berechenbarkeit lieferte die Grundlage für die moderne Komplexitätstheorie. Diese Theorie versucht, die Frage zu beantworten: „Welche von den Problemen, die von einem Computer gelöst werden können, können effizient gelöst werden?“ „Effizient“ bedeutet hier nicht in Milliarden Jahren, sondern je nach Rechenproblem in Millisekunden, Sekunden, Stunden oder Tagen.

Zum Beispiel beruht ein Großteil der Kryptographie, die derzeit unsere Daten und Kommunikation schützt, auf der Überzeugung, dass bestimmte Probleme, wie die Zerlegung einer ganzen Zahl in ihre Primfaktoren, nicht gelöst werden können, bevor sich die Sonne in einen roten Riesen verwandelt und die Erde verschlingt (derzeit Prognose für 4 bis 5 Milliarden Jahre). NIST ist verantwortlich für kryptografische Standards, die weltweit verwendet werden. Ohne die Komplexitätstheorie könnten wir diese Arbeit nicht leisten.

Die Technologie wirft uns manchmal eine Kurve, wie die Entdeckung, dass ein ausreichend großer und zuverlässiger Quantencomputer, wenn er gebaut wird, in der Lage wäre, ganze Zahlen zu faktorisieren und so einen Teil unserer Kryptographie zu brechen. In dieser Situation müssen sich NIST-Wissenschaftler auf die Experten der Welt (viele davon intern) verlassen, um unsere Standards zu aktualisieren. Es gibt tiefe Gründe zu der Annahme, dass Quantencomputer nicht in der Lage sein werden, die Kryptografie zu knacken, die NIST im Begriff ist, einzuführen. Einer dieser Gründe ist, dass Turings Maschine Quantencomputer simulieren kann. Dies impliziert, dass uns die Komplexitätstheorie Grenzen dafür setzt, was ein leistungsstarker Quantencomputer leisten kann.

Aber das ist ein Thema für einen anderen Tag. Im Moment können wir feiern, wie Turing die Schlüssel zu einem Großteil der heutigen Computertechnologie bereitstellte und uns sogar Hinweise gab, wie wir drohende technologische Probleme lösen können.

Leave a Comment

Your email address will not be published.