Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Entscheidbare Teilmengen

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Entscheidbare Teilmengen » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

chillerstudent

Entscheidbare Teilmengen

Meine Frage:
Hallo,

meine Aufgabe lautet:

Seien M1 und M2 beliebige entscheidbare Teilmengen der natürlichen Zahlen. Zeigen Sie die Gültigkeit der folgenden Behauptungen:

a) M1 U M2 ist entscheidbar.

b) M1 $[latex]\cap [/latex]$ M2 ist entscheidbar.

c) M1 \ M2 ist entscheidbar.

Meine Ideen:
Erstmal allgemein:
Eine Menge ist dann entscheidbar, wenn das charakteristische Polynom berechenbar ist.

Ich weiß leider nicht wie ich die Gültigkeit beweisen soll. Vielleicht mit dem charakteristischen Polynom?