Diskussion:Halteproblem

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Halteproblem“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Diese Diskussionsseite wurde aufgeräumt.
Einträge ohne direkten Diskussionsbezug oder nicht unterschriebene Einträge wurden ohne Archivierung entfernt, Verbleibendes ins Archiv verschoben, sofern die Diskussion als abgeschlossen erachtet wurde. Bitte nicht wieder zurückverschieben, sondern das Thema neu starten. Die Archivierung erfolgt von Zeit zu Zeit, um die Übersicht wiederherzustellen.

Dies betrifft nur Abschnitte bis zum 12. Nov 2006. Sie sind hier auffindbar: Diskussion:Halteproblem.
--AwOc 17:53, 10. Dez. 2008 (CET)

Zum Archiv

Automatische Archivierung

Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit 3 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind.

Beispiel

Ich bitte Benutzer:Mussklprozz den Revert [1] zu begründen. --Headbreak (Diskussion) 19:10, 11. Mär. 2012 (CET)

Wie bei früheren Versuchen Deinerseits: Das Beispiel erhellt nicht den Sachverhalt. Gruß, --Mussklprozz (Diskussion) 19:54, 11. Mär. 2012 (CET)

3M: Ich grüße euch beide.

1. Den Streit um das Beispiel kann ich als Aussenstehender nicht nachvollziehen, da es einem Aussenstehenden nicht möglich ist zu verstehen, worum es im Artikel überhaupt geht (insofern ist das strittige Beispiel auch egal). Dies ist ein typisches Lemma für Fachleute, aber (leider) nicht für Laien (für die wir aber eigentlich in Wikipedia schreiben).
2. Dieser Artikel hatte ein ähnliches Problem mit der Laienverständlichkeit - schaut euch dazueinfach die Versionsgeschichte an. Falls ihr beide an einer grundsätzlichen Überarbeitung des Lemma "Halteproblem" interessiert seit, kann ich gerne helfen (ich werde mich aber nicht aufdrängen).

BG --Friedrich Graf (Diskussion) 21:16, 11. Mär. 2012 (CET)

„Lemma“ ist übrigens nur der Titel. Der ganze Text mit Lemma nennt sich Artikel. --Headbreak (Diskussion) 21:43, 11. Mär. 2012 (CET)

Okay - das ist auch eine Antwort. Ich habe jetzt also verstanden, das du Recht hast. Kein Problem. Aber wozu hast du dich eigentlich auf der 3M gemeldet? --Friedrich Graf (Diskussion) 22:04, 11. Mär. 2012 (CET)

Guten Abend Friedrich,

Danke für Deinen Beitrag und Dein Angebot. Artikel über ein mathematisches Fachthema haben es leider an sich, dass sie teilweise nur für Leute mit Vorwissen verständlich sind. Dass die Beweisidee nicht für alle nachvollziehbar ist, liegt in der Natur der Sache. Der Einleitungsabschnitt und der Abschnitt Konsequenzen sollten aber. Sie sind es nicht? Dann bin ich Dir in der Tat dankbar, wenn Du mir betriebsblindem Informatiker einen Hinweise gibst, an welcher Stelle das Verständnis aussetzt, so dass wir gemeinsam den Text verbessern können. :-) Gruß aus Freiberg am Neckar, --Mussklprozz (Diskussion) 22:52, 11. Mär. 2012 (CET)

Ich grüße euch. Gerne kann ich die beschriebene Arbeit beginnen, würde nur gerne - zumindest mit Duldung, besser mit Zustimmung - von Headbreak arbeiten. Denn nichts ist schlimmer als kontraproduktive Arbeit (weil gegeneinander). Leider war die letzte Reaktion von Headbreak doch sehr mißverständlich. FG --Friedrich Graf (Diskussion) 08:56, 12. Mär. 2012 (CET)

Hm, ich hatte so meine Probleme mit den bisherigen Beiträgen von Headbreak. Es war m.E. entweder spekulativ und persönlich, zu weit über das mathematisch-fachliche hinausführend, oder es handelte sich um Codebeispiele, die auf mich und andere unvollständig und kryptisch wirkten. Andere Fachleute sind der gleichen Ansicht; siehe Versionsgeschichte. Es tut mir ja Leid, dass Headbreak hier immer wieder aufläuft und frustriert ist, aber ...--Mussklprozz (Diskussion) 09:49, 12. Mär. 2012 (CET)

• ... mit Frust, persönlichen Angriffen oder anderen Dingen habe ich null Probleme. Das einigste, was ich vermeiden will, ist Unproduktivität. Diese entsteht nach meiner Erfahrung nur, wenn einer der "Mitspieler" ausschliesslich auf seiner Meinung beharrt - und das funktioniert bei Wikipedia nie. Da ich Headbreak nicht kenne und deine Schilderung eben auch nur DEINE Schildung ist, wollte ich eine Reaktion von Ihm haben. Also nochmal deutlich: mir geht es um keinerlei Befindlichkeiten oder andere Dinge. Diese sind mir egal.
• Zu meiner Arbeitsweise. Sollte es zu einer Zusammenarbeit kommen, würde ich folgende Verfahrensweise vorschlagen:

1. Ich arbeite in Etappen. Die Etappen sind meist stundenweise - ich werde diese eindeutig ansagen.
2. Ich arbeite original im Lemma. Diese Arbeitsweise hat einen Vorteil: mit der Versions-Funktion kann jeder von euch kontrollieren, das ich keine Fakten lösche. Da ich meist sehr viel Text bewege, hat sich dieses Detail als hilfreich erwiesen.
3. Am Anfang der Etappen stehen immer einige Fragen von mir, bei der ich eure Hilfe benötige. Am Ende der Etappen könnt ihr immer gnadenlos kritisieren.
4. Prinzipiell greife ich in die Metastruktur des Lemmas, in den Satzbau und die Redundanzen ein. Dabei ändere ich natürlich die Inhalte, Verlinkungen usw. Ich werde äußerst genau darauf achten, keine reinen Fakten zu löschen (daher auch die Arbeitsweise mit der Versionsgeschichte).

BG --Friedrich Graf (Diskussion) 10:42, 12. Mär. 2012 (CET)

Danke für Dein Angebot. Meinetwegen, go ahead. Eine Bitte: lasse den Beweis so stehen, wie er ist. Das ist eine Sache für Mathematiker oder Informatiker. Gruß, --Mussklprozz (Diskussion) 10:56, 12. Mär. 2012 (CET)

meiner meinung nach sollte der ganze artikel, inklusive beweis, auch fuer nichtinformatiker verstaendlich sein. die beweisidee ist nicht sonderlich kompliziert und wenn du eine moeglichkeit siehst, den beweis verstaendlicher zu machen, wuerde mich das freuen. natuerlich sollte die beweisidee, wie sie im verlinkten artikel beschrieben ist, erhalten bleiben. --Mario d 11:46, 12. Mär. 2012 (CET)

Zustimmung. Danke für Deinen Zusatz von eben; damit sollte eigentlich verständlich sein, wie der Beweis läuft. Wo siehst Du noch einen Punkt, wo das Verständnis aus dem Ruder laufen könnte, etwas redliche Mühe des Lesers voraussetzend? --Mussklprozz (Diskussion) 12:06, 12. Mär. 2012 (CET)

das weiss ich nicht, ich hoffe, dass uns Friedrich Graf dabei helfen kann. --Mario d 12:50, 12. Mär. 2012 (CET)

Zur Zeit gibt es eine Konfliktmeldung im Vermittlungsausschuss. Um dieses Konfliktthema sauber vom Lemmathema zu trennen, warte ich erst die Reaktion von Headbreak ab. Was deine Frage betrifft: ja, ich bin zuversichtlich. BG --Friedrich Graf (Diskussion) 12:54, 12. Mär. 2012 (CET)

Zur Info: Wikipedia:Vermittlungsausschuss/Problem_zwischen_Headbreak_und_Mussklprozz. Mario, Du bist dort auch als Konfliktbeteiligter benannt. --Mussklprozz (Diskussion) 14:50, 12. Mär. 2012 (CET)

interessant, davon wusste ich noch gar nichts. meinetwegen koennen wir die arbeit am artikel ruhen lassen, waehrend der VA laeuft. --Mario d 16:25, 12. Mär. 2012 (CET)

... ob das nötig ist, hängt von Headbreaks Reaktion ab. --Friedrich Graf (Diskussion) 16:31, 12. Mär. 2012 (CET)

Ich stimme dem zu die Arbeit am Artikel erstmal ruhen zu lassen bis die Diskussion geklärt ist. --Headbreak (Diskussion) 23:09, 12. Mär. 2012 (CET)

Mal ganz ernsthaft, Headbreak: Was soll denn das? Ich lese mich gerade in den Konflikt ein, nur um nach 5 Minuten festzustellen, dass du einen (!) Tag nach Meldung bei der DM schon in den VA gegangen bist. Ich sehe hier absolut noch keine Notwendigkeit, in den VA zu gehen, weil es noch genug inhaltliche Fragen zu diskutieren gibt. Ich stimme Friedrich Graf zu: Die fehlende Laienverständlichkeit der Einleitung und der grundsätzlichen Beschreibung ist sowieso KO-Kriterium, vorher brauchen wir uns nicht über ein Beispiel unterhalten. Lasst uns bitte zusammen konstruktiv am Artikel arbeiten und auf den VA zunächst verzichten.--Jan Rieke (Diskussion) 17:54, 12. Mär. 2012 (CET)

Das Problem zieht sich aber schon länger hin. --Headbreak (Diskussion) 23:10, 12. Mär. 2012 (CET)

Zum Erklärung des Inhalts des Artikels:

Auch wenn für viele Algorithmen die Frage, ob sie irgendwann terminieren, leicht beantwortet werden kann, gibt es also keinen Algorithmus, der diese Frage für alle möglichen Algorithmen und beliebigen Eingaben beantwortet. Dies bedeutet, dass es Berechnungsvorschriften gibt, bei denen rein prinzipiell die Frage, ob sie irgendwann terminieren, nicht beantwortet werden kann. Dafür ist es bei diesen Berechnungsvorschriften nicht nur nicht möglich zu prüfen, ob sie jemals terminieren werden, es ist bei allen diesen Berechnungsvorschrift auch nicht möglich sie fehlerfrei auszuführen. --Headbreak (Diskussion) 23:22, 12. Mär. 2012 (CET)

Das Halteproblem besteht aus der Frage, ob es eine Berechnungsvorschrift gibt, welche für alle Berechnungsvorschriften mit allen Eingaben entscheiden kann, ob diese terminieren werden. Dieses ist nicht-entscheidbar. Daher gibt es auch kein Programm und, auch gemäß der Church-Turing-These, keinen Menschen, welches bzw. welcher dieses Problem entscheiden könnte.

Im folgenden Beispiel ist rein prinzipiell nicht möglich festzustellen, ob das Programm halten wird oder nicht. Ein solcher Fall kann nur mit Hilfe eines Quines auftreten. Die Funktion auf_terminierung_pruefen stellt eine Implementierung der Halteproblementscheidung dar. Sie gibt entweder true oder false zurück. In diesem Fall wird auf_terminierung_pruefen eine Ausnahmesituation hervorrufen.

function a() {
	if ( auf_terminierung_pruefen ( a.toSource() ) )
	{
		while(true) {}
	}
};
a();

Auf Deutsch übersetzt:

(Serielle Abarbeitung der Befehle=Nacheinander)

Anleitung „Auf Terminierung prüfen“:

• prüft, ob eine Anleitung im Laufen im Kreis endet oder die Anleitung beendet wird, sodass mit etwas anderem fortgefahren werden kann

Anleitung 1:

1. Befolge die Anleitungen zum Thema „Auf Terminierung prüfen“ für Anleitung 1. Eine Eingabe ist für Anleitung 1 nicht nötig.
2. Falls die Antwort „Ja.“ zurückgegeben wird, was bedeuten würde, dass diese Anleitung nicht im endlosen Laufen im Kreis enden wird, laufe endlos im Kreis rum.
3. Ansonsten beende das Befolgen dieser Anleitung.

--Headbreak (Diskussion) 23:32, 12. Mär. 2012 (CET)

Hallo Headbreak, danke für deine Reaktion, danke für deine Zuarbeit. Da ich jetzt gerade einen vollen Terminkalender habe, werde ich nur moderat starten können. In jedem Fall werde ich mich heute nochmal melden. BG --Friedrich Graf (Diskussion) 08:03, 13. Mär. 2012 (CET)

Guten Morgen allerseits.

Headbreaks Aussage: „Dafür ist es bei diesen Berechnungsvorschriften nicht nur nicht möglich zu prüfen, ob sie jemals terminieren werden, es ist bei allen diesen Berechnungsvorschrift auch nicht möglich sie fehlerfrei auszuführen“ ist sachlich falsch. Eine (deterministische) Turingmaschine folgt einer festen Berechnungsvorschrift, die immer in der gleichen Weise Weise durchgeführt wird. Die zusätzlichen Kategorien fehlerhaft und fehlerfrei gehören nicht zum Problem und stiften daher nur Verwirrung.

Die Codeskizze stellt keine „Implementierung der Halteproblementscheidung“ dar. Sie ist lückenhaft. Eine korrekte Darstellung in Java müsste die Maschinen H, G, F und T aus dem Beispiel darstellen, beispielsweise in Form einer Funktion oder Klasse. Der Code wäre nur für jemanden verständlich, der sich schon mit Programmierung beschäftigt hat; somit nicht laien-verständlicher als das Beispiel selbst.

Der Zusatztext zum Code führt zusätzliche Begriffe ein, die ihrerseits nicht unmittellbar verständlich sind: „Ein solcher Fall kann nur mit Hilfe eines Quines auftreten.“ Damit leistet der Zusatztext nicht, was eine gute Erläuterung leisten sollte: Unbekanntes auf Bekanntes zurückzuführen.

Es sollte nur solche Redundanz in den Artikel eingeführt werden, die unmittelbar das Verständnis fördert. Ein gutes Beispiel in diesem Sinne scheint mir diese Hinzufügung von Mario zu sein.

@Headbreak, es tut mir Leid, dass Dir das Ganze persönlich nahe geht. Mir liegt nichts daran, Dich zu kränken, und ich will auch nicht „gezielt verhindern (...), dass der Benutzer den Artikelinhalt verstehen kann.“ ;-) Unnötige Zusatzbegriffe blähen jedoch den Text auf, erschweren dem Leser den Zugang zum Kerngedanken.

--Mussklprozz (Diskussion) 08:48, 13. Mär. 2012 (CET)

Das Halteproblem ist von grundlegender Bedeutung: Aus seiner Unlösbarkeit folgt, dass es 1) unmöglich ist, generell zu verhindern, dass sich Computerprogramme in einer Endlosschleife verfangen, und dass es 2) wohldefinierte mathematische Funktionen gibt, die sich nicht berechnen lassen. Diese Konsequenzen bereits in der Einleitung kurz und prägnant in den Vordergrund zu stellen, wäre vielleicht ein Ansatz, den Einstieg laienfreundlicher zu gestalten.

Gruß aus Freiberg am Neckar, --Mussklprozz (Diskussion) 09:03, 13. Mär. 2012 (CET)

ich moechte ein paar der von Headbreak getroffenen aussagen aufgreifen.

• "Daher gibt es auch kein Programm und, auch gemäß der Church-Turing-These, keinen Menschen, welches bzw. welcher dieses Problem entscheiden könnte."

die Church-Turing-These spricht von algorithmischer entscheidbarkeit, ob ein mensch etwas entscheiden kann wird davon nicht beruehrt.

• "Im folgenden Beispiel ist rein prinzipiell nicht möglich festzustellen, ob das Programm halten wird oder nicht. Ein solcher Fall kann nur mit Hilfe eines Quines auftreten."

aus dem artikel: "Ein Quine ist ein Computerprogramm, das eine Kopie seiner selbst (üblicherweise seines Quelltextes) als Ausgabe schreibt." ich sehe nicht, wo das hier geschieht. ich finde es auch nicht hilfreich, neue begriffe einzufuehren, die fuer das verstaendnis des halteproblems nicht notwendig sind. der letzte satz ist jedenfalls falsch, denn der beweis im artikel enthaelt keine quines.

• dein code gibt nicht die beweisidee wieder. a) ist die konstruktion im beweis black-box, d. h. G muss nur die schnittstellen von H kennen. die konstruktion in deinem code ist nicht black-box, denn die funktion a muss die beschreibung von H kennen um den quellcode auszugeben. b) beruht der beweis darauf, dass die konstruktion von F aus H einfach und offensichtlich machbar ist. das ist in deinem code nicht der fall, denn nicht jede TM kann ihre eigene beschreibung ausgeben. c) verstehe ich, genau wie Mussklprozz, nicht, warum du neue bezeichner fuer die maschinen einfuehrst, die im beweis auftauchen.

eine kurze beschreibung der maschinen aus dem beweis in pseudocode sieht bspw. so aus:

F(x):

if H(x,x) = 1 then while(true);

else exit;

ob das allerdings hilfreicher ist als das bild, weiss ich nicht.--Mario d 13:05, 13. Mär. 2012 (CET)

Fragen

Zur Vorbereitung des Artikelumbaus hier die ersten Fragen:

1. Woher kommt der Begriff "Halteproblem"? Ich frage weniger unter dem Gesichtspunkt der Quellenangabe, sondern mehr wegen des (Laien-) Verständnisses. Um das an einem Beispiel zu illustrieren: hält die Berechnung irgendwo an, weil die Rechenkapazität erschöpft ist (sicher nicht...)?
2. Warum ist bei der jetzigen Einleitung formuliert: "... zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift ... zu einem Ende gelangt.". Nicht "zum Ende" wird man auch beim ausrechen der Nachkommastellen von Pi gelangen. Und Pi wird auch nach einer bestimmten Berechnungvorschrift ermittelt ... nun ist natürlich etwas anderes gemeint, aber so wird es vom Laien verstanden. Was soll er also verstehen mit "... zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift ... zu einem Ende gelangt."?

Mehr Fragen später ... --Friedrich Graf (Diskussion) 13:09, 13. Mär. 2012 (CET)

1. eine Turingmaschine ist ein kleiner schreib-/lesekopf, der auf einem unendlich langen band umherflitzt, auf dem zeichen stehen. durch das lesen und schreiben von zeichen fuehrt er eine berechnung (algorithmus) aus, so wie ein computer ein programm ausfuehrt, indem er daten aus dem speicher liest und andere daten in den speicher schreibt. die berechnung ist vorbei (der algorithmus terminiert), wenn der schreib-/lesekopf anhaelt. die antwort (ausgabe) ist dann an einer vorher definierten stelle auf dem band zu finden. es kann aber auch vorkommen, dass der kopf nie anhaelt, weil er bspw. in einer endlosschleife steckt. das halteproblem fuer einen algorithmus fragt: haelt der kopf bei der ausfuehrung dieses algorithmus irgendwann an oder nicht? anders gefragt: wenn ich das programm laufen lasse, bekomme ich irgendwann eine antwort?
2. ich glaube, das ist genauso gemeint, wie der laie es versteht. wenn du einen computer bittest, dir alle nachkommastellen von Pi auszurechnen, wird er nie zu einem ende kommen. deshalb hoeren alle algorithmen, die Pi ausrechnen, bei einer bestimmten genauigkeit einfach auf. Pi komplett auszurechnen oder Pi mit einer bestimmten genauigkeit auszurechnen sind aber zwei verschiedene probleme. --Mario d 13:44, 13. Mär. 2012 (CET)

Moin Friedrich,

und hallo Mario, (Bearbeitungkonflikt)

zu 1: Laut der englischen Wikipedia wurde der Begriff Halting problem von Martin Davis in seinem Buch Computability and Unsolvability geprägt (McGraw-Hill, New York 1958, ISBN 978-0486614717). Turing selbst verwendet den Begriff in seiner Originalarbeit von 1937 nicht (On computable numbers, with an application to the Entscheidungsproblem, online hier). – Eine Turingmaschine ist ein abstraktes Modell einer Rechenmaschine. Ihre Kapazität kann sich nicht erschöpfen: Sie hat potenziell beliebig viel Zeit zur Verfügung und ein beliebig erweiterbares Band für ihre Daten. Sie hält genau dann an, wenn ihr Programm auf den Befehl HALT stößt.

zu 2: Du siehst das vollkommen richtig, beim Berechnen aller Nachkommastellen von Pi kommt die Maschine nicht zum Halt. Immerhin schafft sie es aber, Pi mit beliebig großer Genauigkeit zu berechnen. Man kann sich der Einfachheit halber aber auf ganzzahlige Funktionen beschränken. Schon bei diesen gibt es solche, bei denen die Turingmaschine nicht zum Halt kommt. Als Paradebeispiel wird immer die Radó-Funktion genannt, die leider etwas tricky ist. Ich weiß leider kein laienfreundlicheres Beispiel. Die Funktionen, die wir so aus dem Mathematikunterricht an der Schule kennen, sind alle mit beliebig hoher Genauigkeit turing-berechenbar.

Gruß, --Mussklprozz (Diskussion) 13:57, 13. Mär. 2012 (CET)

zur Antwort 1.) ... genau das sollte in der Einleitung angerissen werden.

zur Antwort 2.) ... letztlich lautet die Antwort: "es ist ein Problem der Genauigkeit" -bzw. der verwendeten Skale (umso genauer ich ein Ergebnis haben will, umsomehr entsteht überhaupt erst das Halteproblem). Ist dies der Inhalt, der dem Laien vermittelt werden soll? Oder entsteht das Halteproblem bei noch anderen Berechnungen (die gänzlich vom Beispiel "Pi" abweichen?

--Friedrich Graf (Diskussion) 14:04, 13. Mär. 2012 (CET)

bei manchen funktionen wissen wir wirklich nicht sicher, ob der algorithmus fuer jede eingabe haelt: Collatz-Problem.--Mario d 14:07, 13. Mär. 2012 (CET)

Zu 2): Nein, es ist kein Problem der Genauigkeit. Es kommt auch bei anderen Berechnungen zum Tragen (siehe oben: Radó-Funktion, möglicherweise beim Collatz-Problem). Gruß, --Mussklprozz (Diskussion) 14:18, 13. Mär. 2012 (CET)

das halteproblem ist kein problem, das bei einer berechnung entsteht. es ist die (ja/nein)-frage, ob eine berechnung terminiert oder nicht. diese frage laesst sich fuer jeden algorithmus stellen. --Mario d 15:17, 13. Mär. 2012 (CET)

Beschreibung der Rado-Funktion als nicht lösbares Problem: ... ist ein Problem, das nicht allgemein algorithmisch lösbar ist. ... Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich.

Ich habe weiter oben von der "Skale" gesprochen - ich denke, das es die Beschreibung besser trifft (als die Genauigkeit), da bei dem von euch genannten Beispielen um den Komplexitätsgrad der Rahmenbedingungen geht. Mir geht es bei meiner Frage nach passenden Beispielen aber nicht um Grundsatzdiskussionen. Ich versuche nur, das Halteproblem "herunterzubrechen". Also wäre der derzeitige Stand des Herunterbrechens:

• das Halteproblem tritt bei der Anwendung von Berechnungsvorschriften auf, wenn die zu berechnenden Elemente einen bestimmten Komplexitätsgrad überschreiten.
• Ab diesem Komplexitätsgrad kann der Punkt des anhaltens nicht mehr bestimmt werden

Liege ich damit richtig? --Friedrich Graf (Diskussion) 15:28, 13. Mär. 2012 (CET)

nein. mit skale hat das nichts zu tun.

• aus problem: "Ein Problem [...] nennt man eine Aufgabe oder Streitfrage, deren Lösung mit Schwierigkeiten verbunden ist" (fett von mir). das halteproblem ist kein problem, das bei einer berechnung auftritt. es ist das problem, zu entscheiden, ob eine berechnung terminiert oder nicht. diese frage laesst sich fuer jeden algorithmus stellen. das halteproblem fuer ein kochrezept ist: wird das essen in endlicher zeit fertig? die beantwortung des halteproblems ist fuer viele algorithmen sehr leicht.
• die frage ist, ob der algorithmus ueberhaupt haelt oder nicht, nicht, an welchem punkt er haelt und die schwierigkeit des halteproblems ist einem algorithmus inhaerent, haengt also nur indirekt mit der komplexitaet der ausgabe zusammen. --Mario d 15:47, 13. Mär. 2012 (CET)

Die eigentliche Ursache, warum der Beweis so kompliziert ist, ist nur zu verstehen, wenn man beispielsweise die Grundaussagen des Buches Schatten des Geistes kennt.

Die ganzen Lügen brauche ich ja gar nicht alle einzeln kommentieren. Der Mensch arbeitet natürlich gar nicht algorithmisch, sondern mit einem unvorstellbaren System, welches man nicht auf herkömmlichen Papier beschreiben kann. (Ironie) Auf keinen Fall soll auf die Begründung des Halteproblems näher eingegangen werden. Fachbegriffe wie Quine sollten besser verschwiegen werden, damit der Leser ja nicht selber nachdenkt. (Ironie) Das Beispiel ist natürlich nicht verständlicher als das Beispiel selbst. Dieser Satz versteht sich ja von selbst! (Ironie) Sowas wie „Blackbox“ ist nicht möglich. Genauso nicht wie ein „freier Wille“, der nicht von Naturgesetzen abhängt, nicht möglich ist.

F(x):
   if H(x,x) = 1 then while(true);
   else exit; 

Toll, da tu ich für X=F rein und schon ist es 1:1 mein Beispiel. Und natürlich würde dann H mit genau dem gleichen Eingabewerten aufgerufen werden, wie die Maschiene, die H aufruft.

Natürlich gibt es Programme, bei denen eine einfache Maschine zur Lösung des Halteproblems unendlich lang brauchen würde. Aber ob das dann auch genau wegen dem Beweis so wäre? In dem Beispiel kommt ja H gar nicht in eine Endlosschleife, sondern ist selber gar nicht möglich.

Es sollte vielleicht mal im Artikel definiert werden, was "entscheidbar" bedeutet, also eine „Ja.“- oder „Nein.“-Antwort.

Das mit dem Komplexitätsgrad stimmt schon. Programmiersprachen ab einer gewissen Komplexität ermöglichen einen Quine und auch Funktionsaufrufe und damit lässt sich leicht ein Programm schreiben, bei dem nicht geprüft werden kann, ob es jemals halten wird, welches aber gerade deshalb auch nicht ausführbar ist.

Das Halteproblem ist deshalb nicht lösbar, weil die Fragestellung rein logisch nicht funktioniert. Daher ist auch der Beweis rein logisch. Mit Programmen, die jahrelang laufen und bei denen man nicht weiß, ob sie jemals enden werden (z.B. Algorithmus zur Suche nach ungeraden volkommene Zahlen) hat das soviel zu tun, wie, dass die Frage

„Epimenides der Kreter sagte, dass alle Kreter immer das Gegenteil der Wahrheit sagen. Alle anderen Aussagen von Kretern außer diese sprachen sicher immer das Gegenteil der Wahrheit aus. Sprach Epimenides die Wahrheit oder das Gegenteil der Wahrheit aus?“

irgendetwas mit endlos laufenden Programmen zu tun hat. Wenn bei jemandem bei der Frage eine Endlosschleife auftritt, bei der er zweifelt, ob, dass nur eine wirklich langdauernde Berechnung sein könnte oder vielleicht doch eine Endlosschleife, dann ist die Logik-Komponente im Gehirn kaputt. --Headbreak (Diskussion) 17:14, 13. Mär. 2012 (CET)

Ich möchte euch erstmal allen für eure Antworten danken. Die erste Überarbeitungsetappe werde ich in den nächsten Stunden realisieren - allerdings werde ich es nicht schaffen, alles (von euren Antworten) zu berücksichtigen. Heute werde ich mich erstmal auf einige Sortierarbeiten und die Einleitung konzentrieren.
Um Bearbeitungskonflikte zu vermeiden, würde ich um Geduld bitten. Ich werde definitiv heute Abend Bescheid geben, das ich fertig bin - danach könnt ihr auch gnadenlos kritisieren, ergänzen, umschreiben, vorschlagen usw.
BG --Friedrich Graf (Diskussion) 16:30, 14. Mär. 2012 (CET)

FERTIG - mit der heutigen Etappe. Ich warte jetzt auf eure Kritik ... vermutlich werde ich morgen weitermachen. --Friedrich Graf (Diskussion) 18:03, 14. Mär. 2012 (CET)

Einleitung liest sich jetzt sehr gut. Glückwunsch, herzlichen Dank, und Gruß aus Freiberg am Neckar, --Mussklprozz (Diskussion) 20:31, 14. Mär. 2012 (CET)

ich finde die einleitung auch sehr gut gelungen, mir gefaellt nur der erste satz nicht. ich finde es schoen, einen ersten satz zu haben, der der artikel kurz zusammenfasst, wie bspw. in der englischen version des artikels. was meint ihr? --Mario d 22:53, 14. Mär. 2012 (CET)

Entscheidbarkeit

2 Fragen noch mit auf den Weg ...

1. Was ist der Unterschied zwischen "Entscheidbarkeit" und "Nicht-Entscheidbarkeit". Das eine ist ja nicht zwangsläufig das Gegenteil des anderen.
2. Wie erklärt man das einem Laien?

BG bis morgen ... --Friedrich Graf (Diskussion) 20:46, 14. Mär. 2012 (CET)

Etwas ist immer dann nicht-entscheidbar, wenn die Annahme, die Aussage wäre wahr, als auch die Annahme, die Aussage wäre falsch, zu einem Widerspruch führen würden. --Headbreak (Diskussion) 21:08, 14. Mär. 2012 (CET)

@Headbreak: Nein, das stimmt so nicht. Siehe Entscheidbar#Abgrenzung

@Friedrich: Eine Eigenschaft ist bezüglich einer Menge entscheidbar, wenn es einen Algorithmus gibt, der für jedes Element der Menge eine Ja-Nein-Aussage liefert, ob die Eigenschaft für das Element zutrifft oder nicht. Die Eigenschaft ist dann nicht entscheidbar, wenn es einen solchen Algorithmus nicht gibt. Das eine ist das Gegenteil des anderen. – Ich habe eine entsprechende Ergänzung in der Einleitung versucht; löst das die Frage? --Mussklprozz (Diskussion) 21:20, 14. Mär. 2012 (CET)

Dann nenn mal 1) ein Element der Menge, bei dem man die im Artikel diskutierte Eigenschaft nicht berechnen kann und 2) zeige, welche Teile dieses Elements als F und als G bezeichnet werden dürfen. --Headbreak (Diskussion) 21:27, 14. Mär. 2012 (CET)

Angenommen man hat eine Element der Menge der Programme, für die das Halteproblem (Eigenschaft) nicht entscheidbar ist. Man versucht es auszuführen und plötzlich stoppt es. Würde das dann die Annahme, dass das Halteproblem bei diesem Programm nicht entscheidbar ist, widerlegen oder nicht? Eine Antwort würde mich sehr freuen. --Headbreak (Diskussion) 21:46, 14. Mär. 2012 (CET)

der beweis sagt aus, dass es keinen algorithmus gibt, der das halteproblem in jedem fall entscheidet. er gibt keinen algorithmus an, fuer den das halteproblem unentscheidbar ist. das ist ein unterschied. da menschen keine turingmaschinen sind, sagt er auch nicht, aus, dass das halteproblem fuer menschen nicht entscheidbar ist. zur zweiten frage: wenn ein programm fuer jede eingabe haelt, ist das halteproblem fuer dieses programm entscheidbar. (diese aussage ist falsch, es gibt ja unendlich viele moegliche eingaben. entscheidbarkeit folgt nicht aus der tatsache, dass ein programm fuer eine bestimmte eingabe haelt oder nicht.--Mario d 09:01, 18. Mär. 2012 (CET)) --Mario d 22:58, 14. Mär. 2012 (CET)

Die mE. einzig sinnvolle Interpretation der definierenden Eigenschaft der Elemente deiner Menge ist: Sie tricksen jeden der Spezifikation gehorchenden Haltevorhersagealgorithmus aus. Dies trifft aber vakuös auf alle Programme zu (weil kein solcher Haltetest existiert - siehe Beweis im Artikel). Das spezielle Element ist also nur irgendein Programm, das hält. Das widerlegt nichts, außer vielleicht so uninteressante Behauptungen wie die, es gebe keine terminierenden Programme. --Daniel5Ko (Diskussion) 23:05, 14. Mär. 2012 (CET)

Was ist „vakuös“? --Headbreak (Diskussion) 19:40, 15. Mär. 2012 (CET)

Sorry, mir fiel auf die Schnelle nix besseres ein, als das englische "vacuous" einfach mal silbenweise zu übersetzen. Gemeint ist jedenfalls, dass $\forall x\in X.\varphi$ im Fall $X=\emptyset$ unabhängig von $\varphi$ immer wahr ist.--Daniel5Ko (Diskussion) 21:41, 15. Mär. 2012 (CET)

Danke für die Antworten, Ergänzungen und Beispiele. Ich werde vermutlich heute Abend weitermachen, sofern es mein Dienst erlaubt. Ich melde mich in jedem Fall nochmal. --Friedrich Graf (Diskussion) 11:56, 15. Mär. 2012 (CET)

Ich lege jetzt los! --Friedrich Graf (Diskussion) 18:39, 15. Mär. 2012 (CET)

Ähm, Friedrich, Du bist gerade im Begriff, auf einen Holzweg zu tappen ;-) ... Darf ich bitte mal kurz dazwischen? --Mussklprozz (Diskussion) 19:39, 15. Mär. 2012 (CET)

„wenn ein programm fuer jede eingabe haelt, ist das halteproblem fuer dieses programm entscheidbar.“ Also ein Programm, welches nur bei der Eingabe "1" hält, wäre daher nicht entscheidbar? Und wenn das Programm gar nicht hält, dann ist es also auch nicht entscheidbar? --Headbreak (Diskussion) 19:09, 15. Mär. 2012 (CET)

das folgt daraus nicht. ich habe "wenn" gesagt, nicht "genau dann, wenn". --Mario d 22:14, 15. Mär. 2012 (CET) (behauptung mittlerweile zurueckgezogen, s.o. --Mario d 09:01, 18. Mär. 2012 (CET))

Sorry, das ich nicht auf die Diskussionsseite geachtet habe ... ich hör jetzt sowieso erstmal auf. Das alte Kapitel "Konsequenzen" habe ich komplett stehenlassen (allerdings unsichtbar). Die Fakten, die ich aus diesem alten Kapitel noch nicht übernommen habe, werde ich bei der nächsten Arbeitsetappe (morgen) einbauen. So: jetzt dürft ihr wieder . BG --Friedrich Graf (Diskussion) 19:47, 15. Mär. 2012 (CET)

fragen

Fassen wir die Gedanken der anderen Diskussionteilnehmer mal zusammen:

• Es gibt Elemente aus der Menge der Turingmaschienen, für die die Eigenschaft, ob sie halten, nicht entscheidbar ist, weil es keinen Algorithmus gibt, der eine Ja oder Nein-Antwort dafür liefern würde.
• Wenn in unendlicher Zeit kein Ergebnis vorliegen kann, so ist die Eigenschaft unentscheidbar.
• Die im Beweis gezeigte Turinmaschiene ist nicht baubar.
• Die Turingmaschiene, die das Halteproblem für alle Programme lösen würde, würde immer halten.
• Das Algorithmus hält immer für eine bestimmte Eingabe oder nicht.
• Wenn eine Turingmaschiene, für die das Halteproblem nicht lösbar ist, anhält, so ist die Eigenschaft, ob sie terminiert, immernoch nicht-entscheidbar.
• Wenn eine Turingmaschiene, für die das Halteproblem nicht lösbar ist, in eine simple Endlosschleife gerät, so ist die Eigenschaft, ob sie terminiert, immernoch nicht-entscheidbar.
• In dem Beweis der Nichtentscheidbarkeit des Halteproblems ruft T sich nicht selber auf.
• Die Halteproblementscheidung besteht aus den Maschienen H, G, F und T.
• Aus dem Beweis lassen sich keine Turingmaschienen konstruieren, für die das Halteproblem nicht entscheidbar ist.
• Alle Turingmaschienen, für die das Halteproblem nicht lösbar ist, sind nicht aus dem Beweis heraus konstruiert.
• Turingmaschienen, für das Halteproblem nicht lösbar ist, verwenden einen speziellen Trick.
• Alle Turingmaschienen, für die das Halteproblem nicht entscheidbar ist, können nicht auf die Information zurückgreifen, ob sie jemals halten werden.
• Das Halteproblem ist mathematisch wohldefiniert.
• Die Aussage, dass die Halteeigenschaft bestimmter Turingmschienen nicht geprüft werden kann, kann aus dem Beweis nur auf Turingmaschienen angewendet werden, nicht aber auf Menschen.
• Daher gibt es Funktionen, die sich nicht berechnen lassen, für die also ein X-Wert keinem Y-Wert zugeordnet werden kann.
• Daher können (vakuär) generell alle Programme in eine Endlosschleife geraten ohne, dass man dies verhindern könnte.
• Daher können Programme auch keine Transferleistungen wie ein Gehirn vollbringen.

Kann man das so in den Artikel übernehmen?

--Headbreak (Diskussion) 19:40, 15. Mär. 2012 (CET)

nein, auf keinen fall. ich greife mal nur die raus, die falsch oder schlecht formuliert sind.

• Wenn in unendlicher Zeit kein Ergebnis vorliegen kann, so ist die Eigenschaft unentscheidbar.

wenn es keinen algorithmus gibt, der die eigenschaft entscheidet, so ist sie (algorithmisch) unentscheidbar.

• Wenn eine Turingmaschiene, für die das Halteproblem nicht lösbar ist, anhält, so ist die Eigenschaft, ob sie terminiert, immernoch nicht-entscheidbar.
• Wenn eine Turingmaschiene, für die das Halteproblem nicht lösbar ist, in eine simple Endlosschleife gerät, so ist die Eigenschaft, ob sie terminiert, immernoch nicht-entscheidbar.

das halteproblem ist nicht entscheidbar. es gibt klassen von TM fuer die das halteproblem entscheidbar ist, aber erstmal ist "Turingmaschine, für die das Halteproblem nicht entscheidbar ist" dasselbe wie "Turingmaschine". wenn du in der aussage "fuer alle eingaben anhaelt/in eine endlosschleife geraet" meinst, ist der satz falsch.

• Die Halteproblementscheidung besteht aus den Maschienen H, G, F und T.

was ist die "Halteproblementscheidung"?

• Turingmaschienen, für das Halteproblem nicht lösbar ist, verwenden einen speziellen Trick.
• Alle Turingmaschienen, für die das Halteproblem nicht entscheidbar ist, können nicht auf die Information zurückgreifen, ob sie jemals halten werden.

das halteproblem ist nicht entscheidbar. es gibt klassen von TM fuer die das halteproblem entscheidbar ist, aber erstmal ist "Turingmaschine, für die das Halteproblem nicht entscheidbar ist" dasselbe wie "Turingmaschine".

• Daher können (vakuär) generell alle Programme in eine Endlosschleife geraten ohne, dass man dies verhindern könnte.

wie soll das programm, das nur "Hallo Welt" ausgibt, in eine endlosschleife geraten?

• Daher können Programme auch keine Transferleistungen wie ein Gehirn vollbringen.

warum "daher"? --Mario d 22:33, 15. Mär. 2012 (CET)

Ich habe die einzelnen Zitate der anderen Diskussionsteilnehmer weggelassen.

„es gibt klassen von TM fuer die das halteproblem entscheidbar ist, aber erstmal ist "Turingmaschine, für die das Halteproblem nicht entscheidbar ist" dasselbe wie "Turingmaschine".“

Das wäre ein Widerspruch oder was soll "erstmal" bedeuten?

„was ist die "Halteproblementscheidung"?“

Das ist die Entscheidung, ob ein bestimmter Algorithmus mit einer bestimmten Eingabe hält oder nicht. Mussklprozz scheint jedoch den Begriff verstanden zu haben, da er den Begriff in seiner Antwort erwähnte und nicht weiter nach der Bedeutung fragte.

„wie soll das programm, das nur "Hallo Welt" ausgibt, in eine endlosschleife geraten?“

Daniel5Ko hat gesagt: „Sie tricksen jeden der Spezifikation gehorchenden Haltevorhersagealgorithmus aus. Dies trifft aber vakuös auf alle Programme zu (weil kein solcher Haltetest existiert - siehe Beweis im Artikel).“

Also ist das vermutlich falsch, was er gesagt hat.

• Daher können Programme auch keine Transferleistungen wie ein Gehirn vollbringen.

„warum "daher"?“

Ich zitiere den studierten Informatiker P.C. zum Thema Halteproblem: „Man spricht dann vom "lernen". Computer sind auch nicht Intuitiv. Sie können keine Transferleistung erbringen. Doch das ist nur ein Teil der Konsequenzen. “

Auf

„wenn ein programm fuer jede eingabe haelt, ist das halteproblem fuer dieses programm entscheidbar.“ Also ein Programm, welches nur bei der Eingabe "1" hält, wäre daher nicht entscheidbar? Und wenn das Programm gar nicht hält, dann ist es also auch nicht entscheidbar?

hat MarioS geantwortet:

das folgt daraus nicht. ich habe "wenn" gesagt, nicht "genau dann, wenn". --Mario d 22:14, 15. Mär. 2012 (CET)

Das müsste aber bedeuten, dass es neben entscheidbar und nicht-entscheidbar noch eine dritte Möglichkeit gibt. --Headbreak (Diskussion) 19:26, 16. Mär. 2012 (CET)

Die anderen ungeklärten Frage möchte ich aber auch gerne beantwortet haben, falls das möglich ist! Man kann sich doch nicht nur die Rosinen rauspicken. --Headbreak (Diskussion) 19:59, 16. Mär. 2012 (CET)

Hallo Headbreak! Ich habe mir deine Argumentationskette genau angesehen und glaube dich zu verstehen. Der gedankliche Überbau abstrakter Themen gleicht oft einer "Black Box". Dabei definiert man zuerst sämtliche Bereiche, die nicht relvant sind - und ignoriert sie anschliessend gnadenlos. Das ist im Falle abstrakter Systeme auch möglich, da man vorab bereits bewiesen hat, das diese Bereiche (die man ignoriert) nicht relevant sind. In deinem Beispiel ist es ebenso: "eine dritte Möglichkeit" ist nicht relevant für folgende Aussage: "ob die Ausführung eines Algorithmus zu einem Ende gelangt". Mit oder ohne dieser "dritten Möglichkeit" existiert das Halteproblem. So, ich hoffe dir geholfen zu haben ... BG --Friedrich Graf (Diskussion) 18:13, 17. Mär. 2012 (CET)

Nein, das ist ein Widerspruch! MarioS hat mir das Gegenteil gesagt, nämlich, dass es wichtig sei, dass diese dritte Menge existiere (indirekt über sein "wenn dann" statt "genau dann wenn") --Headbreak (Diskussion) 22:04, 17. Mär. 2012 (CET)

Sorry, da halte ich mich jetzt raus, denn ich will nicht die Aussage anderer Personen interpretieren. --Friedrich Graf (Diskussion) 22:38, 17. Mär. 2012 (CET)

die zugrundeliegende aussage habe ich zurueckgezogen; das aendert aber nichts daran, dass ich nie die existenz einer dritten menge behauptet habe. das ist eine voellig falsche interpretation deinerseits. eine TM haelt oder sie haelt nicht, ein drittes gibt es nicht. algorithmische entscheidbarkeit hat nichts damit zu tun, ob eine TM haelt, sondern damit, ob es moeglich ist, algorithmisch zu bestimmen, ob sie haelt. im uebrigen habe ich nicht den eindruck, dass diese diskussion zur verbesserung des artikels beitraegt. auch die meisten deiner oben von mir korrigierten falschen aussagen beruhen auf falschen interpretationen der diskussionsbeitraege anderer benutzer. deine position hat sich im wesentlichen nicht geaendert, wie an deiner einfuegung in den artikel zu erkennen ist. letztendlich fehlt dir einfach das fachwissen, um inhaltlich zum artikel beitragen zu koennen, du beharrst aber dennoch auf der richtigkeit deiner ansichten. das ist eine fatale kombination, die die WP sicherlich nicht weiterbringt. du hast keinen anspruch darauf, deine privaten ansichten in einem artikel unterzubringen. die diskussionsseite ist auch nicht dazu da, dir das zur mitarbeit noetige wissen beizubrungen. ich sehe daher keinen sinn darin, diese diskussion fortzusetzen. --Mario d 09:23, 18. Mär. 2012 (CET)

Die "dritte Möglichkeit" ist das, was auch zutrifft, nämlich dass das Halteproblem semi-entscheidbar ist. Es lässt sich bei jedem Algorithmus zeigen, dass er für eine Angabe anhält, nämlich indem man ihn so lange laufen lässt bis er fertig ist. Dem Programm das eine Zahl x als Eingabe annimmt und einfach die Zahl 0 zurückgibt kann man problemlos ansehen, dass es für jede Eingabe auch anhält. Aber es ist im allgemein nicht möglich festzustellen ob ein Programm ewig weiter läuft oder man noch nicht lange genug gewartet hat. Grüße. 80.133.169.163 21:46, 5. Apr. 2013 (CEST)

T verwendet seinen eigenen Quelltext

Ich bin schon sehr froh darüber, dass folgendes Thema im Artikel behandelt wird:

„Da die Konstruktion selbst sicher möglich ist, kann es eine solche Maschine H nicht geben.“

Allerdings vermisse ich noch den ausdrücklichen Hinweis darauf, ob es erlaubt ist, dass T (auch indirekt) die Maschiene H mit seinem eigenen Quelltext aufrufen darf. Erlaubt in dem Sinne, dass dann H dieses T (und dessen Eingabe) dann auch als Eingabe bekommen kann und dafür dann entscheiden soll, ob T mit der gegebenen Eingabe hält oder nicht. Damit wird die Aufgabenstellung präzisiert.

Egal, ob ja oder nein, die Aussage muss im Artikel drin stehen, sonst ist er unvollständig. --Headbreak (Diskussion) 19:35, 16. Mär. 2012 (CET)

Hallo Headbreak! Ich habe mir deinen Hinweis genau angesehen und möchte dir im Detail antworten:

1. "Quine" - ich vermute, das du diesen Sachverhalt meinst. Die Selbstbezüglichkeit hat zwar etwas mit dem Thema des Halteproblems zu tun, erklärt dieses aber nicht. Denn Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt.. Dabei ist der Alogithmus ansich erstmal zweitrangig (denn es gibt derer extrem viele), wichtig ist, ob er zu einem Ende kommt. Ein Quine wäre maximal ein Mittel zum Zweck der Illustration, da wir aber einfachere Beispiele (zur Illustration) gefunden haben, würde ich das Beispiel "Quine" nicht nehmen wollen.
2. Allerdings vermisse ich ... ob es erlaubt ist, dass ... die Maschien ... seinem eigenen Quelltext aufrufen darf. . Welchen Nutzen bringt ein solcher Hinweis? Schau dir bitte nochmal den Kontext an:

1. Der Nachweis, dass das Halteproblem nicht entscheidbar ist, geschieht durch einen Widerspruchsbeweis...
2. Dies gelingt mit der folgenden Konstruktion von Marvin Minsky,[3] der aus H eine weitere Turingmaschine konstruiert, die unmöglich existieren kann.
3. Da die Konstruktion selbst sicher möglich ist, kann es eine solche Maschine H nicht geben.

... die verwendete Kausalkette ist also beweisen durch Widerspruch > Beispiel-Maschine die widersprüchlich ist > was zu beweisen war.

... wozu also noch der Querverweis zu einer weiteren Möglichkeit, wenn bereits alles bewiesen ist? Du hast recht, das diese Möglichkeit existiert, aber sie ist nicht Beweisrelevant.

3. Dein Hinweis hat noch einen philosophischen Aspekt: "schaut, wieviele Parallelen es für das Halteproblem gibt". Ja, du hast recht. ABER: in Technik und Naturwissenschaft, bei der Konstruktion von Maschinen oder dem schreiben von Computerprogrammen ist das höchste aller philosophischen Gebote: die Abstraktion. Konkret heißt das: "... soll sich das Augenmerk auf das Wesentliche konzentrieren, d.h. auf eine ganz bestimmte begriffliche Bedeutung der so erfassten speziellen Merkmale.". Und das Quine ist nur ein Randthema, wie viele andere Aspekte in Wissenschaft und Technik auch Randthemen des Halteproblems sind. Daher sollten wir auf die Erwähnung des Quine verzichten.

Mit freundlichen Grüßen, --Friedrich Graf (Diskussion)

Der Beweis von Marvin Minsky benutzt nunmal ein Quine. „Die Fragestellung, ob Programme, die auf ihren eigenen Programmcode als Eingabe angesetzt werden, ist recht künstlich.“ (Informatik 5, S. 151, Ernst Klett Verlag) Zwar kann angeblich mittels des „Reduktionsprinzip“ gezeigt werden, dass dies auch für anderen Algorithmen gilt und schließlich sagt der Satz von Rice, dass nicht nur die Eigenschaft, ob eine Turingmaschiene terminiert, unentscheidbar sein kann. Aber im Grunde basiert der Beweis von Marvin Minsky nunmal auf dem Quine. --Headbreak (Diskussion) 22:01, 17. Mär. 2012 (CET)

Ich werde mir die von dir benannte Quelle ansehen. --Friedrich Graf (Diskussion) 22:33, 17. Mär. 2012 (CET)

Ich verwendete „Quine“ in dem Sinne davon, dass der eigene Quelltext verwendet wird. --Headbreak (Diskussion) 23:18, 17. Mär. 2012 (CET)

Ich habe im Katalog nachgesehen, das von dir beschriebene Buch läßt mehrere Schlüsse zu (u.a. ein Buch übers Klettern). Ich benötige daher noch Autor, Erscheinungsjahr, ISBN oder andere Identifizierungsmerkmale. Danke. --Friedrich Graf (Diskussion) 23:57, 17. Mär. 2012 (CET)

ich glaube, das ist nicht noetig. Headbreak hat eben geschrieben, dass er den begriff nicht in seiner ueblichen definition verwendet, sondern ihm seine eigene, private, bedeutung gibt. das ist fuer das schreiben einer enzyklopaedie uninteressant. im beweis gibt es keine quines. --Mario d 09:27, 18. Mär. 2012 (CET)

Dass die Maschine ihren eigenen Quelltext verwendet, ist tatsächlich interessant. Diese Art von Selbstbezüglichkeit findet sich in vielen Beweisen in der modernen Mathematik und Logik; sie ist beispielsweise der entscheidende Kniff in Gödels Beweis seines Unvollständigkeitssatzes. Vielleicht lohnt es sich tatsächlich, diesem Gedanken einen Absatz im Artikel zu widmen. Das sollte aber nicht in Form eines ungewohnten Begriffs geschehen, den der Leser nachschlagen muss. Gruß und schönen Sonntag allerseits :-) --Mussklprozz (Diskussion) 10:03, 18. Mär. 2012 (CET)

eigentlich handelt es sich um einer art von diagonalargument, das ist aber vielleicht nicht so leicht zu sehen. ich mache mal einen neuen abschnitt zum beweis auf. --Mario d 10:28, 18. Mär. 2012 (CET)

Beispiel

Im Artikel fehlt immernoch ein Beispiel, welches nicht "noch nicht entscheidbar" ist, sondern auch richtig "nicht entscheidbar". Außerdem soll bei diesem Beispiel stehen, ob dieses Beispiel eine Anwendung des Beweises ist, sich also die Äquivalente von T, F, G, und H auch im Beispiel zeigen lassen. --Headbreak (Diskussion) 20:02, 16. Mär. 2012 (CET)

Ich nehem an, das dein Wunsch jetzt erfüllt ist. --Friedrich Graf (Diskussion) 23:23, 16. Mär. 2012 (CET)

Nein, ist er nicht. --Headbreak (Diskussion) 22:02, 17. Mär. 2012 (CET)

Dann habe ich dich falsch verstanden - bitte erläutere mir nochmal deinen Gedanken. --Friedrich Graf (Diskussion) 22:35, 17. Mär. 2012 (CET)

Wie ich es gewünscht habe, habe ich es nun in den Artikel eingefügt. ([2]) Ich hoffe es genügt euren Ansprüchen. --Headbreak (Diskussion) 22:50, 17. Mär. 2012 (CET)

Headbreak: es gibt keinen Wikipedianer, der sagen darf "wie ich es gewünscht habe". In Wikipedia gibt es weder Könige oder Diktatoren. Wenn du diese Bemerkung auch nur halbwegs ernst gemeint hast, darfst du dich nicht über soviel Ablehnung in der Community wundern.

... falls dies allerding ein großes Mißgeschick von dir war, solltest du jetzt sehr deutlich eine Endschuldigung schreiben. --Friedrich Graf (Diskussion) 23:39, 17. Mär. 2012 (CET)

P.S. Mich interessiert nicht der beleidigende Tonfall hinter deiner Bemerkung - dies ist mir egal. Mich interessiert ausschliesslich deine Absicht. Und die von dir beschriebene Absicht verstößt gegen dutzende Wiki-Prinzipien.

Ich versuche sämtliche Wikipedia-Beiträge so zu machen, wie ich sie mir wünsche. Damit ist nicht ein utopischer Endstatus gemeint, sondern ein kurzfristiges Ziel, welches für meinen Beitrag realistisch sein soll. --Headbreak (Diskussion) 10:44, 18. Mär. 2012 (CET)

mächtiger Formalismus

Ich halte diese Formulierung nicht für ganz glücklich: und sich streng an einen mächtigen Formalismus hält. - hat jemand eine bessere Idee? --Friedrich Graf (Diskussion) 23:02, 16. Mär. 2012 (CET)

Zur Erklärung:

1. das Wort "Mächtig" wollten wir vermeiden
2. das Wort "Formalismus" wird definiert: Der Formalismus ist eine von David Hilbert gegründete Schulrichtung der Grundlagenforschung in der Mathematik. ... Das Anliegen bestand darin, allein von der Form her die Vollständigkeit und Widerspruchsfreiheit der Axiomensysteme der Mathematik zu beweisen.. Und genau dieser Sachverhalt verträgt sich nicht mit den Grundlagen des Halteproblems. ... ich bin daher für löschen oder umformulieren dieses Satzes.

Ansonsten macht euch bitte an die Kontrolle. Wenn alles erledigt ist, kommen wir dann langsam auf die Zielgerade. Gute Nacht! --Friedrich Graf (Diskussion) 23:26, 16. Mär. 2012 (CET)

Mein Vorschlag, nein, Douglas R. Hofstadters Vorschlag: mathematisch überzeugend statt mächtig. Vgl. Douglas R. Hofstadter, Metamagikum, Klett-Cotta, Stuttgart 1988, S. 8 oben. Gruß, --Mussklprozz (Diskussion) 10:11, 18. Mär. 2012 (CET) So, jetzt bin ich aber wirklich weg für heute ...

Laienverständlichkeit

Hallo Headbreak!

Du warst damit einverstanden, das Lemma laienverständlicher zu machen. Bitte zerstöre nicht diese Bemühung. Wenn du also eigene Inhalte ergänzen willst, mache es bitte in laienverständlicher Form. Falls dir das schwerfällt, kann ich dir gerne helfen (allerdings mußt du dann auch mit meinen Kommentaren leben). Danke. --Friedrich Graf (Diskussion) 23:29, 17. Mär. 2012 (CET)

Mit dem JavaScript-Code wäre es zumindest für jeden verständlich, der JavaScript kann, und das sind einige Menschen ab dem Alter von ungefähr 12 Jahren. Etwas wird dadurch verständlicher, dass es detailiert erklärt wird, nicht dadurch, dass etwas in der Erklärung weggelassen wird. --Headbreak (Diskussion) 23:31, 17. Mär. 2012 (CET)

1. Meine Tochter ist 14 Jahre alt und besucht ein Gymnasium. Mit ihren Leistungen liegt sie oberhalb des Klassendurchschnitts - und: ich kann dir versichern, das sie noch nie etwas von Java-Script gehört hat.
2. Falls dein Inhalt richtig ist, ließe sich im hinteren Teil des Lemmas auch ein Unterkapitel finden - Falls ... --Friedrich Graf (Diskussion) 23:43, 17. Mär. 2012 (CET)

Dann warte ich mal darauf, dass Musklprozz, MarioS oder ein anderer Benutzer seinen Kommentar abgibt. --Headbreak (Diskussion) 10:57, 18. Mär. 2012 (CET)

ich wiederhole meinen kommentar von oben: "die konstruktion im beweis [ist] black-box, d. h. G muss nur die schnittstellen von H kennen. die konstruktion in deinem code ist nicht black-box, denn die funktion a muss die beschreibung von H kennen um den quellcode auszugeben." weiterhin "beruht der beweis darauf, dass die konstruktion von F aus H einfach und offensichtlich machbar ist. das ist in deinem code nicht der fall, denn nicht jede TM kann ihre eigene beschreibung ausgeben." dein erster algorithmus verwendet zwei funktionen, du hast damit gezeigt, dass eine von beiden nicht existiert. natuerlich kann man alle TMs auch in JavaScrip schreiben, da wir die funktion allerdings bereits in pseudocode und mit einem bild darstellen, sehe ich den zusaetzlichen nutzen nicht. --Mario d 12:52, 18. Mär. 2012 (CET)

Schau dir bitte nochmal die letzte Umformung an. Dabei kommt gar kein a vor. Dann zeige mir, welche Zeile nicht dem Beweis entspricht und wie sie anders hätte lauten sollen. Für mich ist die JavaScript-Darstellung bei weitem verständlicher als der ausformulierte Text oder das Bild. Außerdem wird gezeigt, dass die Turingmaschiene deutlich vereinfacht werden kann, ohne, dass sie ihre Funktionalität verliert. Was du unter deinem Blackbox-Prinzip verstehst, bleibt mir unverständlich. a muss keinesfalls die Beschreibung von h kennen. Du kannst ja mal die Funktion toSource() in einem Mozilla-Browser ausprobieren – die Funktionen sind alle nur als Schnittelle und nicht als Beschreibung verfügbar. Wenn allerdings H prüfen soll, ob das Programm hält, muss h natürlich auch wieder den Quelltext von allen aufgerufenen Funktionen überprüfen. Das ist in der Beweisskizze auch nicht anders. --Headbreak (Diskussion) 13:00, 18. Mär. 2012 (CET)

beweis

oben wurde angesprochen, ob wir parallelen zu goedels unvollstaendigkeitssatz zeigen wollen. ich meine, dazu sollten wir zuerst den artikel Cantor-Diagonalisierung ausbauen (s. engl. version), dann koennten wir darauf verlinken und die erklaerung einfach halten.

zum zweiten stellt sich dem leser vielleicht die frage, was die maschine G im beweis soll. vielleicht sollten wir besser herausarbeiten, dass wir eigentlich zeigen, dass das komplement des halteproblems nicht semi-entscheidbar ist und der satz daraus folgt. --Mario d 10:34, 18. Mär. 2012 (CET)

ich habe den zweiten punkt jetzt mal umgesetzt. der beweis benoetigt nun zwar ein paar begriffe mehr, aber die vorgehensweise und insbesondere die funktion von F und G sollte jetzt klarer sein. als bonus taucht jetzt auch die verbindung zur diagonalisierung auf. --Mario d 21:56, 21. Mär. 2012 (CET)

BTHP

im zweiten abschnitt erwaehnen wir, dass die nicht-berechenbarkeit der Radó-Funktion aus der unentscheidbarkeit des halteproblems folgt. das kommt vielleicht ein bischen ueberraschend, weil man dazu wissen muss, dass das halteproblem mit leerem eingabeband (blank-tape halting problem, BTHP) zum halteproblem aequivalent ist. das koennte man kurz mit der bemerkung abhandeln, dass man die eingabe auch im startzustand speichern kann, aber das passt nicht so recht in den abschnitt. hat jemand dazu einen vorschlag? --Mario d 10:40, 18. Mär. 2012 (CET)

Am besten es wird noch eine Beweisführung angefügt, die zeigt, warum die Nicht-Berechenbarkeit der Radó-Funktion aus dem Halteproblem folgt. --Headbreak (Diskussion) 10:59, 18. Mär. 2012 (CET)

dann waere noch zu entscheiden, wie ausfuehrlich man das macht und wo imn artikel es sinnvoll untergebracht werden kann. --Mario d 13:00, 18. Mär. 2012 (CET)

Notfalls kann doch einfach ein entsprechender Unterartikel für den ausführlichen Beweis erstellt werden. In diesem Artikel gibt es dann eine kleine Zusammenfassung und nach einem Klick auf den „Hauptartikel“-Link erfährt man mehr. --Headbreak (Diskussion) 13:14, 18. Mär. 2012 (CET)

ich glaube nicht, dass das fuer einen unterartikel genug hergibt, und thematisch gehoert es sicher in diesen artikel. --Mario d 19:56, 21. Mär. 2012 (CET)

Und wann kommt endlich der Beweis der Nicht-Berechenbarkeit der Radó-Funktion? Ein erster Ansatz mit dem Halteproblem mit leerem Eingabeband wurde hier ja schon erklärt, aber da fehlt doch wahrscheinlich noch was für den Beweis in diesem besonderen Fall. --Headbreak (Diskussion) 15:11, 4. Mai 2012 (CEST)

oh, das ist wohl liegengeblieben. ich kann am wochenende mal drauf schauen. --Mario d 17:55, 4. Mai 2012 (CEST)

ich habe das BTHP hinzugefuegt. die nichtberechenbarkeit der Radó-funktion gehoert auf die entsprechende seite, nicht hierher. ich habe dort aber auch etwas dazu geschrieben. --Mario d 20:14, 5. Mai 2012 (CEST)

Widerspruch

Ich möchte mal auf folgenden Widerspruch hinweisen:

• Das Halteproblem ist offensichtlich semientscheidbar
• Das Halteproblem ist nicht semi-entscheidbar

Falls es sich um eine Antinomie handelt, sollte das auch so genannt werden. Falls nicht, sollte der Unterschied zwischen „semientscheidbar“ und „semi-entscheidbar“ erläutert werden. (nicht ernst gemeint) --Headbreak (Diskussion) 23:32, 5. Mai 2012 (CEST)

Ja, das liegt daran, dass das, was hier in "Schritt 2" als nicht semientscheidbar nachgeweisen wird, nicht das Halteproblem ist, sondern dessen Komplement (jedenfalls nach den in der Literatur üblichen Definitionen). Man könnte nun zwar sagen, Namen seien Schall und Rauch, und eine Definition stehe ja im Artikel, aber ich denke, das wäre 'ne schlechte Idee. --Daniel5Ko (Diskussion) 01:28, 6. Mai 2012 (CEST)

Also das das Komplement des Halteproblems soll nicht semi-entscheidbar sein? --Headbreak (Diskussion) 02:00, 6. Mai 2012 (CEST)

Richtig. --Daniel5Ko (Diskussion) 02:38, 6. Mai 2012 (CEST)

im abschnitt "beweisidee" wars noch richtig erklaert. ich habs jetzt im beweis korrigiert. --Mario d 09:49, 6. Mai 2012 (CEST)

Genauso wollte ich das auch verändern. --Headbreak (Diskussion) 14:20, 6. Mai 2012 (CEST)

Collatz-Vermutung als Illustration des Halteproblems

Im Abschnitt "Illustration" wird die Collatz-Vermutung bemüht. So wie sie dargestellt ist, ist sie ein ausgesprochen schlechtes Beispiel für das Halteproblem, da sie definitiv nie anhält, weil keine Abbruchbedingung formuliert ist. Nur weil (vermutlich) jede Folge in 4-2-1 endet, besagen die 4 Schritte nicht das hier aufzuhören, sondern mit der 1 als ungerade Zahl gemäß Schritt 3 stets weiter zu machen ist. -- 79.208.58.70 23:19, 7. Sep. 2012 (CEST).

das wurde irgendwann geaendert um die verstaendlichkeit zu verbessern, ich habe das programm jetzt korrigiert. --Mario d 15:58, 10. Sep. 2012 (CEST)

Ja, jetzt ist's richtig. Danke! -- 87.176.213.205 18:07, 10. Sep. 2012 (CEST).

unendlich und endlich

Wenn es keinen Algorithmus gibt, der eine unendliche Anzahl von Eingabedaten verarbeiten kann, schließt das nicht aus, dass es vielleicht doch einen gibt, der eine endliche Anzahl Eingabedaten verarbeiten kann.

Beispiel: Ein Algorithmus könnte für jedes Programm bis zu einer Größe von 10 GB das Halteproblem lösen. Damit das Diagonalproblem nicht auftaucht, gehen wir einfach davon aus, dass das Programm selbst größer sei als 10 GB, sodass es sich selbst gar nicht zu prüfen braucht.

So ein Programm wäre durchaus höchst nützlich. Die Berechenbarkeitstheorie sagt nichts darüber aus, ob ein solcher Algorithmus existieren könnte.

Kein praktisches Programm und kein Computer, den es je geben wird, wird eine unendliche Anzahl von Eingaben verarbeiten können. Somit ist die Suche nach einem Programm, das unendlich viele Eingaben verarbeiten können muss, oder die Frage, ob eines existieren könnte, unsinnig.

Für die Praxis der Softwareentwicklung hat das Halteproblem sowie die gesamte Berechenbarkeitstheorie überhaupt keine Relevanz. Wenn dies nicht gleichzeitig erwähnt wird, richtet die Theorie großen Schaden an, da der Leser glauben kann, der Computer könne gewisse Dinge nicht und für gewisse Probleme bräuchte man also gar keine Lösung zu suchen. Dabei beweist die Theorie gar nichts, was für die Praxis von irgendeiner Bedeutung wäre.

--Bigben.in (Diskussion) 16:17, 15. Mai 2013 (CEST)

wo jetzt grosser schaden angerichtet werden soll, kann ich nicht erkennen. ich denke, der abschnitt Halteproblem#Illustration sollte ausreichen um zu verdeutlichen um was es geht. --Mario d 22:01, 15. Mai 2013 (CEST)

Der letzte Abschnitt unter "Bedeutung" sollte folgendermaßen geändert werden:

Für die Softwareentwicklung folgt aus der Nichtentscheidbarkeit des Halteproblems gar nichts, da in der Praxis nur endlich viele Programme zu verifizieren sind und es daher unerheblich ist, wenn unter einer unendlichen Zahl von Programmen einige vielleicht nicht verifizierbar sind. Programme verarbeiten auch nur endliche Datenmengen. Wenn es für ein bestimmtes Problem kein Programm gibt, das unendlich viele Eingabedaten verarbeiten kann, kann es natürlich trotzdem eines geben, das (alle in der Praxis vorkommenden) endlich vielen Daten korrekt verarbeiten kann (und bei diesen immer hält).

--Bigben.in (Diskussion) 08:00, 16. Mai 2013 (CEST)

ich habe den verweis auf die softwareentwicklung rausgenommen. dass fuer die praxis nichts folgt, stimmt nicht, es folgt naemlich, dass es kein programm gibt, dass bei beliebigen anderen programmen feststellt, ob sie terminieren. dass in der praxis programme aus bestimmten klassen verifizierbar sind, steht bereits im text. das liegt aber an ihrer struktur und nicht an der laenge, im abschnitt illustration ist ein kurzes programm angegeben, fuer das nicht klar ist, ob es terminiert. --Mario d 11:12, 16. Mai 2013 (CEST)

Mensch

Kann denn ein Mensch für jeden möglichen Algorithmus und jede mögliche Eingabe entscheiden, ob der Algorithmus zu einem Ende gelangt? Wenn ja, warum kann er das? Und heisst das dann, dass es niemals eine vollwertige künstliche Intelligenz geben kann? Wenn nein, ist er dann genauso limitiert wie eine Turing-Maschine?

Das im Abschnitt Illustration aufgeführte Collatz-Problem ist etwas, das eines Tages mathematisch bewiesen wird, und damit kann eine Aussage getroffen werden, ob der Algorithmus terminieren würde oder nicht. Also muss es einen Algorithmus geben, der diesen Beweis führen kann. Oder ist es unmöglich, für jedes mathematische Problem einen Beweis zu führen?

(nicht signierter Beitrag von 2003:63:2f25:3301:7926:4656:6a5:2f8a (Diskussion) 00:59, 23. Jul. 2013)

Das gehört eigentlich nicht hierher, weil dies hier ein Platz ist, um Artikelverbesserungen zu diskutieren, und nicht, um Fachfragen zu stellen. Ich will ausnahmsweise trotzdem antworten:

1. Ein Mensch kann schon deswegen nicht das Halteproblem entscheiden, weil er nur begrenzt viel Zeit und begrenzt viel Hirnkapazität hat. Bei der Turingmaschine wird vorausgesetzt, dass ihr Speicher beliebig erweitert werden kann und dass sie beliebig viel Zeit hat.
2. Ob es prinzipiell eine vollwertige künstliche Intelligenz geben kann, ist umstritten. Lies hierzu beispielsweise den Artikel Chinesisches Zimmer.
3. Es ist unmöglich, für jedes mathematische Problem einen Beweis zu führen. Das folgt aus dem Gödelschen Unvollständigkeitssatz.

--Mussklprozz (Diskussion) 07:43, 23. Jul. 2013 (CEST)

Anmerkung: Semi-entscheidbar wenn Reduktion auf PCP?!

Tag zusammen. Da ich zur Zeit für eine Prüfung lerne ist mir aufgefallen, dass hier keineswegs erwähnt wird, dass das Halteproblem H auf das postsche Korrespondenzproblem PCP reduziert werden kann. Im Wiki Artikel zum PCP gibt es einen Hinweis, dass dieses semi-entscheidbar werden kann (bzw ist?!) und in meiner Vorlesung hab ich entsprechend gelernt, dass H <= PCP gelten kann. Somit wäre doch H nach dieser Argumentation in irgendeinem Fall semi-entscheidbar, oder? Mag mir das eventuell jemand widerlegen o.Ä.? (nicht signierter Beitrag von 188.101.207.70 (Diskussion) 07:12, 24. Feb. 2014 (CET))

PCP ist semi-entscheidbar. Das ist aber keine Eigenschaft von H (d.i. muss u.a. nicht unbedingt umseitig erwähnt werden). Reduktion geht in eine Richtung: Wenn A<=B, dann: wenn B (semi)entscheidbar, dann A (semi)entscheidbar. Ich würde dir raten, nicht (nur) nach deinen Notizen und Wikipedia zu lernen, sondern ein Einführungsbüchlein in die theoretische Informatik zu kaufen, z.B. Schöning, siehe dort die Beweise in Kap. 2.7. Weitere Informationsfragen vielleicht besser unter WP:AU. Schöne Grüße, ca$e 08:54, 24. Feb. 2014 (CET)

Halteproblem ohne jegliche Bedeutung für Computer mit endlichem Speicher

Ein Computer hat stets nur einen endlichen Speicher und entspricht somit einer linear beschränkten Turingmaschine. Für diese ist das Halteproblem entscheidbar. Somit hat die Unentscheidbarkeit des Halteproblems für allgemeine Turingmaschinen keinerlei Bedeutung für tatsächlich existierende Computersysteme

--Bigben.in (Diskussion) 10:04, 1. Sep. 2017 (CEST)

Ich habe mich vor allem an dem „keinerlei“ gestört. Ich hab' jetzt keine Belege dafür, aber meine praktische Erfahrung mit Beweisen zu realen Programmen sieht anders aus: Details wie die Endlichkeit des Speichers werden weg-abstrahiert. Ein derart korrekt bewiesenes Programm kann auf einem realen Computer immer noch scheitern (abbrechen), weil nicht genug Speicher da ist.

Außerdem meine ich mich zu erinnern, daß es mindestens einen ernst gemeinten Fall gab, wo ein Entwickler-Team ein Programm-Analyse-Tool bauen wollte, das (nebenbei) das Halte-Problem gelöst hätte.

--H.Marxen (Diskussion) 14:13, 1. Sep. 2017 (CEST)

Hallo Bigben, Deine Aussage hier oben ist exakt der Wortlaut, den Du auch im Artikel eingebracht hattest und den ich mit folgendem Vermerk in der Zusammenfassungszeile revertiert hatte: „Sorry, aber ob das Halteproblem überhaupt und speziell so einen (Nicht-)Bezug zu einem realen Computer hat, der hier dann so beschrieben sein muss, ist mir nicht klar. Bitte Belege.“ So eine Aussage wie die Deine ist nicht trivial und muss - wenn sie von Anderen angezweifelt wird - mit Belegen aus reputablen Quellen untermauert werden. Auch, um nicht fälschlich als WP:Theoriefindung abqualifiziert zu werden. VG --Apraphul ^Disk _WP:SNZ 16:11, 1. Sep. 2017 (CEST)

In Hilberts Hotel, wenn es voll belegt ist, kann trotzdem noch ein Gast einziehen. Das liegt daran, dass das Hotel unendlich viele Zimmer hat. Diese Eigenschaft kann man aber auf kein Hotel übertragen, das nur endlich viele Zimmer hat. In ein voll besetztes Hotel kann kein Gast mehr einziehen.

Die Berechenbarkeitstheorie geht davon aus, dass es unendlich viele Algorithmen gibt und ebenso viele Turing-Maschinen, die darüber hinaus auch noch unendlich viel Speicherplatz (Arbeitsspeicher) haben. Ferner setzt die Berechenbarkeitstheorie voraus, dass die Geschwindigkeit der Maschinen unerheblich ist, also für den Menschen, der auf die Maschine wartet, der Faktor Zeit gänzlich unerheblich ist. Unter dieser Prämisse behauptet die Berechenbarkeitstheorie v. A. die Unentscheidbarkeit von manchen Fragestellungen, bei denen die Beantwortung von unendlich vielen Fragen erwartet wird. Keine Maschine und kein Mensch werden aber je unendlich viel Speicherplatz haben, nie wird der Faktor Zeit belanglos sein, und solange die Menschheit existiert, wird sie auch nur endlich viele Fragen stellen und nur endlich viele Algorithmen benutzen.

Ist Hilbers Hotel für die Hotellerie von Bedeutung? Natürlich nicht!

Ist die Berechenbarkeitstheorie für die Software-Entwicklung von Bedeutung? Aus demselben Grund: nein!

--Bigben.in (Diskussion) 14:30, 7. Sep. 2017 (CEST)

Zu komplizierter Satz

Dieser Satz klingt für Nicht-Kundige grammatikalisch unvollständig: "Das folgende Programm hält für jede Eingabe n (bei n>0 und n∈{N} ), wenn die bisher unbewiesene Collatz-Vermutung richtig ist. " Ein unbedarfter Leser/eine unbedarfte Leserin wird lange suchen, was das Programm den "nun eigentlich hält"? Es wird ein ganzes Weilchen dauern, bis kapiert wird "Das Programm hält AN". Dieser Satz sollte daher dringend verbessert werden, gerade im Sinne von Leuten, die nicht so tief in der Materie drin sind und sich (bloß) einen Überblick bzw. einen (groben) Überblick verschaffen wollen (oder müssen). DANKE! --Molekuelorbital (Diskussion) 16:15, 7. Sep. 2023 (CEST)

Das Halteproblem ist entscheidbar genau dann, wenn sowohl das Halteproblem als auch sein Komplement semientscheidbar sind.

Diese Beziehung mag Fachkundigen bekannt sein, aber sie erscheint mir nicht auf so triviale Weise offensichtlich, dass man sie ohne Beweis voraussetzen kann. Kann bitte jemand ergänzen, aus welchem Satz das dies folgt oder einen kurze Bewisskizze angeben? --217.18.181.18 17:04, 10. Jun. 2024 (CEST)

Das Halteproblem fragt, ob eine bestimmte Turing-Maschine bei einer gegebenen Eingabe anhält. Das Komplement des Halteproblems fragt, ob die Turing-Maschine bei dieser Eingabe nicht anhält. Semientscheidbar bedeutet, dass es eine Methode gibt, die in endlicher Zeit erkennt, wenn die Maschine anhält (für das Halteproblem) oder nicht anhält (für das Komplement). Wenn man beide Fragen zuverlässig beantworten kann, dann ist das Halteproblem entscheidbar, weil man immer eine klare Antwort erhält. Da jedoch das Halteproblem unentscheidbar ist, kann das Komplement nicht semientscheidbar sein. ca$e 13:39, 11. Jun. 2024 (CEST)