Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 4, Totalitäts- und Endlichkeitsproblem
Hallo allerseits,
Ich hocke (mit meiner Gruppe) ewig an dieser aufgabe und bis jetzt fällt uns kein gescheiter ansatz ein.
Wie sollen wir an die aufgabe rangehen?
Einzig und allein wissen wir dass wir das halteproblem darauf reduzieren müssen. ABER wie genau und was vorallem? Totalität bedeutet ja dass für jede eingabe es anhält. Müssen wir nun annehmen, dass es eine TM M’ gibt, die für alle eingaben hält. Und dann???
Entschuldigung, dass es evtl so blöd rüberkommt, aber wir verzweifeln an bfs…
Danke schonmals
Hallo
Bei dieser Aufgabe kann man sich recht gut an der Präsenzaufgabe 13 orientieren. Dort wurde auch die Unentscheidbarkeit einer Sprache gezeigt. Überlegt euch an dieser Schritt für Schritt, wie das dort gemacht wurde. Dann sollte es klarer werden, wie man bei dieser Aufgabe vorgehen muss.
Die Aufgabe 19 ging ja schon wie die Präsenzaufgabe 13.
Das kann doch nicht sein, dass man für die 19 und 20, 90% der Präsenzaufgabe übernehmen kann und nur ein bisschen anpassen muss…
Oder doch?