K6 Buch für die Informatik PDF

Preview

Summary

Download K6 Buch für die Informatik PDF

Description

Sind alle Arbeiten, die vorstellbar sind, auch auf einem Rechner programmierbar? Gibt es Grenzen für den Computereinsatz? Können Computerprogramme denken? Ist das menschliche Gehirn ein Computer? Können Computer lachen?

510

Ausblick – Computer: Chancen und Grenzen

6.1

Grenzen der Programmierung und der Informatik

1993 begannen Bund und Länder die Entwicklung eines einheitlichen Softwaresystem für die rund 650 Finanzämter der Bundesländer. Zuletzt arbeiteten 40 verbeamtete und 150 angestellte Steuerfachleute, Programmierer und Softwareentwickler im Projekt FISCUS („Föderales Integriertes Standardisiertes Computer-Unterstütztes Steuersystem“); es wurde jedoch nie fertig entwickelt. Über einen Zeitraum von zwölf Jahren gab die öffentliche Hand rund 900 Millionen Euro Entwicklungskosten, ohne ein brauchbares Ergebnis zu erhalten. Der Bundesrechnungshof beanstandete seit dem Jahr 2000 die FISCUS-Entwicklung – ohne ernsthafte Folgen. Im Jahr 2000 wurde die Entwicklung der mit dem eingesetzten Personal neu gegründeten privaten fiscus GmbH übertragen. Bis zum Jahr 2004 erstellte die fiscus GmbH einige Teilanwendungen, darunter die OnlineStammdatenabfrage, ein Programm für die Grunderwerbssteuer und ein Programm für Bußgeldverfahren und Strafsachen, ohne das Gesamtprogramm vorlegen zu können. Deshalb beschloss die Finanzministerkonferenz 2005, die fiscus GmbH zu liquidieren und ein neues Projekt KONSENS (Koordinierte neue Softwareentwicklung der Steuerverwaltung) zu starten. Die abgestellten Beamten wurden wieder in den Finanzverwaltungen eingesetzt, die Angestellten entlassen. Damit scheiterte das „aufwendigste Informationstechnik-Projekt in der Verwaltung der Bundesrepublik Deutschland,“ wie es der Berliner Landesrechnungshof nannte. Warum haben sich so viele Fachleute bei der Einschätzung einer informatischen Entwicklungsaufgabe derart verschätzt? Mit einiger Übung und Erfahrung lernen Softwareentwickler doch, den Aufwand zur Bewältigung einer Aufgabe abzuschätzen. Wieso kommt es dann immer wieder zu gewaltigen Fehleinschätzungen, sodass die Entwicklung eines fertigen Programms viel länger dauert als ursprünglich erwartet und die Kosten den ursprünglich gesetzten Rahmen weit überschreiten? FISCUS ist kein Einzelfall, es ist nur ein besonderes schwerwiegendes Beispiel solcher Fehleinschätzungen. Der finanzielle und zeitliche Rahmen, den die Auftraggeber gesetzt haben, ist bei FISCUS nach 12 Jahren und fast eine Milliarde Euro an seine Grenzen gestoßen, ohne ein brauchbares Produkt zu liefern. Nun glaubt niemand, dass die Prozesse der Steuerverwaltung nicht durch Programme abgebildet und unterstützt werden können. Hier ist vor allem der Arbeits- und Abstimmungsaufwand unterschätzt worden. Angesichts eines solchen Scheiterns stellen sich aber einige grundsätzliche Fragen zur Programmierung und zum Informatikeinsatz. (A) Sind alle Arbeiten, die vorstellbar sind, auch auf einem Rechner programmierbar? (B) Ist alles, was sich prinzipiell mit Papier und Bleistift berechnen lässt, programmierbar? (C) Wie viel Aufwand ist nötig, um ein solches Programm zu entwickeln? (D) Welche Grenzen des Programmierbaren oder der Informatik gibt es?

Grenzen der Programmierung und der Informatik

6.1.1 Theoretische Grenzen Programmierbarkeit und Berechenbarkeit Es ist leicht, Aufgaben zu nennen, für die man keine erfolgreiche Vorgehensweise kennt, um sie zu programmieren: Korrekte Übersetzung vom Deutschen ins Französische gehört sicher zu den ungelösten Aufgaben, ebenso der mathematische Beweis der Existenz unendlich vieler Primzahlzwillinge. Kann ein Computerprogramm diese Aufgaben lösen? Zurzeit sicher nicht und man könnte sich zurücklehnen und sagen: „Noch nicht!” Oder mit dem gleichen Recht, nämlich keinem, erklären: „Niemals!” Die Frage A, ob alles Denk- und Wünschbare programmierbar sei, scheint weitgehender als die Frage B, ob alles Berechenbare programmierbar sei. Um dies mit Sicherheit sagen zu können, müsste man aber wissen, was denn „berechenbar” ist. Diese Frage hat sich tatsächlich der bedeutendste Mathematiker am Ende des neunzehnten Jahrhunderts gestellt. Der Göttinger Mathematikprofessor DaviD Hilbert (1862 – 1943) schlug ein „Grundlagenprogramm” der Mathematik vor, das u. a. eine präzise Klärung des Begriffs „Berechenbarkeit” erstellen sollte. Die Frage erwies sich als äußerst schwierig. In den ersten Jahrzehnten des zwanzigsten Jahrhunderts wurden unterschiedliche Vorschläge für diese Präzisierung vorgestellt. Der aus heutiger Sicht spannendste Vorschlag kam 1936 von dem jungen britischen Mathematiker alan MatHison t uring (1912 – 1954), der in seiner Veröffentlichung „On computable numbers with an application to the Entscheidungsproblem“ eine Papiermaschine beschrieb, die das Rechnen mit Bleistift und Radiergummi auf Karopapier formalisiert. Er argumentierte, dass eine Maschine mit einem unbegrenzt großen Vorrat an Karopapier und einem endlichen Satz einfacher Regeln, einem Programm, wie man heute sagen würde, gerade so wie ein menschliches Gehirn arbeitet, wenn es nach einem erlernten Verfahren rechnet. Diese „Turingmaschine” erwies sich bis heute als äquivalent (oder überlegen) zu allen anderen Vorstellungen von Berechenbarkeit, so dass man heute „Turing-Berechenbarkeit” als eine Art Definition der Berechenbarkeit interpretiert. Ein exakter Beweis, dass dies nun alles sei, was berechenbar ist, ist allerdings nicht möglich – dazu ist ein so schillernder Begriff wie „Berechenbarkeit” zu vage. Interessant ist, dass t urings Papiermaschine recht gut mit einem modernen programmierbaren Computer vergleichbar ist. Auch ein Computer arbeitet nach den endlich vielen Regeln eines Programms, er beschreibt schrittweise einen Speicher (und löscht ihn gelegentlich) und solange man noch externe Speichermedien findet, kann man den Speicher nach Bedarf erweitern. Nicht-berechenbare Funktionen t uring konnte mit seiner Papiermaschine nachweisen, dass keineswegs jede definierbare mathematische Funktion über den natürlichen Zahlen oder einem endlichen Vorrat von Zeichen auch berechenbar ist. Benutzt

Zwei Zahlen heißen Primzahlzwilling, wenn sie beide Primzahlen sind und dazwischen nur eine einzige gerade Zahl liegt. So sind 3 und 5 Primzahlzwillinge, ebenso wie 17 und 19 oder 41 und 43. Es sind ziemlich viele Primzahlzwillinge bekannt und es wird vermutet, dass es beliebig viele gibt.

B

B

b Abschnitt 5.2.5, S. 471 ff.

511

512

Ausblick – Computer: Chancen und Grenzen

man den Begriff der mathematischen Abbildung, so folgt das aus der „Abzählbarkeit“ der Menge aller Programme. Es gibt zwar unendlich viele Programme, sie reichen aber trotzdem nicht aus, um alle definierbaren Funktionen zu programmieren. Anders ausgedrückt: Es gibt „nicht-berechenbare” Funktionen und damit „nicht-programmierbare” Aufgaben. Die Frage A, ob alles Vorstellbare auch programmiert werden kann, muss demnach negativ beantwortet werden. Damit wird für eine konkrete Fragestellung, wie der nach der Konstruktion einer menschenähnlichen Übersetzungsmaschine oder einem bestimmten mathematischen Beweis aber nichts Endgültiges ausgesagt. „Noch nicht!” oder „Niemals!” bleiben mögliche Meinungen zur prinzipiellen Programmierbarkeit, aber man sollte zurückhaltend mit starken Meinungsäußerungen umgehen, wenn man keine Idee hat, wie eine bestimmte Aufgabe denn programmiert werden könnte. Die Frage B, ob sich alles Berechenbare auch programmieren lässt, ist von t urings Ergebnis scheinbar nicht berührt, weil man diese Frage B ja gerade beantwortet, indem man eine präzise Turingmaschine angibt oder einen Computer explizit programmiert, um eine bestimmte Aufgabe zu lösen. Findet man so eine exakte Lösung mittels eines Programms, so wird der Rechner angeworfen und nur auf das Ergebnis gewartet. Die größten bis 2005 gefundenen Primzahlzwillinge besitzen über 51 000 Stellen. Zurzeit (2006) gibt es keinen anerkannten Beweis, dass es unendlich viele Primzahlzwillinge gibt, obwohl die Mehrzahl der Mathematiker das sicher erwartet. Dieses vertrackte Problem steht durchaus im Zentrum zahlentheoretischer Forschung. Ein 2004 veröffentlichter Beweisversuch von r. F. arenstorF enthält einen Fehler und wurde vom Autor zurückgezogen.

Oder gibt es da doch ein Problem? Wie wäre die Frage zu beantworten, ob es noch neue, bislang unbekannte Primzahlzwillinge gibt? Das ist im Prinzip ganz einfach: Um zu erkennen, ob eine Zahl n (größer 3) eine Primzahl ist, testet man einfach mit einem Programm, ob sie durch eine kleinere Zahl (außer 1) teilbar ist. Anschließend testet man, ob n – 2 eine Primzahl ist. Falls es unendlich viele Primzahlzwillinge gibt, wird nach hinreichend langer Rechenzeit stets ein neuer Zwilling gefunden. Da man aber wenig über die Lücken zwischen benachbarten Primzahlzwillingspaaren weiß, kann dieses Verfahren sehr lange dauern – vielleicht viel länger als der Computer das aushält. Schlimmer wird es freilich, falls es gar nicht unendlich viele Primzahlzwillinge geben sollte; dann rechnet das kleine Programm, nachdem es den größten Primzahlzwilling ermittelt hat, immer weiter, ohne jemals ein weiteres Ergebnis zu erzielen. Aber das weiß man nicht und die Frage B, ob nämlich alles Berechenbare auch programmierbar sei, lenkt auf ein unentscheidbares Problem: Man weiß bei manchen wohldefinierten Rechenvorgängen und ihren entsprechenden Programmen nicht, ob sie jemals enden werden.

Grenzen der Programmierung und der Informatik

513

Komplexität und eingesetzte Mittel Der Aufwand, den ein Programm an Zeit oder Speicherplatz verbraucht, kann beachtlich werden. In manchen Fällen ist nicht vorherbestimmbar, ob die einsetzbaren Mittel überhaupt ausreichen, etwa bei der Frage nach dem „nächsten” Primzahlzwilling. Aber auch, wenn man weiß, dass es eine Lösung geben muss, können Zeit oder Speicherbedarf über handhabbare Grenzen hinauswachsen. Manche Fragestellungen haben einen Rechenaufwand, der unabhängig von der Eingabe ist. So kann man nahezu mühelos zu jeder negativen Zahl –n ihr positives Gegenstück +n angeben. Man vertauscht einfach das Minuszeichen mit einem Pluszeichen. Solche Probleme gelten, ebenso wie Fragen, deren Rechenaufwand bloß linear mit der Länge der Eingabe wächst, als gut skalierbar. Ein einfaches Beispiel für lineare Skalierbarkeit ist die Addition zweier gleich langer Zahlen. Für jede Ziffer sind maximal drei Ziffern zu addieren, nämlich die beiden Eingaben und ein eventueller Übertrag. Damit wächst der Aufwand n des Addierens linear mit der Länge n der Eingaben. Dieses Wachstum heißt lineares Wachstum. Anders sieht es beim Multiplizieren nach der üblichen Schulmethode durch Verschieben und Addieren aus: Hier müssen n Additionen für eine Multiplikation mit n Stellen ausgeführt werden. Bei zwei gleich langen Eingaben müssen also n2 Operationen ausgeführt werden; die Komplexität dieses Verfahrens wächst quadratisch. Oft wird versucht, solche Komplexitäten zu reduzieren. In einem fairen Fußballturnier müssten eigentlich alle Mannschaften gegen alle spielen. n(n-1) Spiele, wie aus dem Beispiel der Bei n Mannschaften wären das } 2 Tabelle für fünf Mannschaften ableitbar ist.

A

B

C

D

E

Bei den 32 Mannschaften der Weltmeisterschaft wären das 31·16 = 496 Spiele. Bei täglich fünf Spielen würde das Turnier dann einhundert Tage ohne Pause dauern. Als Ausweg werden Schichten gebildet – beginnend mit der Vorrunde, in der alle vier Mannschaften einer Gruppe gegen alle anderen Gruppenmitglieder spielen. Das sind 8 Gruppen mit je 6 Spielen. Danach wechselt das Verfahren. Es folgt ein Auswahlsystem, bei dem sich nur noch Sieger treffen – vom Achtelfinale bis zum Finale. Dies sind

I

Das ist freilich keine untere Schranke für die Multiplikation. Es sind schnellere Multiplikationsverfahren zur maschinellen Programmierung bekannt.

514

Ausblick – Computer: Chancen und Grenzen

weitere 8 + 4 + 2 + 1 = 15 Begegnungen. Und weil Fußballregeln nicht immer logisch sind, gibt es ein zusätzliches Spiel um den 3. Platz. Die Gesamtzahl der Begegnungen wird so von 496 auf 64 begrenzt – eine handhabbare organisatorische Komplexitätsreduktion. Manche Probleme sind aber komplizierter. Sollen alle möglichen Kombinationen aus n verschiedenen Elementen gebildet werden, so wächst die Komplexität dieser Aufgabe exponentiell an. Würde ein Autohersteller ein Modell mit neun möglichen Ausstattungsvarianten wie heizbarem Außenspiegel, Automatikgetriebe, verschließbarem Tank, MP3-Spieler, Glasschiebedach, Biodieselmotor, getönten Scheiben, Liegesitzen oder Breitwandreifen anbieten und alle möglichen Kombinationen auf jeweils einer Katalogseite beschreiben, so besäße dieser Katalog einen Umfang von wenigstens 29 Seiten. Das ist ein 512 Seiten starker Katalog. Beim VW Golf bietet der Hersteller aber 12 Motorenvarianten, 4 Frontscheibenvarianten, 3 Türvarianten, 10 Radiovarianten usw. an. Einige Ausstattungen schließen sich wechselseitig aus, sodass 47 Ausstattungen unabhängig voneinander gewählt werden können. Ein vollständiger Katalog aller möglichen bestellbaren Golf-Varianten wüchse dann auf 247 Seiten an, also auf über 140 Billionen Seiten. Auch bei Volkswagen wird niemals alles gebaut werden, was möglich wäre. Solche exponentiell wachsenden Kombinationsprobleme sind auch mit den schnellsten Rechnern und den größten Platten und den schnellsten Druckern niemals bearbeitbar – sie bilden eine praktische Grenze der Komplexität und die Frage C lässt sich nicht mehr positiv beantworten. Es gibt Fragestellungen, deren programmierte Lösung mehr Mittel oder Zeit verlangen, als wir bereitstellen können. Erkennbare Grenzen der Programmierung und der Informatik

I

Nicht alles, was prinzipiell berechenbar ist, ist auch praktisch programmierbar. Man kann nur das mit Programmen bearbeiten, was in vernünftiger Zeit mit den vorhandenen Mitteln der Hardware und Software bearbeitet werden kann. Wenn diese stets beschränkten Mittel und Zeiten überschritten werden, muss man effektivere Verfahren finden – oder auf denkbare programmierte Lösungen verzichten. Weil man die Fragen A, B und C nicht positiv beantworten kann, gibt es prinzipielle Grenzen der Berechenbarkeit. Diese Grenzen sind grundsätzlich, wenn man nicht-berechenbare Funktionen programmieren will, oder sie hindern an einer praktischen Überwindung, wenn man auf unmäßige Mittelanforderungen stößt. Solange freilich immer mehr Aufwand in die Verbesserung der Mittel gesteckt wird, mag man auf Verbesserungen hoffen. Die wichtigste Verbesserung ist die fast gesetzmäßige Verbesserung der Hardware, die mit

Grenzen der Programmierung und der Informatik

großer Regelmäßigkeit schnellere Prozessoren und größere Speicher bereitstellt. Vieles, was jetzt nicht machbar erscheint, mag in zehn oder zwanzig Jahren mit besseren Prozessoren und größeren Speichern programmierbar werden. Wenn aber die Laufzeit, der Speicherbedarf oder die Zahl der Druckseiten exponentiell zum Umfang der Eingabedaten anwachsen, dann hilft auch ein noch so rasantes Wachstum der Mikroelektronik nicht weiter. Das Katalogbeispiel macht deutlich, dass es unmäßige Mittelanforderungen geben kann, die niemals erfüllt werden können. Leider ist es nicht einfach, eine prinzipielle Unlösbarkeit eines konkreten Problems oder seine praktische Unlösbarkeit nachzuweisen – und selbst dann kann es doch noch brauchbare Näherungslösungen geben. In der Frage der Übersetzung menschlicher Sprachen gibt es aber nicht einmal eine klare Zielfunktion, denn auch menschliche Übersetzer sind sich nicht immer einig, was denn eine gute Übersetzung ist. Näherungsweise mag ein Programm so eine Übersetzung erreichen – aber die konkreten Anforderungen können sehr verschieden sein, sodass man wohl immer nur Annäherungen der Übersetzung an das Original erreichen kann (mit Menschen wie mit Computern). Allerdings sind alle bislang vorgestellten Computerübersetzungen noch nicht einmal eine akzeptable Näherung an die durchschnittliche Leistung menschlicher Übersetzer.

6.1.2

Der industrielle Entwicklungsplan dazu heißt mooresches Gesetz: Alle 18 bis 24 Monate verdoppelt sich die Zahl der Transistorfunktionen auf einem Chip. Ohne diese Basis hätte man keine billigen, schnellen Computer.

Praktische, rechtliche und ethische Grenzen

Gibt es neben der Grenze der Berechenbarkeit und des rechnerischen Aufwandes weitere Grenzen für die Programmierung und die Informatik? (Frage D) Dazu muss man sich von der engen Vorstellung, Programmieren sei nur das Schreiben von Anweisungsfolgen für Rechnerhardware, lösen und die weiten Kontexte der Informatik betrachten. Dies kann hier nur gestreift werden. Eine Vertiefung müsste auf andere Disziplinen neben der Informatik zurückgreifen. Materielle Grenzen der Computertechnik Die technischen Möglichkeiten wachsen von Jahr zu Jahr, aber mit schnelleren Prozessoren und immer größer werdenden Speichern, wächst auch die Gefahr, dass diese materiellen Strukturen Fehler aufweisen. Das können Konstruktionsfehler sein, wie sie auch bei der Software allzu häufig zu finden sind, aber es können auch Ausfälle sein, weil Material nun einmal altert. Auch das beschränkt prinzipiell programmierbare Prozesse praktisch. Bei digitaler Technik gibt es glücklicherweise Methoden der Codierung, die Fehler entdecken oder gar korrigieren können. Leider sind diese Methoden sehr aufwendig, sodass beispielsweise eine Audio-CD nur zu einem Drittel Original-Aufnahmedaten trägt, aber zu zwei Dritteln mit fehlerkorrigierendem und fehlerentdeckendem Code beschrieben ist. Bei DVDs und Festplatten ist dieses Verhältnis von Nutzdaten zu Fehlerkorrekturen noch ungünstiger.

515

b auch „Grenzen der Anwendung von Informatik und informationsverarbeitender Technik“, S. 12

I

516

Ausblick – Computer: Chancen und Grenzen

Ökonomische und rechtliche Grenzen Die Frage nach den Grenzen der Informatik hat auch noch ganz andere Facetten. Im Hintergrund stehen vor allem ökonomische Fragen: Wie viel Geld und Zeit kann lohnend investiert werden, um mit den entstehenden Produkten diese Investition zurückzugewinnen? Das FISCUS-Projekt ist vor allem an diesen finanziellen und zeitlichen Grenzen gescheitert. Gelegentlich wird auf die alternative Entwicklung von Software als Freeware oder in Open-Source-Projekten hingewiesen, wo eine finanzielle Entschädigung entfallen kann, weil die Entwickler sich als Teil einer hilfreichen Gemeinschaft verstehen. Doch selbst wenn Entwickler auf eine materielle Entschädigung verzichteten, bliebe immer eine Grenze durch die für ein Projekt aufwendbare Zeit. Diese Ökonomie der Zeit kann niemals ignoriert werden. Neben ökonomischen Fragen gewinnen juristische Randbedingungen immer größere Bedeutung. Informatisches Handeln unterliegt nicht nur zivilrechtlichen Vertragsbedingungen und eventuellen Strafen, denn verkaufte Software muss versprochene Eigenschaften erfüllen und gemessen am Stand der Technik so fehlerarm wie möglich sein. Nachlässigkeiten können dem Produkthaftungsrecht unterliegen, nach dem Ersatz oder Reparatur zu leisten ist, aus dem aber auch Schadensersatzansprüche aus fehlerhaftem Verhalten von Software abgeleitet werden können. Unter Umständen kann Soft- und Hardware sogar strafrechtlich von Bedeutung sein. Dies gilt, wenn Software z. B. dazu dient, Daten auszuspähen (§ 202a Strafgesetzbuch), Daten unzulässig zu verändern (§ 303a StGB) oder Computersabotage (§ 303b StGB) zu unterstützen. Auch Programme und Geräte, die hauptsächlich zur Umgehung eines „wirksamen Kopierschutzes” dienen, dürfen nach dem Urhebergesetz (§ 95a UrhG) weder hergestellt noch in den Handel gebracht werden. Bei ihrer rechtswidrigen Benutzung drohen strafrechtliche Konsequenzen. StGB § 202a Ausspähen von Daten (1) Wer unbefugt Daten, die nicht für ihn bestimmt und die gegen unberechtigten Zugang besonders gesichert sind, sich oder einem anderen verschafft, wird mit Freiheitsstrafe bis zu drei Jahren oder mit Geldstrafe bestraft. (2) Daten im Sinne des Absatzes 1 sind nur solche, d...