Der Beginn des modernen Rechnens

VWir werden hier über den paradoxen Beginn der modernen Informatik berichten. Und ich sage paradox, weil sie nicht entstanden ist, als man nach einer effizienten Methode zur Berechnung suchte, sondern als man versuchte, zu zeigen, dass es unlösbare Probleme gibt.

Der Held dieser Geschichte ist ein Mann namens Alan Turing, der bereits in einem Hollywood-Film namens "The Imitation Game" eine Rolle spielte.Das Imitationsspielund besitzt einen Preis für Informatik mit seinem Namen, den Turing-Preis, der jährlich an einen Forscher verliehen wird, der sich auf diesem Gebiet hervorgetan hat. Im Jahr 1937 bewies er mathematisch, dass es Probleme gibt, die nicht berechnet werden können. Um dies jedoch zu tun, musste er festlegen, was "berechenbar" bedeutet, und dabei die Turing-Maschinen geschaffen. Diese Maschinen sind abstrakte mathematische Konzepte, die den Begriff der Berechnung formalisieren, und ein wichtiger mathematischer Beweis zeigt, dass es eine spezielle Maschine gibt, die sogenannte Turing-Universelle Maschine, die eine zentrale Rolle in der Theorie der Berechnung spielt. Diese Turing-Universelle Maschine ist die Grundlage für den Bau der Computer, wie wir sie heute kennen.

Der ursprüngliche Artikel von Turing enthält einige Dinge, die Aufmerksamkeit erregen und die auch im Titel des Artikels selbst enthalten sind, der hier frei übersetzt lautet:Über berechenbare Zahlen und eine Anwendung auf das EntscheidungsproblemWas genau sind berechenbare Zahlen? Meint das, dass es nicht berechenbare Zahlen gibt?

Ja, und das ist gar nicht so schwer zu erkennen. Aber zuerst wollen wir kurz in die Vergangenheit reisen, denn die Anfänge der Berechnung sind eng mit unendlichen Zahlen verbunden. Im Jahr 1874 veröffentlichte der deutsche Mathematiker Georg Cantor einen Artikel, in dem er zeigte, dass es mehr als eine Art von Unendlichkeit gibt. Insbesondere zeigte er, dass die Unendlichkeit der natürlichen Zahlen 0,1,2,3... kleiner ist als die Unendlichkeit der reellen Zahlen. Vielleicht haben Sie das bereits bemerkt, aus einer einfachen Zeichnung. Die Unendlichkeit der reellen Zahlen entspricht einer kontinuierlichen Linie (dieser Menge wird als Kontinuum bezeichnet), und auf dieser Linie können wir die natürlichen Zahlen oder ganzen Zahlen (die Größe dieser anderen Unendlichkeiten wird als Zählbar bezeichnet) gut verteilt einsetzen. Mit einer sehr innovativen Strategie zeigte Cantor, dass es nicht möglich ist, die Elemente des Kontinuums nacheinander mit den Zählbar zu ordnen, immer bleibt ein Element übrig, das nicht ausgerichtet wird. Auf diese Weise zeigte er, dass das Kontinuum streng größer ist als die Zählbar.

Dann zeigt Turing, dass es reelle Zahlen gibt, die nicht berechenbar sind. Nicht berechenbare Zahlen sind immer Elemente des Kontinuums. Nach seiner Definition ist eine reelle Zahl berechenbar, wenn es ein Programm oder, in der ursprünglichen Version, eine Turingmaschine gibt, das unendlich viele seiner Ziffern ausgibt. Aber jedes Programm und jede Turingmaschine hat eine endliche Größe und wird in einer Datei gespeichert. Eine Datei ist nichts weiter als eine natürliche Zahl, die sehr groß sein kann. Die maximale Anzahl von Programmen ist eine abzählbare Unendlichkeit, und es kann nicht genügend Programme geben, um alle reellen Zahlen auszugeben. Viele reelle Zahlen können nicht von einem Programm oder einer Turingmaschine ausgegeben werden, und dies sind die nicht berechenbaren reellen Zahlen. Und wir wissen jetzt, dass die meisten reellen Zahlen nicht berechenbar sind, nur ein kleiner Teil davon kann von einem Programm oder einer Turingmaschine ausgegeben werden.

Eine kleine Anekdote hier. Als Turing 1936 seinen Artikel schrieb, hatte ein weiterer berühmter Mathematiker, Alonzo Church, bereits die Existenz nicht berechenbarer Zahlen nachgewiesen, wobei er sehr unterschiedliche Techniken verwendete. Die Herausgeber der Zeitschrift standen daher vor der Frage, ob der Artikel von Turing wirklich originell war. Der Artikel lag für eine Weile auf einem Tisch, bis jemand die Idee hatte, diesen Artikel dem eigenen an Church zu zeigen, der die Idee von Turing so originell fand, dass er ihn zu seinem Doktorand in den Vereinigten Staaten einlud. Aufgrund dieser Verzögerung wurde der Artikel erst 1937 veröffentlicht. Turing schloss sein Doktorat in einem Jahr ab und kehrte nach England zurück, als der Zweite Weltkrieg ausbrach. Dies ist der Beginn der Geschichte des Films.Das Spiel der ImitationNachdem Turing bereits einen bedeutenden Beitrag zur Geschichte der modernen Informatik geleistet hatte.

Zurück zu den Zahlen: Die erste Reaktion der Leute, wenn sie erfahren, dass es nicht berechenbare Zahlen gibt, ist: "Zeigen Sie mir bitte ein Beispiel für eine nicht berechenbare Zahl". Und ich antworte mit Freude: "Ich kann Ihnen kein Beispiel zeigen. Wenn ich Ihnen ein Beispiel zeige, habe ich gerade eine nicht berechenbare Zahl berechnet. Und eine nicht berechenbare Zahl kann nicht berechnet werden. Ist das nicht offensichtlich? Nun, wenn das nicht offensichtlich ist, müssen Sie sich mit der Vorstellung abfinden, dass Sie niemals eine nicht berechenbare Zahl sehen können, genau weil sie nicht berechenbar ist."

Aber, wenn die Zahl nicht berechenbar ist, wie beziehen wir sie dann? Nun, wir müssen indirekte Formen verwenden, um die Zahl zu definieren, ohne etwas zu berechnen. Ein sehr berühmtes Beispiel ist "die Wahrscheinlichkeit, dass ein Computerprogramm stoppt". Dieser Ausdruck in Anführungszeichen ist die Definition der Zahl. Es wird gezeigt, dass dies eine nicht berechenbare Zahl ist, über die wir fast nichts wissen können. Es ist nicht möglich zu wissen, ob diese Zahl größer oder kleiner als 0,5 oder 0,00000001 ist. Alle diese Fragen sind ebenfalls nicht berechenbare Fragen.

Und das führt uns zurück zum ursprünglichen Artikel von Alan Turing. Er zeigte, dass es nicht berechenbare Probleme gibt, d. h. Probleme, die von keiner Turing-Maschine gelöst werden können, einschließlich des berühmten Entscheidungsproblems (der ersten Ordnung) in seinem Artikel.

Und so entstand die moderne Informatik, die zeigte, dass die Informatik Grenzen hat. Es gibt Dinge, die niemals berechnet werden können, und wir müssen innerhalb der Grenzen leben, was mit einer Computer-Maschine möglich ist. Der Turing-Theorem hängt von keiner Programmiersprache oder jedem Computer ab. Daher bleiben nicht berechenbare Probleme mit jeder Technologie nicht berechenbar, selbst mit der modernsten künstlichen Intelligenz oder den Technologien, die in einem Jahrhundert entwickelt werden.

________________
(Die in den Artikeln veröffentlichten Meinungen imJornal da USPDie vollständige Verantwortung für diese Artikel liegt bei ihren Autoren und spiegeln keine Meinungen der Publikation oder institutionellen Positionen der Universität São Paulo wider. Besuchen Sie hier unsereRedaktionsrichtlinien für Meinungsartikel.)