Halteproblem
Diese Seite wurde seit 1 Jahr inhaltlich nicht mehr aktualisiert.
Unter Umständen ist sie nicht mehr aktuell.
Definitionen
Es gibt keine Turing- Maschine, die entscheiden kann, ob eine beliebige andere Turing-Maschine je anhält oder nicht.
Von Raimond Reichert, Jürg Nievergelt, Werner Hartmann im Buch Programmieren mit Kara (2003) im Text TuringKara auf Seite 73As Alan Turing proved in 1936, a computer program can never tell you for sure whether another program might end up calculating forever without end—except by simulating the operation of that program and thus potentially going off the deep end itself.
Von Brian Christian, Tom Griffiths im Buch Algorithms to Live By (2016) Als Eingabe wird das Halteproblem "gefüttert" mit dem Text eines zulässigen Programms A in unserer ausgewählten Programmiersprache Spr und einer möglichen Eingabe X (die nichts anderes als eine Folge von Symbolen ist). Das Problem fragt danach, ob A anhalten würde, wenn wir es mit der Eingabe X laufen liessen.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite 50Bemerkungen
Der erbrachte Beweis dafür, daß das Halteproblem ein mathematisch formulierbares Problem ist, das sich maschinell nicht lösen läßt, hat ungemein tiefgreifende Bedeutung für das wissenschaftliche Selbstverständnis der Mathematik.
Von Peter Gold im Buch Der Mensch in der Perspektive der Kognitionswissenschaften (1998) im Text Philosophische Aspekte künstlicher Intelligenz auf Seite 69Das Halteproblem kann, wie auch das anspruchsvollere Verifikationsproblem, nicht auf algorithmischem Wege gelöst werden: Es ist unentscheidbar. Es gibt also keine allgemeine Möglichkeit, in endlicher Zeit zu bestimmen, ob die Ausführung eines bestimmten Programmes mit einer bestimmten Eingabe anhalten wird oder nicht.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite 51Die allgemeine Lösung dieses Problems mit Hilfe eines Aigorithmus, wenn es einen solchen Algorithmus gäbe, hätte enorme praktische Relevanz für die zuverlässige Programmierung von Computern. Die definitive Einsicht, daß es eine algorithmische Lösung indessen nicht gibt, hat gravierende theoretische Konsequenzen für die prinzipiellen Leistungsgrenzen von Programmen.
Von Peter Gold im Buch Der Mensch in der Perspektive der Kognitionswissenschaften (1998) im Text Philosophische Aspekte künstlicher Intelligenz auf Seite 69Man ist versucht, das Problem durch einen Simulationsalgorithmus lösen zu wollen, der einfach das mit der Eingabe X laufende Programm A nachahmt und schaut, was passiert. Wenn das simulierte A anhält. Dann können wir selbst begründetermaf3en anhalten und schliessen, da die Antwort "ja" ist. Die Schwierigkeit liegt darin wann wir mit dem Warten aufhören sollen, um " nein" zu sagen, Wir können nicht einfach nach einer langen Zeitspanne aufgeben und beschliessen, da die Simulation nie anhalten wird, weil sie es bislang nicht getan hat. Vielleicht müssten wir sie nur ein klein bisschen weiter laufen lassen. vielleicht sogar nur eine Mikrosekunde. Und sie würde anhalten. Daher ist es nicht ausreichend, das Verhalten des gegebenen Programmes mit der gegebenen Eingabe zu simulieren.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite 52Verwandte Objeke
Verwandte Begriffe (co-word occurance) | Turing-Maschineturing machine(0.06), Lambda-Kalkül(0.05), Church-Turing-These(0.05), Gödelsches Theorem(0.04), BerechenbarkeitComputability(0.04) |
Relevante Personen
Häufig erwähnende Personen
Häufig co-zitierte Personen
Statistisches Begriffsnetz
Einträge in Beats Blog
Zitationsgraph
Zeitleiste
42 Erwähnungen
- Menschliche Kommunikation - Formen, Störungen, Paradoxien (Paul Watzlawick, Janet H. Beavin, Don D. Jackson) (1967)
- Formal languages and their relation to automata (John E. Hopcroft, Jeffrey D. Ullman) (1969)
- Die Macht der Computer und die Ohnmacht der Vernunft (Joseph Weizenbaum) (1976)
- Münchhausens Zopf - oder: Psychoanalyse und 'Wirklichkeit' (Paul Watzlawick) (1988)
- Berechnungstheorie für Informatiker (Erwin Engeler, Peter Läuchli) (1988)
- Computerdenken - Die Debatte um künstliche Intelligenz, Bewusstsein und die Gesetze der Physik (Roger Penrose) (1989)
- Zukunftsperspektiven der Informatik für Schule und Ausbildung - GI-Fachtagung, München, 15.-17. November 1989, Proceedings (Franz Stetter, Wilfried Brauer) (1989)
- Einführung in die Technische und Theoretische Informatik im Unterricht (Hermann Stimm) (1989)
- Computer in der Schule 3 - Materialien für den Mathematik- und Informatikunterricht (Klaus-Dieter Graf) (1990)
- Shadows of the mind - A search for the missing science of conciousness (Roger Penrose) (1994)
- Der Mensch in der Perspektive der Kognitionswissenschaften (Andreas Engel, Peter Gold) (1998)
- Philosophische Aspekte künstlicher Intelligenz (Peter Gold)
- Der Computer als didaktisches Medium - Über die Mythen des Mediums und das Lernen von Subjekten (Rupert Röder) (1998)
- Der Wissensnavigator - Das Lexikon der Zukunft (Artur P. Schmidt) (1999)
- Didaktik der Informatik - Grundlagen, Konzepte und Beispiele (Peter Hubwieser) (2000)
- Das Affenpuzzle - und weitere bad news aus der Computerwelt (David Harel) (2000)
- The New Turing Omnibus (A. K. Dewdney) (2001)
- Theoretische Informatik - Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie (Juraj Hromkovic) (2001)
- Computerlogik (Daniel Hillis) (2001)
- Pragmatischer Konstruktivismus und fundamentale Ideen als Leitlinien der Curriculumentwicklung - am Beispiel der theoretischen und technischen Informatik (Eckart Modrow) (2002)
- A New Kind of Science (Stephen Wolfram) (2002)
- Programmieren mit Kara - Ein spielerischer Zugang zur Informatik (Raimond Reichert, Jürg Nievergelt, Werner Hartmann) (2003)
- 5. TuringKara - Zweidimenisonale Turing-Maschinen
- Complex Adaptive Systems - An Introduction to Computational Models of Social Life (John H. Miller, Scott E. Page) (2007)
- INFOS 2007 - Didaktik der Informatik in Theorie und Praxis - 12. GI-Fachtagung Informatik und Schule (Sigrid E. Schubert) (2007)
- Mathematical and Algorithmic Foundations of the Internet (Fabrizio Luccio) (2011)
- Informatik in Bildung und Beruf - INFOS 2011 - 14. GI-Fachtagung Informatik und Schule (Marco Thomas) (2011)
- Ein genetischer Zugang zum Programmieren mit CGI-Skripten in Python (Jan Schuster) (2011)
- Mehr als 0 und 1 - Schule in einer digitalisierten Welt (Beat Döbeli Honegger) (2016)
- 6. Wozu Informatik? (2016)
- Algorithms to Live By - The Computer Science of Human Decisions (Brian Christian, Tom Griffiths) (2016)
- Didaktik der Informatik (Eckart Modrow, Kerstin Strecker) (2016)
- Die Schlangenöl-Branche (Klappentext) (2016)
- Dem Computer ins Hirn geschaut - Informatik entdecken, verstehen und querdenken (Eckart Zitzler) (2017)
- Wo Maschinen irren können - Verantwortlichkeiten und Fehlerquellen in Prozessen algorithmischer Entscheidungsfindung (Katharina A. Zweig, Sarah Fischer, Konrad Lischka) (2018)
- Computational Thinking (Peter Denning, Matti Tedre) (2019)
- 1. What is computational Thinking?
- 2. Computational Methods
- Ansturm der Algorithmen - Die Verwechslung von Urteilskraft mit Berechenbarkeit (Wolf Zimmer) (2019)
- 13. Das Atrium des Computers
- Informatik für alle - 18. GI-Fachtagung Informatik und Schule (Arno Pasternak) (2019)
- Informatikunterricht - Ein Muss zur politischen Mündigkeit (Niko Hausner, Katharina Wendlandt, Matthias Wendlandt)
- Ein Algorithmus hat kein Taktgefühl - Wo künstliche Intelligenz sich irrt, warum uns das betrifft und was wir dagegen tun können (Katharina A. Zweig) (2019)
- Human Compatible - Künstliche Intelligenz und wie der Mensch die Kontrolle über superintelligente Maschinen behält (Stuart Russell) (2020)
- Informatik - Bildung von Lehrkräften in allen Phasen - 19. GI-Fachtagung Informatik und Schule (Ludger Humbert) (2021)
- Informatik fürs Leben lernen (Till Tantau)
Anderswo finden
Externe Links
Das Halteproblem: oder warum Gott keine Maschine sein kann ( : Link unterbrochen? Letzte Überprüfung: 2020-11-28 Letzte erfolgreiche Überprüfung: 2011-03-28) |