Die Mathe-Redaktion [Home] - Neues auf einen Blick 11.04.2021 02:12 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Berechenbare Funktion angeben		Druckversion
Druckversion		Antworten
Antworten
Autor
Universität/Hochschule Berechenbare Funktion angeben
GenericAlias
Neu Letzter Besuch: im letzten Monat
Dabei seit: 07.03.2021
Mitteilungen: 1
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-07


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🙂

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Informatik-Rentner
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 29.10.2015
Mitteilungen: 59
Herkunft: Essen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-11


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

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
GenericAlias hat die Antworten auf ihre/seine Frage gesehen.
GenericAlias wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]