Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beispiel einer aufzählbaren aber nicht entscheidbaren Menge
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Beispiel einer aufzählbaren aber nicht entscheidbaren Menge
 
Autor Nachricht
Urza
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 18.12.2007
Beiträge: 2

BeitragVerfasst am: 18 Dez 2007 - 01:08:34    Titel: Beispiel einer aufzählbaren aber nicht entscheidbaren Menge

Hallo,

Sei A ein endliches Alphabet (Menge von Zeichen) und A* die Menge der Zeichenketten aus Zeichen in A.
Ich suche für irgendein konkretes A (z.B. A={'1'}, A*=IN sozusagen) eine Teilmenge M von A, sodass M aufzählbar, aber nicht entscheidbar ist.
D.h. es soll einen Algorithmus geben, der nacheinander alle Elemente von M aufzählt, aber es soll keinen Algorithmus geben, der als Eingabe ein beliebiges Element von A* nimmt und als Ausgabe "ja" oder "nein" liefert, je nach dem, ob die Eingabezeichenkette in M liegt oder nicht (und der immer nach endlicher Zeit fertig wird).
Ich bin mir im Moment garnicht sicher, ob es sowas überhaupt geben kann (für mich ist das Gebiet "Berechenbarkeitstheorie" Neuland!)

Gruß,
Urza
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 18 Dez 2007 - 01:46:30    Titel:

Hallo!

Standard-Beispiel ist das Halteproblem, welches offensichtlich semi-entscheidbar (d.h. aufzählbar) ist, aber es ist nicht entscheidbar.

Cyrix
Masor
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 16.07.2006
Beiträge: 256

BeitragVerfasst am: 18 Dez 2007 - 01:53:37    Titel:

Oder auch die Menge der Tautologien/unerfüllbaren Formeln in der Prädikatenlogik.
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 18 Dez 2007 - 02:02:32    Titel:

Masor hat folgendes geschrieben:
Oder auch die Menge der Tautologien/unerfüllbaren Formeln in der Prädikatenlogik.


Na, aufpassen. Soweit ich weiß, ist die Prädikatenlogik erster Stufe vollständig und konsistent, d.h. genau für jede wahre Aussage existiert ein Beweis, der diese zeigt. "Wahr" bedueutet hier, dass sie in allen Modellen wahr ist. Insbesondere werden alle noch freien Variablen einer Formel mit "für alle Quantoren" gebunden. (Gödelscher Vollständigkeitssatz).

Da für jede Aussage sie, oder ihre Negation wahr ist, und ein Beweis nur eine endliche Zeichenkette über einem endlichen Alphabet ist, kann man so nach endlicher Zeit entscheiden, ob eine Aussage A wahr, oder falsch ist (man geht einfach nacheinander nach einem Abzählverfahren "alle" möglichen Zeichenketten über dem Alphabet, in welchem die Beweise geschrieben sind, durch, prüft für jede Zeichenkette, ob sie ein Beweis ist (geht leicht, da es dafür leicht nachprüfbare Regeln gibt), und schaut dann jeweils, ob es ein Beweis für A oder für nicht(A) ist. Ist es eins von beiden, ist man fertig, ist es keines, so macht man mit der nächsten Zeichenkette weiter...


Cyrix
Masor
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 16.07.2006
Beiträge: 256

BeitragVerfasst am: 18 Dez 2007 - 02:31:10    Titel:

Also nach meinen Büchern ist die Prädikatenlogik 1. Stufe, oder genauer gesagt, sowohl das Erfüllbarkeitsproblem als auch das Gültigkeitsproblem für prädikatenlogische Formeln unentscheidbar.

Nur die Unerfüllbarkeit (und darüber natürlich auch die Tautologien) sind semi-entscheidbar.
Urza
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 18.12.2007
Beiträge: 2

BeitragVerfasst am: 18 Dez 2007 - 03:58:02    Titel:

Dies ist ein langer Post, aber ich habe versucht, alles möglichst übersichtlich hinzuschreiben und wäre dankbar, wenn mir jemand helfen könnte, mir wäre auch schon ein Verweis auf ein gutes Buch hilfreich.

cyrix, meinst du das mit dem Halteproblem jetzt folgendermaßen :
A:= Menge aller Zeichen, die für die Beschreibung von Algorithmen und Eingabezeichenketten benötigt werden (endlich viele Zeichen) plus ein Trennungszeichen.
M:= Diejenige Teilmenge von A*, in der genau ein Trennungszeichen vorkommt und wo der Text vor dem Trennungszeichen einen Algorithmus kodiert (mit genau einer Zeichenkettenvariable als Eingabe) und der Text nach dem Trennungszeichen eine beliebige Zeichenkette ist.
Jetzt A:=Menge aller Elemente von M, wo der zugehörige Algorithmus hält.

Jetzt die Behauptung : A ist semi-entscheidbar, aber nicht entscheidbar.

(Das ist die Weise, wie ich das Halteproblem auf die gegebene Situation übertragen würde, aber ich bin mir nicht sicher, ob du das damit meintest.)

Um jetzt zu zeigen, dass A semi-entscheidbar ist, ist die Idee, wie ich gelesen habe, dass man einen Algorithmus schreibt, der zuerst prüft ob eine gegebene Zeichenkette ein Algorithmus ist [bzw. der erste Teil davon] (ist das entscheidbar?) und dann, falls es ein Algorithmus ist, diesen mit der eigenen Eingabe ausführt und dann am Ende "ja" ausgibt.
Falls der erste Teil der Eingabezeichenkette ein Algorithmus ist, der mit der Eingabezeichenkette terminiert, dann gelangt auch dieser Algorithmus zu der Stelle, wo "ja" ausgegeben wird.

Soweit alles klar, nur stellen sich mir zwei Fragen:
1. Gibt es wirklich einen Entscheidungsalgorithmus für die Frage, ob eine gegebene Zeichenkette ein Algorithmus ist? Kann man das vielleicht darüber lösen, dass man den Begriff "kodierter Algorithmus" über gewisse Grammatiken definiert und dann zeigt, dass Sprachen, die von solchen Grammatiken erzeugt werden, immer in dem Sinne entscheidbar sind?
2. Gibt es wirklich einen Algorithmus, der eine Zeichenkette als Eingabe nimmt und sie als Algorithmus ausführt (1. vorausgesetzt) ?

Das Problem (Scheinproblem?) zu 2. was ich sehe, ist nämlich das:
Man muss doch in der Kodierung eines Algorithmus irgendwie zwischen Variablenbezeichnungen (z.B. der Variable "eingabe") und Zeichenketten (z.B. der Zeichenkette "eingabe") unterscheiden.
D.h. für die Beschreibung eines Algorithmus müssen Zeichen zugelassen sein, die nicht für Eingabe- oder Ausgabezeichenketten (oder sonstige im Algorithmus benutzen Zeichenketten) zugelassen sind (z.B. Hochkommata).
Wenn ich jetzt aber einem Algorithmus eine Beschreibung eines (beliebigen) Algorithmus als Eingabe geben möchte, dann habe ich folglich ein Problem, oder?
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Beispiel einer aufzählbaren aber nicht entscheidbaren Menge
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum