halteproblem

nein. Das ist gerade der Vorteil des Menschen gegenüber dem dummen Computer. Der Mensch kann eben mehr als nur Logik

geist schrieb:

Der Mensch kann eben mehr als nur Logik

Sowas wie rechts blinken und rechts abbiegen? :p

hi,

TGGC schrieb:

Definiere das Halteproblem für den menschlichen Verstand. f'`8k

ich kann es nur schwer definieren, da ich ja noch nichtmal weiß, ob es existiert. aber ich versuche mal, mich heranzutasten:

existiert ein (turing-äquivalentes) computerprogramm, zu dem ein mensch - beliebige, aber endliche lebenszeit bei voller gesundheit und hilfsmittel in form von papier und schreibgerät vorausgesetzt - nicht entscheiden kann, ob es seine ausführung terminiert.

TGGC

..,- schrieb:

existiert ein (turing-äquivalentes) computerprogramm, zu dem ein mensch - beliebige, aber endliche lebenszeit bei voller gesundheit und hilfsmittel in form von papier und schreibgerät vorausgesetzt - nicht entscheiden kann, ob es seine ausführung terminiert.

Ja! f'`8k

Gruß, TGGC (\-/ returns)

TGGC schrieb:

Ja!

Begründung!

Jester

Stichwort: Church'sche These: http://de.wikipedia.org/wiki/These_von_Church

Jester schrieb:

Stichwort: Church'sche These: http://de.wikipedia.org/wiki/These_von_Church

das ist eine these. eine nicht bewiesene nocht dazu.

Jester

,xkym g,vka pokwsm,.lvfm schrieb:

das ist eine these.

Das hast Du richtig erkannt. Die These "5 = 5" ist auch eine These.

eine nicht bewiesene nocht dazu.

Schlimmer noch, es ist sogar eine nicht beweisbare These. Dennoch ist es ein wichtiges Stichwort, das zu diesem Thema gehört.

Letztlich ist es also ne Glaubensfrage.

TGGC

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)

minhen

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)

Jester

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?

Bashar

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?

TGGC

Da steht nicht, das man die Seite am Ende anhängen soll. f'`8k

Autocogito

Gruß, TGGC (\-/ returns)

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

Prof84

..,- 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

minhen

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