Praktische und prinzipielle Grenzen der Berechenbarkeit

Stand: 07.01.2007

Zeitrichtwert: 8 Unterrichtsstunden

Inhaltliche Schwerpunkte	Bemerkungen
Das RSA-Verfahren (2) Realisierung mit Produkten von Primzahlen Kryproanalyse durch Faktorisierung	Zur Verdeutlichung asymmetrischer Verschlüsselung wird das RSA-Verfahren betrachtet. Mit Hilfe von CrypTool werden kleine Nachrichten ver- und entschlüsselt. Nach der Behandlung des RSA-Verfahrens kann man den Schülerinnen und Schülern eine RSA-verschlüsselte Nachricht zur Entschlüsselung vorlegen. Nach der ersten Verblüffung, dass sie ein angeblich sicheres Verfahren 'knacken' sollen, werden sie über eine Faktorisierung zum Ziel kommen.
Praktische Grenzen der Berechenbarkeit (2) Zeit-Messungen an Faktorisierungen Analyse und Extrapolation der Messungen	In einem zweiten Schritt lässt man eine Tabelle der Rechenzeiten beim Faktorisieren der Produkte mit wachsender Stellenzahl erstellen. Die Rechenzeiten können z.B. mit dem Programm 'Derive' oder mit Hilfe selbst geschriebener Programme erfolgen, die auf der Langzahlarithmetik beruhen. Die Analyse der Daten erfolgt z.B. mit einer Tabellenkalkulation. Eine Extrapolation erbringt für gängige Schlüssellängen riesige Rechenzeiten in der Größenordnung von 10⁵⁰ Jahren.
Das Halteproblem (1)	Die Schülerinnen und Schüler erhalten fertige Programme, mit denen sie experimentieren können. Dabei sollen sie insbesondere den Fall untersuchen, wenn eine sehr große natürliche Zahl eingegeben wird (die etwa vom Lehrer vorgegeben wird). Programm 1: berechnet zu einer eingegebenen natürlichen Zahl die nächst größere Primzahl Programm 2: berechnet zu einer eingegebenen natürlichen Zahl das nächst größere Primzahlzwillingspaar Programm 3: berechnet zu einer eingegebenen natürlichen Zahl die nächst größere Primzahl, die nicht zu einem Vielfachen von 6 benachbart ist Bei einer sehr groß gewählten Eingabezahl hält (vorerst) keines der Programme. Zur Erklärung des Verhaltens der Programme werden folgende Aspekte erarbeitet: Das Programm hält, wenn man lange genug wartet bzw. das Programm hält nicht. Man weiß (kann begründen), dass das Programm hält bzw. nicht halten wird bzw. man weiß nichts über das Terminationsverhalten des Programms.
Programmierübung zum Halteproblem (2)	Ziel ist es, mit einfachen Analyseprogrammen das Haltproblem selbst sowie eine mögliche Vorgehensweise zu seiner Lösung zu verdeutlichen. Solche Analyseprogramme sollen Quelltexte von Programmen daraufhin untersuchen, ob sie bestimmte "kritische Eigenschaften" haben, die zu Endlosschleifen führen könnten (z. B. ob sie eine while-Schleife enthalten). Ein Beispiel für ein solches Analyseprogramm findet man in den Materialien zum Weiterbildungskurs 8.6. Anschließende wird diskutiert, wie vielversprechend dieser Ansatz ist. Es wird herausgearbeitet, dass Termination keine syntaktische Eigenschaft ist (die man am Quelltext ablesen kann), sondern eine semantische Eigenschaft (die offensichtlich viel schwieriger zu analysieren ist).
Unentscheidbarkeit des Halteproblems (1) prinzipielle Grenzen der algorithmischen Methode	Nach einer Recherche zum Thema "Halteproblem" werden die Ergebnisse zusammengetragen und besprochen: Termination (und auch Korrektheit) von Programmen können nicht mit einem universellen Algorithmus vorab entschieden werden. Auf eine mathematische Fundierung dieser Ergebnisse wird hier verzichtet. Zur Einordnung kann die folgende Aussage des bekannten Informatikers C. A. R. Hoare diskutiert werden: "Eine unzuverlässige Programmiersprache, aus der unzuverlässige Programme hervorgehen, bedeutet eine größere Gefahr für die Gesellschaft als unsichere Automobile, giftige Schädlingsbekäpfungsmittel oder undichte Reaktoren in Kernkraftwerken." Interessant ist auch ein Exkurs zur Tragweite der Ergebnisse und ein Vergleich mit anderen Wissenschaften. Die algoritschnische Problemlösemethode stößt an prinzipielle Grenzen: Sinnvoll gestellte Probleme wie das Halteproblem können nicht mit dieser Methode gelöst werden. In der Physik stößt die experimentell messende Methode an ihre Grenzen, wenn man in atomare Größenbereiche vorstößt: Ort und Geschwindigkeit eines Teilchens können nicht beliebig genau gemessen werden (Heisenbergsche Unschärferelation). In der Mathematik gibt es prinzipielle Grenzen für die beweisende Methode: Man kann z. B. nicht beweisen, dass die Mathematik widerspruchsfrei ist (Sätze von Gödel). Bemerkenswert ist auch, dass die Unlösbarkeit des Halteproblems bereits erkannt wurde, bevor es die ersten Rechner gab. Bei interssierten Schülerinnen und Schülern können hier Referate zur weiteren Vertiefung verteilt werden. Es muss aber beachtet werden, dass die mathematischen Hintergründe sehr komplex sind und sich so für eine eigenständige Bearbeitung durch Schülerinnen und Schüler wenig eignen.

Inhaltliche Schwerpunkte

Bemerkungen

Das RSA-Verfahren (2)

Realisierung mit Produkten von Primzahlen
Kryproanalyse durch Faktorisierung

Zur Verdeutlichung asymmetrischer Verschlüsselung wird das RSA-Verfahren betrachtet. Mit Hilfe von CrypTool werden kleine Nachrichten ver- und entschlüsselt.

Nach der Behandlung des RSA-Verfahrens kann man den Schülerinnen und Schülern eine RSA-verschlüsselte Nachricht zur Entschlüsselung vorlegen. Nach der ersten Verblüffung, dass sie ein angeblich sicheres Verfahren 'knacken' sollen, werden sie über eine Faktorisierung zum Ziel kommen.

Praktische Grenzen der Berechenbarkeit (2)

Zeit-Messungen an Faktorisierungen
Analyse und Extrapolation der Messungen

In einem zweiten Schritt lässt man eine Tabelle der Rechenzeiten beim Faktorisieren der Produkte mit wachsender Stellenzahl erstellen. Die Rechenzeiten können z.B. mit dem Programm 'Derive' oder mit Hilfe selbst geschriebener Programme erfolgen, die auf der Langzahlarithmetik beruhen.

Die Analyse der Daten erfolgt z.B. mit einer Tabellenkalkulation. Eine Extrapolation erbringt für gängige Schlüssellängen riesige Rechenzeiten in der Größenordnung von 10⁵⁰ Jahren.

Das Halteproblem (1)

Die Schülerinnen und Schüler erhalten fertige Programme, mit denen sie experimentieren können. Dabei sollen sie insbesondere den Fall untersuchen, wenn eine sehr große natürliche Zahl eingegeben wird (die etwa vom Lehrer vorgegeben wird).

Programm 1: berechnet zu einer eingegebenen natürlichen Zahl die nächst größere Primzahl
Programm 2: berechnet zu einer eingegebenen natürlichen Zahl das nächst größere Primzahlzwillingspaar
Programm 3: berechnet zu einer eingegebenen natürlichen Zahl die nächst größere Primzahl, die nicht zu einem Vielfachen von 6 benachbart ist

Bei einer sehr groß gewählten Eingabezahl hält (vorerst) keines der Programme. Zur Erklärung des Verhaltens der Programme werden folgende Aspekte erarbeitet:

Das Programm hält, wenn man lange genug wartet bzw. das Programm hält nicht.
Man weiß (kann begründen), dass das Programm hält bzw. nicht halten wird bzw. man weiß nichts über das Terminationsverhalten des Programms.

Programmierübung zum Halteproblem (2)

Ziel ist es, mit einfachen Analyseprogrammen das Haltproblem selbst sowie eine mögliche Vorgehensweise zu seiner Lösung zu verdeutlichen. Solche Analyseprogramme sollen Quelltexte von Programmen daraufhin untersuchen, ob sie bestimmte "kritische Eigenschaften" haben, die zu Endlosschleifen führen könnten (z. B. ob sie eine while-Schleife enthalten). Ein Beispiel für ein solches Analyseprogramm findet man in den Materialien zum Weiterbildungskurs 8.6.

Anschließende wird diskutiert, wie vielversprechend dieser Ansatz ist. Es wird herausgearbeitet, dass Termination keine syntaktische Eigenschaft ist (die man am Quelltext ablesen kann), sondern eine semantische Eigenschaft (die offensichtlich viel schwieriger zu analysieren ist).

Unentscheidbarkeit des Halteproblems (1)

prinzipielle Grenzen der algorithmischen Methode

Nach einer Recherche zum Thema "Halteproblem" werden die Ergebnisse zusammengetragen und besprochen: Termination (und auch Korrektheit) von Programmen können nicht mit einem universellen Algorithmus vorab entschieden werden. Auf eine mathematische Fundierung dieser Ergebnisse wird hier verzichtet.

Zur Einordnung kann die folgende Aussage des bekannten Informatikers C. A. R. Hoare diskutiert werden: "Eine unzuverlässige Programmiersprache, aus der unzuverlässige Programme hervorgehen, bedeutet eine größere Gefahr für die Gesellschaft als unsichere Automobile, giftige Schädlingsbekäpfungsmittel oder undichte Reaktoren in Kernkraftwerken."

Interessant ist auch ein Exkurs zur Tragweite der Ergebnisse und ein Vergleich mit anderen Wissenschaften.

Die algoritschnische Problemlösemethode stößt an prinzipielle Grenzen: Sinnvoll gestellte Probleme wie das Halteproblem können nicht mit dieser Methode gelöst werden.
In der Physik stößt die experimentell messende Methode an ihre Grenzen, wenn man in atomare Größenbereiche vorstößt: Ort und Geschwindigkeit eines Teilchens können nicht beliebig genau gemessen werden (Heisenbergsche Unschärferelation). In der Mathematik gibt es prinzipielle Grenzen für die beweisende Methode: Man kann z. B. nicht beweisen, dass die Mathematik widerspruchsfrei ist (Sätze von Gödel).
Bemerkenswert ist auch, dass die Unlösbarkeit des Halteproblems bereits erkannt wurde, bevor es die ersten Rechner gab. Bei interssierten Schülerinnen und Schülern können hier Referate zur weiteren Vertiefung verteilt werden. Es muss aber beachtet werden, dass die mathematischen Hintergründe sehr komplex sind und sich so für eine eigenständige Bearbeitung durch Schülerinnen und Schüler wenig eignen.