Informatiker Board | Theoretische Informatik | Entscheidbarkeit von endlichen Mengen

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Entscheidbarkeit von endlichen Mengen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

Entscheidbarkeit von endlichen Mengen

Zitatantwort auf diesen Beitrag erstellen

Endliche Mengen sind ja entscheidbar. Da man bei gegebenen Element die Menge nach diesem Elmenet durchsucht. Man terminiert, da endlich. Aber was ist mit dieser Menge:
M={5| TM x hält bei Eingabe 5}
X sei dabei eine feste TM.
Was mache ich falsch?
PS:
Gibt es hier Latex-Hervorhebungen?
Funktioniert der erweiterte Editor auch mit openjdk? Der erweiterte Editor scheint nur bei oracle jdk zu funktionieren.

22.07.2013 19:14

Nehmen Sie margin in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

1. ich verstehe dein Problem noch nicht.
2. eine Latex-Hervorhebung gibt es. Einfach den Latex-Code in [_latex] [_/latex] einbetten (den Unterstrich weg lassen)
3. Ich habe den erweiterten Editor nie probiert, deshalb keine Ahnung.

VG,

Karlito

22.07.2013 23:15

Nehmen Sie Karlito in Ihre Freundesliste auf

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

Danke für deine Antwort,
Naja, die Menge
$[latex] $M=\{5 | \text{TM x hält bei Eingabe 5}\} $ [/latex]$
ist offensichtlich endlich, aber ist sie entscheidbar?

23.07.2013 11:06

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ja, warum nicht. Es ist doch leicht eine TM zu definieren, welche das Wort 5 akzeptiert. Die TM muss in dem Fall nur so konstruiert werden, dass sie bei der Eingabe 5 akzeptierend anhält, d.h. in einem definierten Finalzustand oder bei allen anderen Eingaben nicht akzeptierend.

VG,

Karlito

23.07.2013 11:21

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

Ne, die TM x soll fest sein, nicht variabel.. Stell dir vor, es wäre das Collatz Programm. Bei manchen Eingaben ist beim Collatz-Programm bis heut nicht feststellbar, ob es hält oder nicht.

23.07.2013 11:54

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Da ist die Frage wie "fest" definiert ist. Ich habe es so interpretiert, dass es sich nicht um eine universelle TM handelt, man aber X selbst definieren kann.
Handelt es sich nur im eine beliebige TM, bei der Du nicht weißt, um welche es sich handelt und es gilt festzustellen, ob die TM x anhält, so ist das Problem unentscheidbar.

Das liegt daran,. dass es sich um einen Spezialfall des Halteproblems handelt. Soweit ich mich erinnere kann man das mit dem Satz von Rice nachweisen.

Das Problem ist hier, dass die Menge der möglichen TM unendlich ist. Somit handelt es sich auch nicht mehr um ein Problem mit einer endlichen Menge, auch wenn die Eingabemenge endlich ist.

VG,

Karlito

23.07.2013 12:04

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

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.

23.07.2013 12:12

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

23.07.2013 14:37

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

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?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von margin: 23.07.2013 20:43.

23.07.2013 20:41

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

23.07.2013 20:58

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

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?

23.07.2013 21:50

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

24.07.2013 08:44

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

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.

24.07.2013 19:53

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

24.07.2013 22:20

margin
Jungspund

Dabei seit: 22.07.2013
Beiträge: 11

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.

04.10.2013 17:50

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

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