Triebkräfte der Digitalisierung
Der erste Beitrag dieses neuen Blogs (vielen Dank für den netten Zuspruch!) ist, zugegeben, etwas programmatisch ausgefallen. Die Betonung der Besonderheiten des digitalen Texts gegenüber seiner traditionellen Variante haben einige Kommentatoren annehmen lassen, dass ich mich in die neuerdings immer größer werdende Riege der Technologie-Kritiker einreihen möchte. Dem ist jedoch nicht so. Ich glaube zwar, dass die Digitalisierung große kulturelle Auswirkungen nach sich zieht, meine zugleich aber auch, dass dies zu einem Wandel führt, der nicht nach den Kategorien von Gut und Böse beurteilt werden kann. Welche Triebkräfte diesem Wandel durch die Digitalisierung aus meiner Sicht innewohnen, möchte ich mit meinem heutigen Beitrag erläutern.
Wenn Gutenberg im 15. Jahrhundert der Menschheit durch die Entwicklung des Buchdrucks mit beweglichen Lettern eine grundlegende kulturelle Umwälzung in Gang gesetzt hat, dann kommt dieses Verdienst fünfhundert Jahre später vielleicht auch Alan Turing zu. Der britische Mathematiker war ein genialer Entwickler und Ideengeber für die Computerentwicklung und die erste Phase der Informatik. Welthistorisch bedeutsam wurde seine Arbeit mit der Konstruktion einer Dechiffriermaschine, durch die während des Zweiten Weltkriegs die verschlüsselten Funksprüche der deutschen Wehrmacht von den Alliierten mitgelesen werden konnten. Dies war entscheidend dafür, dass die deutschen U-Boote ihre Dominanz im Nordatlantik verloren und der Seeweg von Amerika nach England abgesichert werden konnte. Später war er auch an der Entwicklung der frühen britischen Computer beteiligt und stellte als Erster Überlegungen zur Künstlichen Intelligenz an. Die nachhaltigste Wirkung in der Wissenschaft jedoch hatte Turing mit einem Aufsatz, der bereits 1937 erschienen war: On Computable Numbers, with an Application to the Entscheidungsproblem.[i] „The Entscheidungsproblem“ – das war eine der großen theoretischen Herausforderungen der damaligen Zeit. Es dreht sich dabei um die Frage, ob man für jedes mathematisch formulierbare Problem ein Berechnungsverfahren angegeben kann, bei dessen Anwendung man auch tatsächlich irgendwann ein Ergebnis erhält. Oder, auf Computer bezogen: Gibt es für jedes im Computer darstellbare Problem ein Programm, mit dem dieses Problem gelöst werden kann? Das hat unmittelbare praktische Auswirkungen. Turing hatte noch keinen Computer zur Verfügung, für den er dieses Problem so hätte formulieren können. Deshalb überlegte er sich das Modell für einen selbständig arbeitenden Mechanismus, mit dem man Berechnungen Schritt für Schritt durchführen kann – die sogenannte „Turing-Maschine“. Seitdem gelten Turing-Maschinen als eine Art Standard für die Formulierung von Berechnungsverfahren, von Algorithmen. Turing hatte dann den genialen Einfall, auf dem Papier eine allgemeine Turing-Maschine zu entwickeln, mit der unterschiedliche Turing-Maschinen für spezielle Berechnungen simuliert werden können, also eine Turing-Maschine für Turing-Maschinen. Damit gelang es ihm zu zeigen, dass eine solche allgemeine Turing-Maschine nicht in der Lage ist, für alle speziellen Turing-Maschinen anzugeben, ob ihre Berechnungen irgendwann zu einem Abschluss kommen. Es gibt also konkret formulierbare Probleme, die nicht mit einem Computerprogramm verlässlich gelöst werden können.
Mit der Turing-Maschine hat Turing das Rechnen mechanisiert – zumindest konzeptionell –, so wie Gutenberg seinerzeit das Schreiben mechanisiert hat. Turings Überlegungen sind bald darauf in die Architektur von Computern eingeflossen, bei denen Programme und Daten im selben Speicher liegen. Die Daten können Zahlen sein, der digitale Code kann aber auch für andere Arten von Daten stehen: für Schriftzeichen, Bild-, Ton-, Video-Daten und so weiter. Dem Computer selbst ist es gleichgültig, was die Nullen und Einsen in seinem Speicher bedeuten, er manipuliert sie nach den Vorschriften eines Programms. Computer waren deshalb von Anfang an nicht nur Rechenmaschinen, sondern allgemeine Datenverarbeitungsmaschinen.[ii] Die Fähigkeit, Daten automatisch zu manipulieren, bildet eine wesentliche Triebkraft der Digitalisierung: die Automatisierung. Der Informatiker Wolfgang Coy versteht dies als die erste Phase der Computernutzung[iii] – der Computer entsteht als ein Automat, in den Daten und Programme hineingegeben werden und der wiederum Daten als Ergebnis ausgibt. Die frühen Großrechner arbeiteten wie eine Black Box, in die man während ihrer Arbeit nicht eingreifen konnte. Die Automatisierung erstreckt sich auf alle Arten von Daten – zunächst auf Zahlen und Berechnungen, dann auf Texte, später auf Bilder, Klänge, Videos und alles andere. Alles, was digital kodiert werden kann, kann auch den Input bilden für automatische Berechnungs- und Manipulationsprozesse.
Eine zweite Stufe nahm die Computerentwicklung etwa 25 Jahre später. Beispielhaft dafür kann die Entwicklung des oN-Line-Systems durch Douglas Engelbart mit der Maus als bekanntester Hervorbringung oder des ersten grafikverarbeitenden Computers überhaupt, das SAGE-System, angesehen werden: die Integration von verschiedenartigen Daten und ihre unmittelbare Manipulation. Der Computer wurde zum Werkzeug, zu einem Gerät, das mit dem menschlichen Benutzer interagieren konnte. Dafür war es notwendig geworden, Daten unterschiedlicher Art – Zahlen, Schrift, Grafiken – dem Menschen in einer ihm zugänglichen Weise darzustellen. Das Grafik-Display, heute eine Selbstverständlichkeit jedes Computers, und die Bedienung per Tastatur und Maus, zusammengefasst als grafische Benutzeroberfläche bezeichnet, wurden zum neuen Leitbild der Computernutzung.
Die dritte Entwicklungsstufe schließlich wurde mit der Vernetzung der Computer seit Beginn der 1990er Jahre im World Wide Web eingeläutet. Zwar waren auch schon zuvor Computer über Datenleitungen miteinander verbunden, das Internet war bereits Ende der 1960er Jahre entwickelt worden. Doch in der Verbindung von Vernetzung und grafischer Benutzeroberfläche kommunizierten nicht mehr lediglich Rechner miteinander, Daten und Programme wurden vielmehr zu einem weltumspannenden Netzwerk von Informationen und Funktionen miteinander verwoben. Der Computer wurde damit zu einem Medium, das uns den Zugang dazu ermöglicht.
Automatisierung, Datenintegration und Vernetzung – das sind die Triebkräfte der Digitalisierung. Sie wurden zwar jeweils mit dem zeitlichen Abstand von etwa 25 Jahren wirksam, heute sind sie jedoch in jedem Computer, in jedem Smartphone, Laptop oder Tablet gleichzeitig vorhanden. Der Computer automatisiert für uns die Verarbeitung von Daten, wenn wir etwa von ihm die Silbentrennung in einem Text vornehmen oder die Wertentwicklung einer Geldanlage bei einer bestimmten Rendite berechnen lassen. Er ist ein Werkzeug, wenn wir über eine grafische Benutzerschnittstelle ein Dokument gestalten oder eine Anlageplanung interaktiv mit einem Tabellenkalkulationsprogramm durchführen. Und er ist ein Medium, wenn wir einen Text als E-Mail verschicken oder uns auf einer Web-Seite über das Kinoprogramm informieren. Der Computer ist eine universale Maschine, die Maschine aller Maschinen. Wir sind in den Besitz dieser mächtigen Maschine gelangt. Oder hat sie sich unserer bemächtigt?
[i] Alan Turing (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proc. London Mathematical Society 42, 42: 230–265..
[ii] Zur Rolle von Turing in der Entwicklung der frühen Computertechnologie vgl. George Dyson (2013): Turing’s Cathedral: The Origins of the Digital Universe. London: Penguin.
[iii] Vgl. Wolfgang Coy (1995): Automat – Werkzeug – Medium. Informatik Spektrum 18 (1): 31–38..
So in der Art, dass sie als Idee immer schon gelauert hat, und nun hervorspringt? – Philosophisch gibt es aber kein Lauern dieser Art und Ideen, die auch Maschinen bedeuten können, auch ‘Maschinen aller Maschinen’, Metamaschinen sozusagen, bleiben von Ideenträgern abhängig.
Ist so ähnlich wie mit der Mathematik (“Kunst des Lernens”) und der Naturlehre (“Naturgesetze” (sind gesetzt)).
Ansonsten, sehr solide Vorträge bisher, wie Ihr Kommentatorenfreund findet, und das ansonsten soll ‘im Übrigen’ meinen, nicht, dass etwas falsch (gefragt) war,
MFG
Dr. W
Computer führen Maschinenprogramme aus, die aus linearen Ketten von Befehlen mit sehr einfacher Bedeutung zusammengesetzt sind. Lebende Zellen führen einen Programmcode aus, der aus linearen Ketten von DNA-Bausteinen zusammengesetzt ist und die Bedeutung dieser DNA-Bausteine ist ebenfalls sehr einfach – so einfach, dass wir auch heute, 15 Jahren nach der völligen Entschlüsselung des menschlichen Genoms immer noch nicht viel über den Zusammenhang und das Zusammenarbeiten all dieser DNA-Schnipsel wissen. Auch das hat grosse Ähnlichkeit mit den von uns für Computer geschriebenen Maschinenprogrammen: Ein Gigabyte Programmcode in Form von Assemblerbefehlen verrät über die Funktion der Software ebenfalls sehr wenig.
Als Jugendlicher hatte ich den Gedanken, dass die Fabriken der Zukunft wie die Bäume und Wälder unserer natürlichen Umgebung heranwachsen werden und selbständig das herstellen, für das sie programmiert sind.
Und jetzt bewegen wir uns bereits auf diese Zukunft zu. In dieser Zukunft haben technische Systeme eine grosse Ähnlichkeit mit lebenden Systemen. Zuerst allerdings wird der Code, der diese Systeme steuert ein Produkt menschlicher Ingenieurkunst sein und unter völliger Kontrolle des Menschen ablaufen – also völlig anders als das in der biologischen Natur ist, wo es keine höhere Intelligenz gibt, die den Bäumen und Tieren sagt, was sie tun sollen. Irgendwann könnte aber auch dieses technische Second-Life, welches zuerst nur dem Menschen dient, ein Eigenleben bekommen – allerdings wird das noch einige Jahrzehnte, vielleicht sogar Jahrhunderte dauern bis es soweit ist.
Den Computer von der Mathematik her denken wie das im obigen Artikel gemacht wird, ist für den Menschen naheliegend, denn die Mathematik hat sich als Sprache der physikalischen Natur herausgestellt. Doch später werden wir Computer, Roboter und softwaregesteurte Maschinen immer mehr mit Lebewesen und Ökosystemen vergleichen und in einem letzten Schritt vielleicht den Zusammenhang von Mathematik und Leben begreifen.
Das Fachwort soll hier vielleicht einmal genannt werden:
Singularität
Manche meinen, dass es hierfür IT-Systeme der Größenordnung “Erde” geben müsste und einige Millionen bis Milliarden Jahre Laufzeit, günstige Bedingungen vorausgesetzt, vgl. auch Rule 110 und mit dieser ToE,
MFG
Dr. W
@Henning Lobin
Die folgende Formulierung im Text scheint mir etwas missverständlich:
»Oder, auf Computer bezogen: Gibt es für jedes im Computer darstellbare Problem ein Programm, mit dem dieses Problem gelöst werden kann?«
Im Sinne von Turing verstehe ich mal unter einem “im Computer darstellbaren Problem” eines von der Form (M,I) := “Turing machine M running input I”, wobei sowohl M wie auch I als endlich vorausgesetzt sind. Und in Hinblick auf das Entscheidungsproblem bedeutet die Frage nach einem Programm zur Lösung des Problems (M,I) einfach die nach einem Algorithmus, mit dem sich herausfinden liesse, ob (M,I) anhält oder nicht. Ihren obigen Wortlaut umformulierend hätte ich dann:
Gibt es für jedes (M,I) einen Algorithmus, mit dem sich entscheiden lässt, ob (M,I) anhält oder nicht?
Die Antwort darauf wäre eindeutig ja, für jedes (M,I) existiert so etwas. Turings Problem wäre hingegen dieses:
Gibt es einen Algorithmus, mit dem sich für jedes (M,I) entscheiden lässt, ob (M,I) anhält oder nicht?
Hier wäre dann Turings Antwort nein, ein solcher Algorithmus exitiert definitiv nicht.
Folglich meine ich, dass die Reihenfolge der Quantoren hier andersherum sein sollte. Weiter unten im Text stimmt es dann übrigens nach meinem Verständnis auch wieder:
»Damit gelang es ihm [Turing] zu zeigen, dass eine solche allgemeine Turing-Maschine nicht in der Lage ist, für alle speziellen Turing-Maschinen anzugeben, ob ihre Berechnungen irgendwann zu einem Abschluss kommen.«
@Chrys
“Gibt es für jedes (M,I) einen Algorithmus, mit dem sich entscheiden lässt, ob (M,I) anhält oder nicht?
Die Antwort darauf wäre eindeutig ja, für jedes (M,I) existiert so etwas.”
Dann hätte ich das bisher ja vollkommen falsch verstanden. Es ist klar, dass es (M,I) gibt, für die ein solcher Algorithmus existiert. Ich dachte aber auch, es müsse mindestens ein (M,I) geben, für das es keinen Algorithmus gibt, mit dem sich entscheiden ließe, ob die Maschine anhält. Und es gibt keinen Algorithmus mit dem sich herausfinden ließe, welche (M,I) das sind.
Hast Du eine Quelle (leicht verständlich, am beten populärwissenschaftlich formuliert), anhand derer ich das nachvollziehen könnte?
Ein sehr gute Darstellung des Entscheidungsproblems findet sich in John MacCormick (2012). Nine Algorithms that Changed the Future. The Ingenious Ideas that Drive Today’s Computers. Princeton: Princeton University Press, Kapitel 10, “What ist Computable?”.
Sie haben nach Wikipedia wahrscheinlich recht: Es scheint auch konkrete Programme und Eingaben zu geben, wo man nicht sagen kann ob das Programm hält.
Ein Beispiel ist (nach Wikipedia)
Das Programm hält immer, wenn die Collatz-Vermutung richtig ist, sonst aber nicht.
Es könnten nun nach Gödel so sein, dass die Collatz-Vermutung nicht entscheibar ist, also weder bewiesen noch widerlegt werden kann. Dann gäbe es logischerweise auch kein Programm, welches entscheiden kann ob das obige Programmfragment für eine bestimmte Eingabe hält oder nicht.
@Joker
Wenn ein (M,I) vorgegeben ist, dann hat man auch einen algorith. Weg, um herauszufinden, ob (M,I) anhält, nämlich indem man I auf M ausführt. Sofern (M,I) nur endlich viele Zustände annehmen kann, was für alle Belange praktischer Berechnung der Fall ist, hält das dann entweder an, oder es muss sich schliesslich etwas wiederholen. Was natürlich auch bedeuten kann, dass die Grenzen der Darstellbarkeit erreicht werden und die Berechnung daher abbricht.
Lassen wir das mit der Endlichkeit mal ausser acht, das könnte ich ja oben falsch verstanden haben, und das war gar nicht so gemeint. In diesem Fall hat man nur Turings Theorem von der Unentscheidbarkeit des Halteproblems. Das Theorem besagt, dass kein Algorithmus existiert, mit dem für alle (M,I) entscheidbar wäre, ob (M,I) anhält. Turings Beweis ist indirekt, er führt also die gegenteilige Annahme zu einem Widerspruch. Die Reihenfolge, in der dabei die Quantoren kommen, ist jedoch wesentlich.
Literatur, vielleicht wäre das etwas: Dirk W. Hoffmann, Grenzen der Mathematik. Springer, 2. Aufl. 2013. Ich kenne die 1. Aufl., Hoffmann bringt das Zeug ziemlich gut.
Wird das Problem nicht trivialisiert, wenn man die “Unendlichkeit” bei der Turing-Maschine (eine “abstrakte” Maschine”) eliminiert?
Wenn es für _alle_Fälle jeweils einen speziellen Algorithmus gibt, der die Haltefrage beantwortet, müßte es dann nicht einen Algorithmus geben, der diesen jeweils speziellen Algorithmus ermittelt? Wäre letzterer nicht dann der gesuchte Algorithmus, der für _alle_ Fälle das Halteproblem beantwortet?
Diesen Verdacht teile ich. Wenn man den Zahlbereich einschränkt auf z.B. 0 bis 2^16 oder 0 bis 2^32, dann begibt man sich ins Reich der endlichen Mengen. Dort gibt es aber viele Problem eines unendlich oder arbiträr grossen Lösungsraums gar nicht.
@Christoph Deblon
Andersrum formuliert, die Aspekte praktischer Berechnungen problematisieren das Verständnis von “im Computer darstellbar” oder “Lösung”.
Davon unbenommen bleiben freilich Aspekte theoret. Berechenbarkeit. Über das Halteproblem hinaus betrifft das beispielsweise Fragestellungen, für deren Beantwortung unberechenbare Zahlen von wesentlichem Belang sind. Auch ideale Computer kennen nur berechenbare Zahlen, und das schränkt sie ein.
Wenn eine Gesamtheit angenommener spezieller Halte-Vorhersage-Algorithmen selbst wiederum als ein Algorithmus angenommen wird, leistet dieser offenbar dasselbe wie Turings universelle Maschine beim Halteproblem. Aber warum sollte nun diese Gesamtheit so beschaffen sein? Heuristisch betrachtet, es ist doch nicht wirklich plausibel, dass mit einem einzelnen (M,I) die Grenze des Berechenbaren tatsächlich erreicht wird. Hat man aber eine unendliche Folge davon, dann kann man dieser Grenze womöglich beliebig nahe kommen, sodass die unendliche Gesamtheit diese Grenze eben doch tangiert, womit dann die “berechenbare Welt” gewissermassen transzendiert wird.
@Christoph Deblon
Wird das Problem nicht trivialisiert, wenn man die “Unendlichkeit” bei der Turing-Maschine (eine “abstrakte” Maschine”) eliminiert?
Klar sollte sein, dass weder eine Turing-Maschine noch ihr Input unendlich sein dürfen, beide sind endlich.
“Wenn es für _alle_Fälle jeweils einen speziellen Algorithmus gibt, der die Haltefrage beantwortet, müßte es dann nicht einen Algorithmus geben, der diesen jeweils speziellen Algorithmus ermittelt?”
Nein.
Ein Algorithmus ist endlich. Es könnte aber unendlich viele verschiedene spezielle Algorithmen geben. Einfach zusammenbasteln aller Algorithmen geht nicht, das würde zu etwas unendlich Langem werden, was per Definition kein Algorithmus sein kann.
Dass alle Algorithmen sich aus einem (endlichen) universellen Algorithmus generieren ließen, wäre ein zusätzliche Annahme, oder man müsste dessen Existenz ebenfalls erst beweisen.
Aber wie gesagt, ich denke je sowieso, dass schon die Bedingung ihres Konditionalsatzes nicht erfüllt ist.
Soweit ich orientiert bin, wird das Speicherband als unendlich angenommen. Daher entfällt, daß sich nach Chrys irgendwann eine Schleife einstellen muß, wenn die Maschine nicht anhält.
Wenn zu jeder Turingmadschine ein spezieller) Algorithmus existiert, der das Halteproblem beantwortet, sollte man über eine (endliche) Konstruktionsvorschrift für diesen Algorithmus verfügen. Falls nein, kann die Existenz des Algorithmus für jeden Fall bewiesen werden? Die (endliche) Konstruktionsvorschrift wäre der universelle Algorithmus.
Falls es einen speziellen Algorithmus gibt, der das Halteproblem beantwortet für eine Turingmaschine, die die Goldbachvermutung testet, wäre damit auch die Goldbachvermutung aufgeklärt. M.W. ist das bis heute nicht der Fall.
@Christoph Deblon
“Soweit ich orientiert bin, wird das Speicherband als unendlich angenommen.”
Nichtsdestotrotz muss der Input endlich sein, darf also nicht das ganze Band nutzen.
“Daher entfällt, daß sich nach Chrys irgendwann eine Schleife einstellen muß, wenn die Maschine nicht anhält.”
So hatte das @Chrys auch nicht formuliert. Er hatte nur gesagt, für Maschinen die nur endlich viele Zustände annehmen, müsse diese entweder anhalten oder in eine Schleife geraten. Damit hat er recht.
Und Sie haben natürlich recht, wenn man diese Beschränkung fallen lässt. Und sie haben natürlich auch recht, dass das erst die für das Halteproblem interessanten Fälle sind. (Während @Chrys vielleicht recht hat, dass die anderen die sind, die häufiger von praktischem Belang sind)
Bei einigen Algorithmen kann man ja auch zeigen, dass sie “über alle Grenzen wachsen”, will sagen: nicht halten. Womit das Halteproblem auch für diese durch eine Turingmaschine gelöst werden kann. Aber es gibt auf jeden Fall auch einige, bei denen wird man es nie wissen, ob oder ob nicht.
“Falls nein, kann die Existenz des Algorithmus für jeden Fall bewiesen werden?”
Der Versuch einer Analogie:
Für die überabzählbar vielen reellen Zahlen gilt, dass man nur für einen Bruchteil, nämlich abzählbar vielen von ihnen, eine Konstruktionsvorschrift generieren kann (und von ganz wenigen tatsächlich eine kennt), aber ihre Existenz scheint mir bewiesen.
So in etwa hätte ich mir das auch vorstellen können für die Existenz von Algorithmen mit bestimmten Eigenschaften.
“damit [wäre] auch die Goldbachvermutung aufgeklärt”.
Nicht unbedingt. Wenn man die Existenz eines Algorithmus nachweisen könnte, der das Halteproblem für die Goldbachvermutung löst, muss man, nach dem oben gesagten, weder den Algorithmus noch dessen Ergebnis kennen.
@Joker:
Warum so zurückhaltend? Den Beweis kann man Schwarz auf Weiß nachlesen:
http://us.metamath.org/mpegif/aleph1re.html
Ohne Bekenntnis zur Unendlichkeit [1] gelangen Sie allerdings gar nicht erst nicht in Cantors Paradies:
http://us.metamath.org/mpegif/mmtheorems61.html#mm6034s
[1] http://en.wikipedia.org/wiki/Axiom_of_infinity
@Ano Nym
“Warum so zurückhaltend?”
Wegen der Konstruktivisten. Die lassen indirekte Beweise nicht gelten, für sie ist die Existenz mathematischer Objekte durch ihre Konstruktion zu begründen. (Wikipedia, http://de.wikipedia.org/wiki/Konstruktive_Mathematik)
@Joker:
Wo ist der Beweis indirekt?
@Ano Nym
Unter anderem hier: http://us.metamath.org/mpegif/mmcomplex.html#uncountable
Der Autor arbeitet mit einer Liste, von der er weiß, bzw. zeigen kann, dass sie nicht existiert, “a purported list of all real numbers”.
@Joker: Das was Sie da haben ist eine reductio ad absurdum. Die ist wohl konstruktivistisch keine zulässige Schlussweise. Aber noch einmal zurück zu ihrem “Scheinen” (“Für die überabzählbar vielen reellen Zahlen […] scheint mir [aber ihre Existenz] bewiesen.”):
Sie drücken damit so etwas wie Unbestimmtheit oder (Ihre) Unsicherheit aus. Es ist aber nicht unbestimmt oder unsicher, ob “der” Konstruktivismus oder die Standard-Mengentheorie “gilt”. Es ist vielmehr sicher, dass in der Standard-Mengentheorie
http://us.metamath.org/mpegif/aleph1re.html
ein gültiger Beweis ist während er in konstruktivistischen Systemen keinen gültigen Beweis darstellt.
Im echten Leben wird ihnen weder die Menge der Natürlichen Zahlen noch die der Reellen Zahlen in irgendeiner Form begegnen, daher handelt es sich auch nicht um einen Konflikt, der irgendwie an der materiellen Welt entschieden wird. Dass gar ein Kampf zwischen “Konstruktivisten” und anderen Mathematikern ausgefochten würde, kann ich auch nicht erkennen. Es handelt sich bei beiden Gruppen um Formalisten, die untersuchen, welche Theoreme es in den verschiedenen Systemen gibt.
@Ano Nym
Mir scheint, Sie haben recht.
@Joker
Heuristisch etwas einfacher einzusehen als beim Halteproblem ist die Sache vielleicht noch bei Chaitins Theorem in der Algorith. Info.theorie, wonach es keinen Algorithmus zur Bestimmung der algorith. Komplexität eines bliebigen Binärstrings endlicher Länge geben kann. Für jeden einzelnen String dieser Art wäre das zwar ein Problem von endlicher algorith. Komplexität, aber für beliebige Binärstrings ist diese nicht mehr beschränkt. Da sich mit einem Programmcode endlichen Umfangs aber immer nur ein strikt begrenztes Mass an algorith. Komplexität ausdrücken oder erfassen lässt, muss jedes solche Programm irgendwann an der beim allgemeinen Problem unbegrenzten algorith. Komplexität scheitern.
In anderen Worten bedeutet das, es existiert keine algorith. Methode, mit der sich für eine beliebige, endliche Sequenz von Bits entscheiden liesse, ob diese zufällig ist oder nicht.
@Chrys
“Heuristisch etwas einfacher einzusehen als beim Halteproblem ist die Sache vielleicht noch bei Chaitins Theorem”
Chaitins Theorem ist ein gutes Beispiel für die hinzukommenden Schwierigkeit beim Übergang vom endlichen Einzelfall zu unendlich vielen endlichen Einzelfällen.
Beim Halteproblem sehe ich die Sache allerdings weder heuristisch noch anderweitig ein. Meine Überzeugung bleibt bestehen, es gibt hier NICHT für jedes (M,I) einen Algorithmus, der dies berechnet. Das Komplement “(M,I) hält nicht” ist nicht semi-entscheidbar. Entscheidbar ist das Halteproblem für einzelne (M,I), wenn man voraussetzt, dass diese nur endlich viele Zustände annehmen können. Im allgemeinen Fall kann man aber nicht berechnen, ob immer neue Zustände entstehen oder durch Wiederholung der Algorithmus in eine Schleife eintritt oder ob er anhält.
“es existiert keine algorith. Methode, mit der sich für eine beliebige, endliche Sequenz von Bits entscheiden liesse, ob diese zufällig ist oder nicht.”
Keine Bifolge ist zufällig! – sagt der Determinist, der sich dieser Wissenslücke gerne bedient.
“jedes solche Programm [muss] irgendwann an der beim allgemeinen Problem unbegrenzten algorith. Komplexität scheitern.”
Nicht zuletzt auch deswegen, sollten wir den Komplexitätsforschern dankbar sein, dass sie Orakel-Turingmaschinen erfunden haben. Die sind ja wohl wirklich hilfreich, das ein oder andere Problem doch noch lösen zu können.
Aber vielleicht führt das alles zu weit weg von den Triebkräften der Digitalisierung, also: Halt (!?)
@Joker
Chaitins Komplexitäts- und Turings Halteproblem sind äquivalent, siehe etwa
Burgin, M. (2007). Algorithmic complexity as a criterion of unsolvability. Theoret. Comput. Sci., 383(2), 244-259.
DOI: 10.1016/j.tcs.2007.04.011
Als Special Extra Service hier noch ein Link zu seinen Referenzen [2, 17].
»… sagt der Determinist, der sich dieser Wissenslücke gerne bedient.«
Der Determinismusstreit ist ganz bestimmt eine Endlosschleife, inszeniert von Philosophen mit nicht-digitalen Triebkräften. So, press ctrl-c to terminate.
@ Chrys
“Chaitins Komplexitäts- und Turings Halteproblem sind äquivalent”
Ja und?
Burgin verwendet ein Orakel, um das Halteproblem für einzelne Turingmaschinen zu entscheiden. Und Chaitin sagt, man könne auf das Orakel verzichten, wenn man eine Zeitschranke berechnen könnte, von der man weiß, dass die Turingmaschine nicht mehr halten wird, sobald die Berechnungszeit diese Schranke überschritten hat. Das kann man aber nicht.
@Joker
»Das kann man aber nicht.«
Chaitin kann das. Genauer, für ein gegebenes Programm P kann er das. P hat eine konstante Grösse in Bits, und alles, was P bei seiner Ausführung insgesamt tut, lässt sich als eine Abfolge von Bits darstellen, was sukzessive einen Binärstring von zwangsläufig nach oben beschränkter algorith. Komplexität liefert. Daraus lässt sich eine obere Schranke für die Anzahl von Operationen gewinnen, bis zu deren Erreichen P alle algorith. Information, die es überhaupt jemals liefert, bereits geliefert haben muss. Jenseits dieser Schranke, falls sie bei der Ausführung von P überschritten werden sollte, kann P unmögich noch weitere algorith. Information hinzufügen, sodass insbesondere P entweder vor Erreichen der Schranke oder nie terminiert.
Wäre das jetzt nicht ein Grund, Deine das Halteproblem betreffenden Überzeugungen nochmals einer AIT-Prüfung zu unterziehen?
@ Chrys
Wie sage ich kleines Licht es meinem Lehrer?
“Chaitin kann das.”
Nein, auch er kann das nicht. In seinem Beweis ist eine kontrafaktische Annahme, “if one could compute program-size complexity”; “Assuming that H is computable”. So kann er die Äquivalenz der Problemstellungen nachweisen: Wenn das eine geht, dann geht das andere auch zu lösen.
Tatsächlich kann aber niemand sagen, wie komplex die Ausgabe eines Programms ist, bzw. “alles, was P bei seiner Ausführung insgesamt tut “.
“was sukzessive einen Binärstring von zwangsläufig nach oben beschränkter algorith. Komplexität liefert”
Eben nicht zwangsläufig, sondern nur unter der gemachten Annahme.
Ich senke meinen Blick, kann zur Zeit aber keinen Schlauch erkennen, auf dem ich eventuell stehen könnte.
@Chrys:
“Daraus lässt sich eine obere Schranke für die Anzahl von Operationen gewinnen, bis zu deren Erreichen P alle algorith. Information, die es überhaupt jemals liefert, bereits geliefert haben muss. Jenseits dieser Schranke, falls sie bei der Ausführung von P überschritten werden sollte, kann P unmögich noch weitere algorith. Information hinzufügen, sodass insbesondere P entweder vor Erreichen der Schranke oder nie terminiert.”
Wäre das nicht gleichbedeutend damit, daß z.B. für die Goldbachsche Vermutung eine Obergrenze angegeben werden kann, bis zu der ein Gegenbeispiel gefunden sein muß, oder es gibt keines? Und damit wäre das Goldbachproblem gelöst, denn man muß nur bis zu dieser Obergrenze alles checken.
@Joker
Die Frage nach Berechenbarkeit ist dabei auch wieder die nach einer Berechnungsmethode für alle Programme, anderes hat er da gar nicht in der Peilung. Jedoch hängt Chaitins Beweis, dass eine solche Methode zur Berechnung algorith. Komplexität nicht existiert, wesentlich daran, dass ein Programm fixer Grösse keine nach oben unbeschränkte algorith. Komplexität liefern kann, und das muss er abschätzen können. Beim gegebenen Programm P sei nun die Schranke so gewählt, dass ein Terminieren von P jenseits der Schranke einen Binärstring von grösserer algorith. Komplexität erfordern würde, als durch die Ausführung von P produziert worden sein kann.
»Tatsächlich kann aber niemand sagen, wie komplex die Ausgabe eines Programms ist, bzw. “alles, was P bei seiner Ausführung insgesamt tut “.«
Wenn dem so wäre, dann stünde das in Konflikt mit dem Beweis von Chaitins Theorem. Und damit kann man nicht so recht glücklich sein.
—
@Christoph Deblon
In Grunde hätte man es da mit einer ganzen Schar von (Unter-)Programmen zu tun, jeweils bestehend aus einem eigentlichen Programmteil und einer geraden Zahl als Argument, wobei die binäre Länge des Arguments hier zur Programmgrösse hinzuzählt. Für jedes individuelle Argument hätte man so zwar eine feste Programmgrösse, aber für die ganze Schar liesse sich keine uniforme Begrenzung nach oben a priori vornehmen. Das hilft einem also auch nicht weiter.
@Joker
Mir scheint, eine gewisse Klarstellung wäre da noch angebracht. Die Existenz einer Schranke der besagten Art erfordert keine Annahmen über deren Berechenbarkeit, und das ergibt sich auch nicht etwa umgekehrt als Schlussfolgerung. Insofern stimmt es natürlich, dass auch Chaitin die nicht berechnen kann. Doch das muss er auch nicht.
Der Sinn der Sache besteht einzig in der Einsicht, dass aus der AIT Perspektive Turings Halteproblem einfach algorith. zu komplex ist, um durch ein Programm entscheidbar zu sein. Und die Unentscheidbarkeit impliziert daher nicht, dass es da ein konkretes Joker-Programm mit einem derart unmöglichen Halte-Verhalten geben müsse, dass sich nachweislich jeder Algorithmus daran die Zähne ausbeissen wird. Im allgemeinen weiss man eben nur, dass kein Königsweg existiert, um das im konkreten Einzelfall zu beurteilen.
@ Chrys
Ah ja, da war ja doch ein Schlauch, auf dem ich stand. Er war schon so platt, habe ihn ständig mit dem Boden verwechselt.
“Gibt es für jedes (M,I) einen Algorithmus, mit dem sich entscheiden lässt, ob (M,I) anhält oder nicht? Die Antwort darauf wäre eindeutig ja, für jedes (M,I) existiert so etwas.” (@Chrys, 7. August 2014 10:13)
Klar, eindeutig. Danke, für dein hartnäckiges Behaupten des Richtigen. Man sieht, nicht nur die Komplexität einer Turingmaschine ist beschränkt.
(Meine Denkfehler zu erläutern, ist vermutlich weder hilf- noch lehrreich, stattdessen werde ich einfach die Löschung meiner diesbezüglichen Kommentare aus den Ergebnislisten entsprechender Google-Suchanfragen beantragen.)
@Christoph Deblon, Joker
Was ich da (15. August 2014 23:46) zu einem Goldbach-Vermutungsprogramm angemerkt habe, ist dummes Zeug. Damit behaupte ich ja praktisch, dass sich mit einer schlichten Zählschleife beliebig viel Komplexität erreichen liesse und widerspreche platt dem, was gerade davor noch geschrieben hatte.
Ein solches Programm der Grösse 1068 Bits ist hier beschrieben [The Complexity of Goldbach’s Conjecture and Riemann’s Hypothesis]. Die bestmögliche Strategie (wenn man das noch so nennen kann), um damit etwas anzufangen, bestünde letztlich aber auch nur darin, irgendwie an die ersten 1068 Bits von Chaitins Haltewahrscheinlichkeit Ω zu kommen. Wie Chaitin selbst schreibt:
Entsprechendes lässt sich dann auch zur Goldbachschen Vermutung sagen.
Sind Konzepte wie die Turingmaschine (die alles berechnen kann was ein Computer je berechnen können wird), sind Algorithmen und ihre Macht (was können sie berechnen, was nicht?) relevant für die Bewertung des Computers, für seine sozialen Auswirkungen und seine Bedeutung für unsere Gesellschaft?
Zuerst ist es nicht offensichtlich, dass das so ist. Erst wenn man sich bewusst wird, dass auch das, was im Kern das biologische Leben ausmacht, mit dem Konzept der Turing-Maschine beschrieben wird, erkennt man die Bedeutung des Algorithmen-Konzepts.
Es ist nun nicht so, dass es nur für Computer – trotz all ihrer Macht – Beschränkungen geben würde, beispielsweise in der Form, dass es kein allgemeines Programm gibt, welches sagen kann ob ein anderes Programm irgendwann hält oder nicht. Nein, diese Beschränkungen gelten genau so für das biologische Leben, welches ebenfalls nicht beliebig allgemeine Problemlösungen finden kann, weil es in wichtigen Bereichen keine allgemeine Lösung gibt. Das lässt sich zusammenfassen in: Ein Computer ist nicht mächtiger als ein Mensch und ein Mensch nicht mächtiger als ein Computer.
Als Menschen und damit als biologische Wesen wissen wir allerdings aus Erfahrung schon lange, dass die Bäume nicht in den Himmel wachsen können. Und dank Turing und anderen wissen wir nun auch, dass auch die von uns geschaffene Technologie keine Allmacht erreichen kann.
In einem Punkt ist das Potenzial der Computertechnologie allerdings grösser als das von biologischen Wesen: Unsere Ressourcen als Menschen sind biologisch festgelegt und das Resultat von Millionen von Jahren Evolution, sie lassen sich jedenfalls nicht von heute auf morgen ändern und sind auch nicht beliebig skalierbar. Ganz anders bei der Computertechnologie. Sollte es je eine Maschine geben, die die kognitiven Fähigkeiten eines Menschen erreicht, dann kann
1) diese Maschine beliebig kopiert werden
2) kann diese Maschine weiter skaliert werden, also mit mehr Speicher ausgerüstet und schneller gemacht werden.
Auch Maschinen haben zwar eine Art DNA und eine Geschichte ähnlich unserer Evolutionsgeschichte, nur dass der Takt mit der die Technologiegenerationen sich ablösen in Einheiten von Monaten und Jahren gerechnet wird, der biologische und evolutionäre Takt aber in Generationen.
Henning Lobin: “Automatisierung, Datenintegration und Vernetzung – das sind die Triebkräfte der Digitalisierung. Sie wurden zwar jeweils mit dem zeitlichen Abstand von etwa 25 Jahren wirksam, heute sind sie jedoch in jedem Computer, in jedem Smartphone, Laptop oder Tablet gleichzeitig vorhanden.” Zustimmen kann man dabei, dass in jeden Computer die Automatisierung und Datenintegration eingebaut ist, nicht jedoch die Vernetzung. Diese braucht Übertragungswege und Zwischenstationen. Die Vernetzung ist ein über den einzelnen Computer, Smartphone, Laptop oder Tablet hinausgehender Bereich. Sie ist der Raum, das Universum, die Computer sind die Sterne darin. Selbstverständlich ist der Raum trotzdem eine Triebkraft der Digitalisierung.
Zustimmung: Gestern und heute morgen war die Vernetzung das sine qua non, also Pflicht, vorgestern gab es keine Vernetzung und morgen wird es auch Geräte geben, die bewusst nicht vernetzt sind.
Ergänzung: Dick Cheney hat seinen Schrittmacher vom Netz genommen.
Ok, ein Rechner kann auch nicht vernetzt sein und manchmal ist das auch sinnvoll. Trotzdem gehört die Vernetzung zu den Triebkräften der Digitalisierung in dem Sinne, dass wesentliche Veränderungen bestimmter Kommunikationspraktiken dadurch angeschoben werden.
Die Digitalisierung hat für mich schon mit der Erfindung des Alphabets begonnen, denn die Reduktion der vielen Sprachlaute auf einige wenige Zeichen ist eigentlich ein typischer Digitalisierungsschritt. Digitalisierung bedeutet immer auch Diskretisierung, ein Schritt der ein Kontinuum oder Beinahe-Kontinuum auf ein kleine Menge von Symbolen abbildet.
So gesehen sind feste Begriffe und ein Vokabular von häufig verwendeten Worten ebenfalls Symbole, die einem Abstraktions- und Filterprozess entspringen. Von einer eigentlichen Digitalisierung möchte ich aber erst bei der Reduktion auf ein sehr kleines Set sprechen – wie es eben ein Alphabet ist.
Dieser frühe Digitalisierungsschrritt, weg von den Hieroglyphen (Piktogrammen) und Wortsymbolen (Logogrammen), hin zu ener abstrakten, reduzierten Lautnotierung war ungemein erfolgreich. Es war wahrscheinlich eine der grössten Innovationen in der Menschheitsgeschichte überhaupt. Alphabete gibt es erst seit 1400 vor Christus und kurz nach ihrer Erfindung breiteten sie sich richtiggehend viral aus. In vielen Weltgegenden – wohl auch in Kreta und später Griechenland – begann das Schreiben und Lesen überhaupt erst mit der Übernahme und der Anpassung des ugaritischen und phönizischen Uralphabet.
Digitalisierung ist für mich also nicht gleichbedeutend mit Computerisiserung. Bis zu einem gewissen Grad ist symbolisches Denken – also, das was den Menschen vom Tier unterscheidet -, bereits mit einer Diskretisierung verbunden. Die Reduktion auf nur noch wenige Symbole wie sie bei der Erfindung des Alphabets geschah, ist für mich bereits eine Digitalisierung.
Die “Digitalisierung” (als Nicht-Fachterminus) gab es schon mit der Findung der Sprache und des Erkennens; auch eine Katze erkennt, ob sie es mit einer oder mit mehren Mäusen zu tun hat.
Es scheint insgesamt aber um den Fachterminus gegangen zu sein.
Genau das hab ich im Kommentar geschrieben: (Zitat) Die “Digitalisierung” (als Nicht-Fachterminus) gab es schon mit der Findung der Sprache und des Erkennens;, habe es aber als Diskretisierung bezeichnet und den Begriff Digitalisierung eingeschränkt auf die Codierung mit einer kleinen Symbolmenge.
Wie steht es mit (Zitat)” Es scheint insgesamt aber um den Fachterminus gegangen zu sein.”. In der Wikipedia liest man dazu:
Das digitale Speichermedium für Texte, die ein Alphabet verwenden, ist das Papier oder was man auch immer zur Niederschrift verwendet. Der gesamte Vorgang von der Erfassung und Aufbereitung bis zur Speicherung von analogen Informationen .. wäre im Falle der Niederschrift von mündlichen Äusserungen das Übersetzen der oft recht gutturalen Laute in eine schriftliche Äusserung, die dem Gesagten inhaltlich entspricht, wobei man dialektgefärbte Wendungen in die Standardsprache übersetzt. Und schon ist das Digitalisat erstellt.
Was Sie meinen, Herr Holzherr, ist die Kodierung von Sachen oder Sachverhalten zu Sprache oder Schrift, Datenträger meinend, auch akustische, und die anschließende Dekodierung, für einige auch: Abstraktion, zu Inhalt oder Nachricht, Sachen oder Sachverhalte betreffend, wobei eine sozial kommunizierte Regelmenge, von einigen (vereinfachend) Sprache oder Kultur genannt, bereit stehen muss, damit dbzgl, geleistet werden kann.
Nicht so toll fand Ihr Kommentatorenfreund diesen Einschub – ‘Bis zu einem gewissen Grad ist symbolisches Denken – also, das was den Menschen vom Tier unterscheidet -, bereits mit einer Diskretisierung verbunden.’ – also zur ‘Diskretisierung’ vielleicht noch: Sie ist ein Fachwort, die Trennung meinend, und stammt von ‘cernere’, wobei man beim Erkennen und der Unterscheidung wäre.
Digitalisierung meint die “Fingerung” und als Fachwort die zeitgenössischen IT-Systematik.
MFG
Dr. W (der hier aber keinen besonderen Dissens sieht)
Jein. Es geht mir darum, dass im Alphabet mit seinen 20+ Buchstaben eine sehr nützliche und menschheitsgeschichtlich revolutionäre Art der Digitalisierung gesprochener Sprache vorliegt. Diese Digitalisierung setzt eine kognitive (oder elektronische) Verarbeitung gesprochener Sprache voraus, die erst nach einem Lernprozess, einer Schulung zur Verfügung seht.
Noch einmal: Mit Digitalisierung meine ich die Diskretisierung mittels einer ganz kleinen Symbolmenge. Das Alphabet mit seinen 20+ Buchstaben ist sehr klein. Und das Alphabet ist eine ganz erstaunliche Erfindung:
1) Es ist erstaunlich, dass es so lange dauerte bis ein Alphabet erfunden wurde
2) Es ist erstaunlich, wie schnell sich diese Erfindung anschliessend verbreitete
Im übrigen staune ich etwas über ihr Beharren auf der wörtlichen zeitgenössischen Bedeutung des Begriffs Digitalisierung.
Mir ist bewusst, dass ich hier etwas ausschere mit meiner Interpretation. Ausscheren gehört aber zum kreativen Prozess und war hier mit einem Zwinkern gemeint, ist also mit einer Prise Humor zu nehmen.
Turing hat bereits die Selbstbezüglichkeit und Rekursivität von Computerprogrammen und das Konzept der funktionellen Äquivalenz in seine frühesten Überlegungen und Beispiele aufgenommen. Dies sollte sich als äusserst hellsichtig erweisen, denn damit – mit Selbstbezüglichkeit, Rekursivität und funktioneller Äquivalenz – beschäftigen sich Informatiker noch heute und zwar nicht nur fachwissenschaftlich, sondern auch philosophisch. Das Buch Gödel, Escher, Bach von Douglas R. Hofstadter hat genau das zum Thema, wobei er damit auch das Phänomen der menschlichen Intelligenz und der menschlichen Bewusstsein angehen will.
Turings Beweis, dass es kein Computerprogramm geben kann, das bestimmt, ob ein beliebiges Computerprogramm jemals hält (terminiert), ist nämlich nicht nur vom Ergebnis her interessant (Unentscheidbarkeit sogar in der Mathematik), sondern gerade auch deshalb, weil es Selbstreferenzialität einführt: Ein Programm, das andere Programme untersucht, könnten sogar sich selbst untersuchen. Das erinnert an den Menschen, an das bewusste Geschöpf, das darüber nachdenkt, was er gerade denkt. Auch die erst heute in 08/15-Programmiersprachen vorgedrungenen Funktionen höherer Ordnung ( Funktionen, die Funktionen als Argumente erhalten oder Funktionen als Ergebnis liefern) gibt es bei Turing bereits.
Die funktionelle Äquivalenz hat Turing mit der Erfindung der Turingmaschine zum Thema gemacht. Die Turingmaschinen ist ein maximal reduzierter Computer (reduced to the Max), der aber von seiner Leistungsfähigkeit her, definiert als Fähigkeit das Resultat von Funktionen zu bestimmen (zu berechnen), gleich mächtig ist wie jeder andere Computer. Heute spielen Äquivalenzklassen in vielen Gebieten der Informatik eine wichtige Rolle. So spricht man von der Komplexität von Berechnungsproblemen und meint damit den Rechen- und Speicheraufwand um ein Problem in Abhängigkeit von der Grösse des Problems zu lösen. Bei sogenannten Nichtdeterministischen-Polynominalen Problemen (NP-Problemen) ist kein Algorithmus bekannt, der ein Problem der Grösse n (z.B. n -Städte die mit dem kürzesten Weg hintereinander besucht werden müssen) mit dem Aufwand n^k (n hoch k) löst, wobei hier angenommen wird das die Maschine nicht parallel arbeitet, Arbeitsschritte also hintereinander ausgeführt werden. Diese Klasse der NP-Probleme kann aber mit polynomialen Aufwand gelöst werden, wenn man Parallelität zulässt, wenn also die Maschine beliebig viel Ausführungspfade gleichzeitg verfolgen kann. Wie weiss man nun, dass ein Problem ein NP-Problem ist? Dazu hat man für einige wenige praktische Beispiele gezeigt, dass für sie der Berechungsaufwand polynomial auf einer nichtdeterministischen, also einer parallelen Maschine ist. Für die meisten anderen Probleme hat man gezeigt, dass sie vom Aufwand her äquivalent sind zu einem der bekannterweisen NP-harten Probleme.
Selbstbezüglichkeit, Rekursivität und funktionale Äquivalenz sind uns aus dem menschlichen Denken, der menschlichen Kognition und auch der menschlichen Sprache bestens bekannt, man denke nur an den eingeschachtelten Satzteil, der die gleiche Struktur hat wie der Hauptsatz. In der Informatik, bei Computerprogrammen und im Zusammenhang der Digitalisierung gibt es Selbstbezüglichkeit, Rekursivität und funktinale Äquivalenz ebenfalls und zwar nicht nur als Zutat sondern als essentielles Element.