Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Satz von Rice und rekursive Aufzählbarkeit
Druckversion
Druckversion
Autor
Universität/Hochschule J Satz von Rice und rekursive Aufzählbarkeit
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-03-28


Guten Tag, ich wollte wissen ob meine Grundidee zu folgenden Aufgaben richtig ist.


 
Laut des Satzes von Rice sind beide Sprachen nicht rekursiv, da es sich um nicht-triviale Eigenschaften von Turingmaschinen handelt.
\(M_1\) = {\(w\)| gibt bei jeder Eingabe \( w \in \{0,1\}^*\) bin\((42)\) aus}
\(M_2\) = {\(w\)| gibt bei jeder Eingabe \( w \in \{0,1\}^*\) bin\((0)\) aus}

\(H'_{42}\) ist rekursiv aufzählbar da man Eingaben \(<M>\) auf \(\epsilon\) starten und akzeptieren kann wenn die Ausgabe 42 ist.

\(\overline{H'_{42}}\) ist nicht rekursiv aufzählbar, da rekursive Aufzählbarkeit nicht gegen Komplementbildung abgeschlossen ist und diese bedeuten würde das \(H'_{42}\) rekursiv wäre.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 248
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-03-29


2021-03-28 14:31 - Chrispyk im Themenstart schreibt:
Guten Tag, ich wollte wissen ob meine Grundidee zu folgenden Aufgaben richtig ist.

Die Beweise sind OK.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 01.09.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-03-31


Danke



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Chrispyk hat die Antworten auf ihre/seine Frage gesehen.
Chrispyk hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  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]