Forum:  Berechenbarkeitstheorie
Thema: Berechenbare Funktion angeben
Themen-Übersicht
GenericAlias
Neu
Dabei seit: 07.03.2021
Mitteilungen: 1
Themenstart: 2021-03-07 09:01

Ich möchte mich mit folgender Aufgabe auf die Prüfung vorbereiten, Punkte bekomme ich dafür also nicht mehr.

Geben Sie berechenbare Funkionen an, die folgende Eigenschaften haben

1) Def(f1) nicht entscheidbar und Bild (f1) entscheidbar
2) Def(f2) entscheidbar und Bild (f2) unentscheidbar

Es gibt noch zwei weitere Teilaufgaben, aber die will ich hiernach erstmal selber lösen.

Bild ist ja verkürzt gesagt, der Wertebereich einer Funktion also alle y-Werte die die Funktion annehmen kann.
Definionsbereich demnach alle x-Werte für die die Funktion definiert ist.

Bei 1) hatte ich die Funktion
f(x)= a falls fed-Code einblenden
fed-Code einblenden fed-Code einblenden

Dann wäre Bild(f1)= {a} und damit Bild(f) berechenbar.
Das x kann ja nicht entscheidbar sein, da das Halteproblem nicht entscheidbar ist. Aber die Aufgabe habe ich wohl falsch gelöst, denn als Anmerkung habe ich nur "Berechenbar?" bekommen. Müsste ich jetzt eine TM bauen wo ich zeige das f berechenbar ist. Oder wie kann man die Aufgaben lösen?

Die anderen Teilaufgaben habe ich nach dem gleichen Schema gelöst, wenn etwas nicht entscheidbar ist dann den Output bzw. Input als Halteproblem festlegen.

Für Hilfe wäre ich sehr dankbar🙂


Informatik-Rentner
Aktiv
Dabei seit: 29.10.2015
Mitteilungen: 62
Wohnort: Essen
Beitrag No.1, eingetragen 2021-03-11 17:49

Aus meiner Sicht kann das Problem x für eine konkrete Eingabe y schon entscheidbar sein. Das Halteproblem oder pkp ist generell nicht entscheidbar, aber konkrete Probleme können schon entscheidbar sein. ZB. die kontextsensitiven Sprachen. Wenn sich irgendwann die Konfiguration/Bandinhalt auf der bandbeschränkten TM wiederholt, weiß man, dass die TM nicht anhält, weil sie in einer Endlosschleife läuft




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=252717=510002
Druckdatum: 2021-05-15 21:54