halteproblem
-
Jester schrieb:
Stichwort: Church'sche These: http://de.wikipedia.org/wiki/These_von_Church
Die Churchsche These macht eine Aussage zur Berechenbarkeit - hier geht es aber um Entscheidbarkeit. Zwei Paar Schuhe. Denn die Berechenbarkeit ist ja gerade eine Voraussetzung der Frage (ein Computerprogramm ist wegen der Churchschen These immer berechenbar). Die Frage ist jetzt, ob es auch entscheidbar ist - und zwar für Menschen.
Die Chruchsche These hilft da nicht weiter.@TGGC:
Hatte den selben Gedanken: K.O. durch Time-Out.
Als Nicht-Mathematiker hätte ich es aber einfacher gesagt: man nehme einfach ein Programm für dessen Code der Mensch Lebenszeit + 1 Sekunde benötigt um ihn zu lesen. Einfacher geht's nicht
(Das mit der Endlosschleife kannst dir sparen. Ob das Programm jetzt wirklich terminiert oder nicht, tut ja nichts zur Sache ob der Mensch es entscheiden kann oder nicht)
-
minhen schrieb:
Die Churchsche These macht eine Aussage zur Berechenbarkeit - hier geht es aber um Entscheidbarkeit. Zwei Paar Schuhe.
Kannst Du das mal näher ausführen? Entscheidbarkeit ist doch mit Berechenbarkeit sehr eng verknüpft. Es geht ja auch nicht darum das Programm auszuführen, sondern herauszufinden, ob es terminiert.
Computerprogramm ist wegen der Churchschen These immer berechenbar). Die Frage ist jetzt, ob es auch entscheidbar ist - und zwar für Menschen.
Die Chruchsche These hilft da nicht weiter.Wenn das Problem entscheidbar ist, dann gibt es einen Algorithmus (der vom Menschen ausgeführt werden kann), der es entscheidet (das ist die Definition). Nach curchscher These kann das dann auch ein Rechner tun. Ich sehe nicht, wo da der Fehler liegt, bzw. warum church da nicht hilft.
Vielleicht kannst Du das alles mal ein bißchen genauer erläutern?
-
minhen schrieb:
Die Churchsche These macht eine Aussage zur Berechenbarkeit - hier geht es aber um Entscheidbarkeit. Zwei Paar Schuhe. Denn die Berechenbarkeit ist ja gerade eine Voraussetzung der Frage (ein Computerprogramm ist wegen der Churchschen These immer berechenbar). Die Frage ist jetzt, ob es auch entscheidbar ist - und zwar für Menschen.
Eine Menge (hier die Menge aller Paare von Programmen und Eingaben, die terminieren, aka Halteproblem) ist genau dann entscheidbar, wenn ihre charakteristische Funktion berechenbar ist.
-
minhen schrieb:
Jester schrieb:
Stichwort: Church'sche These: http://de.wikipedia.org/wiki/These_von_Church
Die Churchsche These macht eine Aussage zur Berechenbarkeit - hier geht es aber um Entscheidbarkeit. Zwei Paar Schuhe. Denn die Berechenbarkeit ist ja gerade eine Voraussetzung der Frage (ein Computerprogramm ist wegen der Churchschen These immer berechenbar). Die Frage ist jetzt, ob es auch entscheidbar ist - und zwar für Menschen.
Die Chruchsche These hilft da nicht weiter.@TGGC:
Hatte den selben Gedanken: K.O. durch Time-Out.
Als Nicht-Mathematiker hätte ich es aber einfacher gesagt: man nehme einfach ein Programm für dessen Code der Mensch Lebenszeit + 1 Sekunde benötigt um ihn zu lesen. Einfacher geht's nicht
(Das mit der Endlosschleife kannst dir sparen. Ob das Programm jetzt wirklich terminiert oder nicht, tut ja nichts zur Sache ob der Mensch es entscheiden kann oder nicht)Was passiert wenn ein Lamer wie ich komme der einfach mal die letzte Seite aufschlägt und spickt?
-
-
hi,
TGGC schrieb:
clk madlf ap o.xfyk6ti ph schrieb:
TGGC schrieb:
Ja!
Begründung!
- Ein Mensch braucht die Zeit t um eine Seite Quellcode zu lesen mit t > 0
- Erzeuge ein Programm mit n Seiten Quellcode ohne Endlosschleife, wobei t n * t = 200
- Erweitere das Programm um eine Seite mit einer Endlosschleife
- Ein Mensch kann in seinem Leben nicht alle Seiten des Quellcodes lesen (s. 1 u. 2)
- Hat er die Seite mit der Endlosschleife nicht gelesen kann er nicht entscheiden, ob das Programm terminiert.
Gruß, TGGC (\-/ returns)
unser hypothetischer mensch hat eine beliebige lebenszeit.
interessant wäre auch, ob man nicht in einem überdefinierten anstatt in einem unvolständigen system logik betreiben sollte. ok, einige sachen wären dann falsch, aber man könnte auch viel mehr beweisen
bye.
-
Hallo
Das Halteproblem ist von großer theoretischer Bedeutung, stellt sich aber
in der Praxis nicht.Denn in der realen Welt gibt es keine Turing-Maschinen.
Beweis: Der Quantentheorie zufolge besteht das Universum aus endlich vielen
diskreten Teilchen, also kann jeder Computer, egal wie beschaffen er ist,
immer nur eine endliche Zustandsmenge besitzen. Also ist jeder Computer
der realen Welt ein endlicher Automat. Für endliche Automaten ist das Halteproblem
aber entscheidbar (per Umrechnung in einen regulären Ausdruck). Q.E.D.Sorry, wenn jetzt jemand enttäuscht ist.
Grüße
-
..,- schrieb:
hi,
existiert das halteproblem auch für den menschlichen verstand?
bye.
Trotz der vielen Trollposts ist das ein sehr ernstes Thema in den kognitiven Wissenschaften. Genauer zu verstehen, wann ein Mensch seine Analyse abbricht, eine Entscheidung trifft, wie Enscheidungen trifft und wann handelt.
Das Zusammenspiel zwischen Psyche, Persönlichkeit, Biologie, Physik, Chemie und logischen Prozessen bestimmt, warum einige Menschen aus der Analyse nicht rechtzeitig ausbrechen können und ihre Ergebnisse zeitig in der wirklichen Welt reflektieren können, um Erfolg zu haben. Warum andere Menschen recht impulsiv und spontan sind. Warum wieder andere Menschen extrem unvernünftig sind. Wann Menschen sehr abstrakt denken, genau berechnend sind, inspirativ denken oder träumen. Wann Sie pingelig genau oder recht oberfächlich sind.
Bis heute gehören Modelle dieser Art zu den größten Herausforderungen in der Informatik!
-
Das sind doch gar keine wohldefinierten Aufgaben.
-
Hallo
ob das Halteproblem auf den menschlichen Geist anwendbar ist oder nicht,
hängt davon ab, ob man das Gehirn für eine rein immanente chemo-elektrische
Maschine hält oder nicht.
In diesem Falle gilt dasselbe wie in meinem vorigen Posting:
Modulo der Richtigkeit des quantenmechanischen Weltbildes wäre ein Gehirn
als endlicher Automat modellierbar, und für endliche Automaten ist das
Halteproblem trivial entscheidbar.Glaubt man dagegen, daß das Gehirn nicht rein-immanent ist, also transzendent,
wird die Antwort schwieriger.
Das hängt dann eng mit der Frage zusammen, ob es einen freien Willen gibt
oder nicht, und dies ist wiederum der Frage ähnlich, ob die Welt deterministisch
ist oder nicht. Damit wären wir wieder bei der Quantenmechanik, die eine
gewisse Art von Nichtdeterminismus nahelegt, aber Weiteres würde den Rahmen
eines C++ Forums sicher sprengen.Grüße
-
Jester schrieb:
Wenn das Problem entscheidbar ist, dann gibt es einen Algorithmus (der vom Menschen ausgeführt werden kann), der es entscheidet (das ist die Definition). Nach curchscher These kann das dann auch ein Rechner tun. Ich sehe nicht, wo da der Fehler liegt, bzw. warum church da nicht hilft.
Vielleicht kannst Du das alles mal ein bißchen genauer erläutern?
Na ganz einfach, du vertauschst die Voraussetzungen mit dem Gesuchten. Du kannst nicht einfach aufgrund der Berechenbarkeit auch Entscheidbarkeit annehmen. Und das ist eben der Punkt. Gefragt ist nach der Entscheidbarkeit bei gegebener Berechenbarkeit.
Bei Rechnern selbst ist die Frage langweilig. Vom Halteproblem weiß man ja, dass es nicht entscheidbar ist. Deswegen die ziemlich esoterische Fragestellung ob es Menschen entscheiden können.
Das lässt sich zwar über die charakteristische Funktion auf Berechenbarkeit zurückführen, aber damit lässt sich auch nur die eine Seite zeigen: nämlich dass es Menschen (sofern die Lebenszeit ausreicht ;)) entscheiden können, wenn es entscheidbar ist. Aber was ist, wenn es für Turing-Maschinen unentscheidbar ist im Falle vom Menschen?
Das ist die Frage. Und die Frage lässt sich eigentlich auch so umformulieren, ob die Churchsche These wirklich zutrifft. Und bei Infragestellen der Churchschen These ist es eben eine merkwürdige Antwort, wenn du "siehe Churchsche These" sagst. Deswegen hilft sie dir nicht weiter
-
Hobbyprogrammierer schrieb:
Beweis: Der Quantentheorie zufolge besteht das Universum aus endlich vielen
diskreten Teilchen, also kann jeder Computer, egal wie beschaffen er ist,
immer nur eine endliche Zustandsmenge besitzen. Also ist jeder Computer
der realen Welt ein endlicher Automat. Für endliche Automaten ist das Halteproblem
aber entscheidbar (per Umrechnung in einen regulären Ausdruck). Q.E.D.Sorry, wenn jetzt jemand enttäuscht ist.
Ok, ich bin genau so wenig Mathematiker wie Physiker, aber eines weiß ich noch: die Quantentheorie sagt mit absoluter Sicherheit nicht, dass das Universum aus disrketen Teilchen besteht. Sie sagt eigentlich das exakte Gegenteil davon aus. Sagt dir Welle-Teilchen-Dualismus etwas? Quanten werden eigentlich über ihre Wellenfunktion beschrieben. Und weil du gerade so schön auf Computer anspielst, lies dich mal zu Quantencomputer etwas ein. Ein Qubit kann die Zustände 0 und 1 haben ... sowie sämtliche Superpositionen dieser Zustände. Heisenberg lässt grüßen.
-
minhen schrieb:
Na ganz einfach, du vertauschst die Voraussetzungen mit dem Gesuchten. Du kannst nicht einfach aufgrund der Berechenbarkeit auch Entscheidbarkeit annehmen. Und das ist eben der Punkt. Gefragt ist nach der Entscheidbarkeit bei gegebener Berechenbarkeit.
Bei Rechnern selbst ist die Frage langweilig. Vom Halteproblem weiß man ja, dass es nicht entscheidbar ist. Deswegen die ziemlich esoterische Fragestellung ob es Menschen entscheiden können.Ich glaube, Du wirfst da ziemlich vieles durcheinander. Entscheidbarkeit ist durch Berechenbarkeit einer bestimmten Funktion, nämlich der charakteristischen Funktion definiert.
Vielleicht nochmal kurz die Argumentation: Wenn Menschen es entscheiden können, dann ist es intuitiv berechenbar. Nach Church könnte es dann auch eine Turinmaschine tun. Also wäre es entscheidbar. Widerspruch. Daß es sich dabei um Programme handelt und diese ausführbar (also berechenbar) sind ist völlig unerheblich. Bloß weil da nur berechenbare Sachen drin wird die Menge nicht einfach so entscheidbar.
edit:
Church schrieb:
Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen.
Wichtig ist das *genau*.
-
Jester schrieb:
Ich glaube, Du wirfst da ziemlich vieles durcheinander.
Und ich glaube, du liest nicht richtig
Alles was du mir gerade "erklärt" hast, hab ich im Beitrag vorher selbst gesagt.
Jester schrieb:
Entscheidbarkeit ist durch Berechenbarkeit einer bestimmten Funktion, nämlich der charakteristischen Funktion definiert.
minhen schrieb:
Das lässt sich zwar über die charakteristische Funktion auf Berechenbarkeit zurückführen
Jester schrieb:
Bloß weil da nur berechenbare Sachen drin wird die Menge nicht einfach so entscheidbar.
minhen schrieb:
Du kannst nicht einfach aufgrund der Berechenbarkeit auch Entscheidbarkeit annehmen.
Vielleicht nochmal kurz die Argumentation: Wenn Menschen es entscheiden können, dann ist es intuitiv berechenbar.
Vielleicht noch ein weiteres Mal: die Frage ist, ob es berechenbar ist, wenn Menschen es entscheiden können:
minhen schrieb:
du vertauschst die Voraussetzungen mit dem Gesuchten. (...) die Frage lässt sich eigentlich auch so umformulieren, ob die Churchsche These wirklich zutrifft. Und bei Infragestellen der Churchschen These ist es eben eine merkwürdige Antwort, wenn du "siehe Churchsche These" sagst.
Vielleicht sollte ich den Punkt genauer sagen. Mir geht es nicht darum ob intuitive Berechenbarkeit, GOTO-, WHILE-, und Turing-Berechenbarkeit äquivalent sind, sondern um die andere Aussage, welche da wäre, dass die durch diese Klasse erfassten Funktion genau alle berechenbaren sind. D.h., dass damit exakt der Berechenbarkeitsbegriff erfasst ist. Das lässt sich nicht beweisen und die Fragestellung hier ist nun eben, ob Menschen (in der Fragestellung ja notgedrungen eine Black Box) eine umfassendere Berechenbarkeitsmöglichkeit haben oder nicht.
-
minhen schrieb:
Vielleicht sollte ich den Punkt genauer sagen. Mir geht es nicht darum ob intuitive Berechenbarkeit, GOTO-, WHILE-, und Turing-Berechenbarkeit äquivalent sind, sondern um die andere Aussage, welche da wäre, dass die durch diese Klasse erfassten Funktion genau alle berechenbaren sind. D.h., dass damit exakt der Berechenbarkeitsbegriff erfasst ist.
Dann sind wir doch einer Meinung. Unter Voraussetzung der church'schen These läßt sich die ursprüngliche Frage eindeutig mit "Ja" beantworten. Mehr habe ich die ganze Zeit auch garnicht behauptet (und dabei auch nix durcheinandergeworfen ;)).
Daß man diese These nicht beweisen kann war sowieso klar. Damit ist der Zusammenhang mit dem Thema dann wohl hinreichend geklärt und ich kann in Urlaub fahren.
-
Hallo
Ich bleibe bei allen Feststellungen in meinem Posting,
Du darfst aber gerne anderer Meinung sein.Grüße
-
Jester schrieb:
Dann sind wir doch einer Meinung.
Ja, jetzt da ich dir explizit erklärt habe, auf welche Teilaussage der Chruchschen These ich mich genau beziehe, schon.
Und was das Durcheinanderwerfen angeht möchte ich einfach noch mal auf den vorigen Beitrag hinweisen.Viel Spaß im Urlaub.
Hobbyprogrammierer schrieb:
Ich bleibe bei allen Feststellungen in meinem Posting,
Du darfst aber gerne anderer Meinung sein.Die Frage ist nicht welcher Meinung ich bin, sondern welcher Meinung die Quantenphysik ist auf die du dich berufst
-
Hallo
Die Frage ist nicht welcher Meinung ich bin, sondern welcher Meinung die Quantenphysik ist auf die du dich berufst<<
Wie Du meinst
Nein, im Ernst: Genügt Einsteins Nobelpreis-gekrönte Quantenhypothese W=h*f als Referenz ?
Grüße
PS. nicht ärgern. Ich habe kein Problem damit, wenn Leute anderer Meinung sind
als ich. Aber für häßliche Streitereien ist mir meine Zeit zu kostbar, das gilt auch für Internet-Diskussionen.PS 2. Man kann nicht nur die Rechenkraft eines Computers berechnen, wenn das
ganze Universum als ein einziger Computer verwendet würde, man kann auch berechnen, wo in unserem Universum die absolute Grenze der praktischen Berechenbarkeit liegt und wie schnell ein Computer in unserem Universum
maximal sein könnte.PS 3. Die Frage, ob die Quantentheorie oder die allgemeiner Relativität
die Welt richtig darstellen (oder keine von beiden), werden wir hier vermutlich
in einem Programmierpsrachen-Forum nicht klären. Das überlassen wir besser
Hawking, den Stringtheoretikern und anderen.Grüße
-
Hobbyprogrammierer schrieb:
Genügt Einsteins Nobelpreis-gekrönte Quantenhypothese W=h*f als Referenz ?
Da wirfst du was durcheinander. Einsteins Formel für den photoelektrischen Effekt, die du wohl meinst, würde nach W umgestellt W = h*f - m/2*vmax² lauten. Aber das ist nicht das Problem. Die Frage ist viel eher, für was willst du das als Referenz verwenden?
-
Hallo
Nein, ich werfe nichts durcheinander.
Das Einstein-Postulat lautet "Licht der Frequenz f besteht aus Quanten
der Energie W=h*f".Licht ist aber nicht das einzige im Universum, das gequantelt vorkommt.
Die Quantengravitations-Theorie postuliert eine "körnige" Struktur des Raumes, und die "Loop-Theorie" diskretisiert die Zeit, was aber in
diesem Zusammenhang keine Rolle spielt. Wie auch die Stringtheorien sind
dies Versuche, Quantentheorie und Relativitätstheorie zu einer gemeinsamen
Theorie zu verbinden.Würde man jedes Einzelteil des gequantelten Universums (seien es nun Energie-Quanten oder eine "körnige" Raumstruktur) als Speicherzelle verwenden,
so hätte man einen maximal großen Computer, der dennoch keine Turingmaschine darstellt, da
eine Turingmaschine einen unendlichen Speicher benötigt.Wie bereits betont, behaupte ich dies lediglich im Rahmen dieser quantentheoretischen Weltbilder, deren Übereinstimmung mit der Wirklichkeit
ich nicht nachprüfen kann und ebensowenig wie alle anderen weiß, wie das
Universum wirklich beschaffen ist, aber das ist ja auch nicht Gegenstand
der Diskussion.Ich denke, jetzt ist die Behauptung aber klar geworden.
Grüße
