Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Entscheidbare Teilmengen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

chillerstudent
Grünschnabel

Dabei seit: 24.05.2011
Beiträge: 4

Entscheidbare Teilmengen

Zitatantwort auf diesen Beitrag erstellen

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?

24.05.2011 22:43

Nehmen Sie chillerstudent in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

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