Diskussion:Entscheidbarkeit

Link hinzugefügt

Habe den Link zur Linearen Diophantischen Gleichung hinzugefügt. Tobias

Echte Unentscheidbarkeit

Nach reiflicher Überlegung frage ich mich, ob es überhaupt ein (sinnvolles) Problem geben kann, das echt unentscheidbar ist. Bzw. frage ich mich, ob Semi-Entscheidbarkeit überhaupt eine echte Teilmenge von Unentscheidbarkeit ist. Hat dazu jemand eine Info? Sowohl das PCP als auch das Halteproblem sind ja (auch) semi-entscheidbar. --F GX 11:13, 17. Sep. 2009 (CEST)

OK ich glaube ich kann es selbst beantworten, das Komplement des (speziellen) Halteproblems, also die Sprache aller Maschinen die auf sich selbst nicht hält, ist nicht semi-entscheidbar sondern nur unentscheidbar. So wie generell alle Komplemente aller Sprachen die semi-entscheidbar und unentscheidbar sind, echt unentscheidbar sind. Und natürlich, die Komplemente aller Sprachen die semi-entscheidbar und entscheidbar sind, wiederum nicht unentscheidbar sind. Ist es denn sinnvoll, das irgendwie in den Artikel einzuarbeiten? Gerade weil es etwas kompliziert ist. Leider traue ich mich noch nicht ganz, weil ich das Konzept der Semi-Entscheidbarkeit immer noch nicht 100% durchblickt habe.--F GX 16:00, 18. Sep. 2009 (CEST)

Lemma und Einleitung

Müsste das Lemma nicht „Entscheidbarkeit“ oder „Entscheidungsproblem“ sein? Für gewöhnlich wird Nominativ Singular verwendet.

Zudem bin ich mit der Einleitung nicht zufrieden. Es wird nicht erklärt worum es eigentlich geht – einen Begriff in der theoretischen Informatik. Für Leser die keine Ahnung davon haben sollte wenigstens eine Zuordnung zu einem Fachbereich möglich sein. Gruß, --Church of emacs D B 13:16, 5. Okt. 2010 (CEST)

Zum "Zudem"-Teil: Ich habe den 1. Satz entsprechend geändert. -- UKoch 19:03, 13. Jul. 2011 (CEST)

Entscheidungsprobleme und Entscheidbarkeit

Ob ein Problem / eine Sprache entscheidbar ist, hat doch eigentlich nichts mit Entscheidungsproblemen zu tun. Die Weiterleitung sollte entfernt werden. Das hier sind Entscheidungsprobleme:

• TSP-Entscheidungsproblem: Gibt es eine Route der Länge 100 km (oder weniger) durch eine gegebene Menge an Städten?
• KNAPSACK-Entscheidungsproblem: Gibt es eine Rucksack-Belegung mit einem minimalen Wert von 100 für einen gegebenen Rucksack und gegebene Gegenstände?

Alle Entscheidungsprobleme sind entscheidbar (soweit ich weiß), indem man schlicht alle Möglichkeiten durchgeht. Ich glaube jedes Optimierungsproblem kann als Entscheidungsproblem formuliert werden. --MartinThoma 17:25, 7. Jan. 2012 (CET)

Können Optimierungsprobleme Entscheidungsprobleme sein?

Hallo,

ich bin in den Artikeln Partitionsproblem und Optimierungsproblem darauf gestoßen, dass beliebige Probleme, deren Lösung Ja oder Nein ist, als „Entscheidungsprobleme“ bezeichnet werden. Das scheint mir nicht ganz richtig:

Das Entscheidungsproblem, wie umseitig definiert, stellt ja die Frage nach der Existenz eines Verfahrens, das ein Problem löst, nicht die Frage nach der Lösung selbst. Es handelt sich also um ein Meta-Problem, dass Aussagen über Problemlöser (deren Existenz, deren Unmöglichkeit, etc.) macht.

Insofern ist das Partitionsproblem kein Entscheidungsproblem, auch wenn man es auf eine „Ja-Nein-Frage“ beschränkt. Denn die Entscheidbarkeit des Partitionsproblems ist bereits mit seiner NP-Vollständigkeit bewiesen.

Oder liege ich hier falsch? Grüße, --Tobias D B 21:16, 29. Apr. 2012 (CEST)

Letzteres. Das Partitionierungsproblem ist ein Entscheidungsproblem. Entschieden wird die Frage "Gibt es für die Zahlen a,b,c,d,... eine Partitionierung in zwei Mengen, so dass [...] die Differenz der beiden Summen kleiner als die gegebene Schranke n ist." Antwort: Ja oder Nein. Das ist also ein Entscheidungsproblem, da man sich für jede Problemstellung zwischen ja und nein entscheiden muss. Da es für alle möglichen Problemstellungen ein Verfahren gibt, um zur gesuchten Entscheidung zu kommen (z.B. einfach alle Kombinationen ausprobieren), ist das Problem entscheidbar (=es ist möglich, die Entscheidung zu treffen). Anders beim Halteproblem: Für dieses Problem ist bewiesen, dass es kein Verfahren geben kann, dass für alle erlaubten Eingaben die Entscheidung richtig treffen kann. Das Problem ist nicht entscheidbar. Mit der Laufzeit (=Komplexitätsklasse) hat das erstmal nichts zu tun. Du hast allerdings insofern Recht, dass aus der NP-Zugehörigkeit auch die Entscheidbarkeit folgt.

Nochmal kurz: Entscheidungsproblem ist nicht "das Problem ist entscheidbar".  — Felix Reimann 13:08, 2. Mai 2012 (CEST)

Halteprobleme

Der Abschnitt Halteprobleme ist aus meiner Sicht grob fehlerhaft und nicht durch kleinere Korrekturen zu retten.

Erstens beschäftigt sich das Halteproblem nicht nur mit Turing-Maschinen, sondern gilt allgemein.
Zweitens sind die Aussagen über die Turing-Maschinen sehr unklar formuliert und nach meinem Verständnis einfach falsch. Die Aussage, dass das Halteproblem für linear beschränkte Turing-Maschinen entscheidbar sei, ist mir komplett neu. Leider fehlt mir hierzu eine Quellenangabe, aber aus meiner Sicht ist es offensichtlich, dass auch eine linear beschränkte Turing-Maschine in eine Endlosschleife geraten kann, woraus folgt, dass das Halteproblem auch hier unentscheidbar ist.

Gibt es Einwände dagegen, dass ich den Absatz komplett neu schreibe? Folgendes wäre mein Vorschlag, kurz, knapp und sicher fehlerfrei:

Das Halteproblem beschreibt die Frage, ob ein Algorithmus mit einer Eingabe terminiert. Alan Turing wies die Unentscheidbarkeit dieser Frage nach.--Lex parsimoniae (Diskussion) 22:25, 30. Aug. 2012 (CEST)

Ich stimme zu, dass man "Algorithmen" nehmen soll. Allerdings finde ich sonst die Formulierung im Artikel klarer. Bei Deiner Formulierung ist nicht mehr so klar, dass das Halteproblem eine Menge von Paaren aus Algorithmus und Eingabe bezeichnet, und nicht etwa pro Algorithmus eine Menge von Eingaben (dann ist es mal entscheidbar, mal unentscheidbar), und erst recht nicht das Problem "Hält Algorithmus (irgendein Algorithmus) auf Eingabe 'abcd'" (dann ist es prinzipiell entscheidbar). Wenn Du die Formulierung im Artikel zu verworren findest, kann man ja zuerst Deine und dann "formal bezeichnet es eine eigenschaft..." schreiben. Bei linear beschränkten Maschinen geht das Entscheiden so: da der Platz beschränkt ist, gibt es nur endlich viele (sagen wir N) Konfigurationen, in denen sich die Maschine während der Berechnung befinden kann. Falls die Maschine nicht in eine Schleife gerät, hält sie spätestens nach N Schritten, denn sobald eine Konfiguration zweimal besucht wurde, ist man in eienr Schleife. Soweit für deterministsiche Maschinen; für nichtdeterministische Maschinen geht es so ähnlich, indem man die Zustandsmenge aufbläht. Gruß--Schreiber ✉ 22:53, 30. Aug. 2012 (CEST)

Hallo Schreiber, vielen Dank für Deine Erklärung. Mit der linear beschänkten TM hast Du natürlich Recht.

Wie wäre es, wenn ich folgenden Satz am Anfang des Kapitels hinzufüge:

"Das Halteproblem beschreibt allgemein die Frage, ob ein Paar, das aus Algorithmus und Eingabe besteht, terminiert. Alan Turing wies die Unentscheidbarkeit dieser Frage nach."

Möchtest Du dann vielleicht selbst den momentan noch ersten Satz wie von Dir beschrieben anpassen?--Lex parsimoniae (Diskussion) 23:39, 30. Aug. 2012 (CEST)

Klingt gut!--Schreiber ✉ 23:55, 30. Aug. 2012 (CEST)

Hm naja wobei, ich würde das mit dem Paar weglassen, denn was terminiert, ist ja der Algorithmus und nicht das Paar. Also eher wie Du oben geschrieben hast. Gruß--Schreiber ✉ 23:57, 30. Aug. 2012 (CEST)

Gut, ich trage das mal ein. Schau Dir dann bitte noch mal den Rest des Abschnitts an.--Lex parsimoniae (Diskussion) 00:13, 31. Aug. 2012 (CEST)

Man beachte: Nicht entscheidbar ist, ob eine linear beschränkte TM bei irgendeiner Eingabe hält (bekanntermaßen ist unentscheidbar, ob eine kontextsensitive Sprache leer ist). Und nach dem Satz von Immerman und Szelepcsényi sind die kontextsensitiven Sprachen abgeschlossen unter Komplementation und wenn ich das richtig sehe (müsste man nochmal prüfen), geht der Beweis über eine berechenbare Reduktion, sodass auch das Problem, ob eine linear beschränkte TM immer hält, unentscheidbar. --Chricho ¹ ² ³ 17:37, 1. Sep. 2012 (CEST)

Ja, das müsste stimmen, die Reduktion ist wohl berechenbar. Wäre im Artikel erwähnenswert (das Phänomen, dass "uniformere" Versionen des Halteproblems unentscheidbar bleiben, ist ja häufiger), habe aber keine Referenz dafür gefunden. Direkt durch Reduktion aufs Halteproblem müsste es auch so gehen (habe es aber nicht im Detail durchdacht): Für jedes Paar TM-Eingabe gibt es (berechenbar) eine linear beschränkte TM, die bei Eingabe mit Länge k genau dann hält, wenn die TM auf der Eingabe in Platz $\leq k$ hält (man ersetzt den Anfang des Bandes durch die Eingabe und simuliert dann die TM. Sobald man dabei die Platzbeschränkung erreicht, geht man in eine Endlosschleife.). Dann hält die TM auf der angegebenen Eingabe gdw. die linear beschränkte TM für eine Eingabe hält.--Schreiber ✉ 19:55, 1. Sep. 2012 (CEST)

Damit hat man doch aber auch nur das „jemals halten“ und nicht das Komplement „immer halten“, oder? Aber das sieht gut aus. --Chricho ¹ ² ³ 20:07, 1. Sep. 2012 (CEST)

Äh ja, da hast du natürlich recht^^ Also so: Man hält nur dann, wenn man die Platzbeschränkung erreicht. Kommt die TM in einen Endzustand, geht man in eine Endlosschleife. Dann hält die linear beschränkte Maschine immer gdw. die TM nie hält.--Schreiber ✉ 20:20, 1. Sep. 2012 (CEST) Ähm ja.--Schreiber ✉ 20:22, 1. Sep. 2012 (CEST)

Jaja, so ein Durchstreichen hatte ich vorhin auch bei mir im Kopf.^^ --Chricho ¹ ² ³ 20:24, 1. Sep. 2012 (CEST)

:D Dann noch ein Versuch xD Man beschränkt auch die Zeit, und hält auch dann, wenn die Zeitschranke erreicht ist. Es genügt, wenn Zeit- und Platzschranke unbeschränkte Funktionen von n sind, da es nur um eine einziges Eingabe-TM-Paar geht. Das Beschränken der Zeit geht dann so: Man schreibt auf die ersten n/2 Zellen Nullen, dann ein Trennzeichen (man reinigt das Band, dann geht man abwechselnd zum linken und rechten Ende und füllt vom Rand her mit 1 auf, dann erreicht man die Position n/2), dann die Eingabe. Man simuliert die TM rechts vom Trennzeichen, und bei jedem Schritt der TM fügt man in der linken Hälfte eine Eins hinzu (man ersetzt das Symbol an der Kopfposition der TM durch ein diesem Symbol zugehörendes Spezialsymbol, geht nach links über das Trennzeichen zur ersten 0, schreibt eine Eins, kehrt zum Spezialsymbol zurück). Erreicht man dabei das linke Ende, hält man. Damit hält die linear beschränkte immer gdw. die TM nie hält. Wie zuvor ohne Gewähr auf Richtigkeit^^--Schreiber ✉ 20:56, 1. Sep. 2012 (CEST)

Ja, so sollte man das machen können. :) --Chricho ¹ ² ³ 22:12, 1. Sep. 2012 (CEST)

Titel „Entscheidbar“

Ich würde gerne den Artikel zu „Entscheidbarkeit“ verschieben (umbenennen). Gibt es einen bestimmten Grund, dass der Artikel nicht so heißt? Ansonsten berufe ich mich auf Wikipedia:Namenskonventionen#Abstraktes_Substantiv. Spezialist^D 22:34, 7. Jul. 2015 (CEST)

Wäre auch für eine Umbenennung und unterstütze dieses Vorhaben. --Andreschulz (Diskussion) 20:37, 30. Jul. 2015 (CEST)

Bin auch dafür, aber... es gibt schon eine Weiterleitungsseite „Entscheidbarkeit“ --> „Entscheidbar“, so daß die beiden also die Rollen tauschen sollten, oder? Außerdem wäre es vielleicht ganz gut, den Anfang des Artikels (den ersten Satz oder so) so zu formulieren, daß das nun neue Lemma „Entscheidbarkeit“ darin auch vorkommt / erklärt wird. Oder?
--H.Marxen (Diskussion) 20:51, 30. Jul. 2015 (CEST)

Genau, das sollte dann natürlich angepasst werden. --Andreschulz (Diskussion) 07:43, 31. Jul. 2015 (CEST)

Es hat sich in den acht Jahren nichts getan; ich werde dann mal einen SLA auf die Weiterleitung stellen (verschieben auf die Weiterleitung kann man ohne weiteres nicht, wenn es eine Versionsgeschichte dazu gibt), damit das Lemma gemäß der Substantivregel umbenannt werden kann. --Bildungskind (Diskussion) 14:52, 12. Feb. 2024 (CET)

Der Titel sollte "Entscheidungsproblem" lauten

Im angelsächsischen Sprachraum ist "Entscheidungsproblem" ein wichtiger Begriff, zu dem es mit David Hilbert, 1928, einen historischen Kontext gibt und der den Beginn der Informatik markiert. Das hier zu "Entscheidbar" umzuleiten halte ich für eine unzulässige Verkürzung. (nicht signierter Beitrag von West of House (Diskussion | Beiträge) 11:02, 9. Mai 2020 (CEST))

entscheidbar, semi entscheidbar

es müsste noch weiter differenziert werden, viele gelistete probleme werden als unentscheidbar betitelt sind aber in wirklichkeit semi entscheidbar - zB PCP oder Halteproblem. Ebsno Diagonal oderCFG-NonDisjointness. Es wäre schön wenn hier mal unterschieden würde zwischen nicht entscheidbar und semi entscheidbar. --134.147.24.10 13:58, 18. Jan. 2024 (CET)

Alle semi-entscheidbaren Probleme sind per Definition unentscheidbar, da sie nicht entscheidbar sind. Im Abschnitt Verwandte Begriffe steht bereits, dass das Halteproblem semi-entscheidbar ist. --Dexxor (Diskussion) 09:30, 20. Jan. 2024 (CET)