Informatiker Board | Theoretische Informatik | Entscheidbarkeit von endlichen Mengen

Informatiker Board » Themengebiete » Theoretische Informatik » Entscheidbarkeit von endlichen Mengen » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge

Karlito

Danke für die Rückmeldung.

Irgendwie will mir das noch nicht in den Kopf. Ich mach mich noch mal schlau. Vielleicht muss ich für mich den Begriff der Berechenbarkeit überarbeiten,

VG,

Karlito

margin

Entschuldige die lange Pause. Ich habe mich noch mal ausgiebigst bei meinem Mentor erkundigt.

Also $[latex]M=\{5 \in M \Longleftrightarrow [/latex]$ TM x hält bei Eingabe 5 $[latex] \}[/latex]$ kann man umformulieren in:

$[latex] y \in M [/latex]$ gdw. TM x hält bei Eingabe y und y = 5. Wir definieren die charakteristische Funktion von c_M(y) für M wie folgt:
[latex]c_M(y)=1[/latex]

, falls TM x bei Eingabe y und y=5 hält. Sonst [latex]c_M(y)=0, sonst[/latex]

.
Es können zwei Fälle können eintreten:
1.) TM x hält bei eingabe 5
2.) TM x hält nicht bei Eingabe 5

1.) [latex]c_M(y)=1[/latex]

, falls y=5
[latex]c_M(y)=0[/latex]

, sonst

2.)
[latex] c_M(y)=0[/latex]

für alle y

c_M ist in allen beiden Fällen berechenbar, entweder ist $[latex]M=\{5\}[/latex]$ oder $[latex]M=\{\}[/latex]$ . Somit ist M entscheidbar.

Karlito

Sorry, dass ich dich so verwirrt habe, aber M ist schon endlich. Aber das zu untersuchende Problem basiert doch auf der Menge aller Turingmaschinen.

VG,

Karlito

margin

Zitat:

Original von Karlito
Wir haben die selbe Auffassung des Begriffs unendlich. Ich glaube wir haben nur aneinander vorbei geredet. Und dass es unendlich viele TM gibt, da sind wir uns doch einig, oder?

VG,

Karlito

Ja, sind wir. Trotzdem verwirrt mich das ganze ein bisschen. Also weil meine Menge M von einer unendlichen Menge abhängt, ist meine Menge M auch unendlich, obwohl keine TM Element meiner Menge M ist, oder?
Vielen Dank für deine Geduld.

Karlito

Zitat:

Original von margin
Nur das die Menge aller Turingmaschinen eben nicht M selber ist, sondern die Menge des Eingabewortes oder halt leer.

Ja, das hängt aber von den zugrundeliegenden TM ab. Mit deiner Argumentation wäre sonst auch das Halteproblem lösbar, da die Ausgabemenge endlich ist (hält, hält nicht).

Zitat:

Original von margin
Wir haben anscheinend unterschiedliche Vorstellungen von Unendlichkeit einer Menge. Für mich ist eine Menge M unendlich, falls sie unendlich viele Elemente besitzt:
$[latex] $|M|=\infty$[/latex]$
und endlich, falls:
$[latex]$|M|=n \quad n \in \mathbb{N}$[/latex]$
Meine Menge M ist doch endlich, da sie entweder das Element 5 oder kein Element besitzt.
Kannst du mir folgen?

Wir haben die selbe Auffassung des Begriffs unendlich. Ich glaube wir haben nur aneinander vorbei geredet. Und dass es unendlich viele TM gibt, da sind wir uns doch einig, oder?

VG,

Karlito

margin

Zitat:

Original von Karlito
Da du das nicht weißt, führst du den Beweis ja für eine beliebige Turingmaschine x aus der Menge der Turingmaschinen. Also faktisch für alle Turingmaschinen.

Nur das die Menge aller Turingmaschinen eben nicht M selber ist, sondern die Menge des Eingabewortes oder halt leer.
Wir haben anscheinend unterschiedliche Vorstellungen von Unendlichkeit einer Menge. Für mich ist eine Menge M unendlich, falls sie unendlich viele Elemente besitzt:
$[latex] $|M|=\infty$[/latex]$
und endlich, falls:
$[latex]$|M|=n \quad n \in \mathbb{N}$[/latex]$
Meine Menge M ist doch endlich, da sie entweder das Element 5 oder kein Element besitzt.
Kannst du mir folgen?

Karlito

Hallo,

ich verstehe deine Argumentation nicht. Ich denke aber auch immernoch, dass du mit der Annahme, dass es sich im eine endliche Menge handelt auch falsch liegst. Nur deine Eingabe ist endlch. Deine TM ist ein Element der Menge aller Turingmaschinen. Auch wenn Du mir ein einziges fixes x betrachtest, ist dir nicht bekannt um welches x es sich handelt! Da du das nicht weißt, führst du den Beweis ja für eine beliebige Turingmaschine x aus der Menge der Turingmaschinen. Also faktisch für alle Turingmaschinen.

Übersehe ich etwas in meiner Argumentation?

Gruß,

Karlito

margin

Ich merke gerade selber, dass ich eigentlich das spezielle Halteproblem auf mein Problem reduziert habe.
$[latex]$ K \le M \quad K \text{ ... spezielles Halteproblem} $[/latex]$ .
Rein faktisch ist ja die Menge M endlich, aber ich kann es nicht nachweisen, da die Prämisse unentscheidbar ist. Man kann also nicht sagen, ob $[latex] $M=\{\} \vee M=\{5\}$ [/latex]$
Ist diese Argumentation richtig?

Karlito

Hallo,

mh, ja, ich verstehe das Problem. Trotzdem handelt es sich um ein spezielles Halteproblem, da es ein beliebiges, wenn auch festes Element aus der Menge aller Turinmaschinen geht. Und dieses Problem ist im allgemeinen nicht Lösbar. Man kann nicht entscheiden, ob eine beliebige TM x für die Eingabe 5 anhält.

Klar?

VG,

Karlito

margin

Nein, es handelt sich um eine fest vorgebene TM. Stell dir vor, du bekommst ein Code-ausschnitt zu sehen. Und man würde dich Fragen, ob dieses Programm bein Eingabe 5 hält. Damit ist die Eingabe und die Menge der TM endlich, da du nur konkret eine TM vorgegeben bekommst.

Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.