Turing-Reduktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen Sie mithilfe einer Turing-Reduktion, dass die Sprache Ap = {<M> : M entscheidet P} nicht rekursiv ist, wobei P = { x [mm] \in [/mm] {0,1}* : val(x) ist eine Primzahl} die Menge aller Primzahlen (in Binärkodierung) ist. |
Ja, ich muss gestehen, dass ich nicht weiß wie ich weiter komme. Mithilfe Turing-Reduktion bedeutet ich nehme an, es die genannte Sprache ist rekursiv, also existiert eine Turingmaschine (TM) M, die diese Sprache entscheidet. M soll dann wohl so modifiziert werden, dass dann auch eine andere Sprache, von der bekannt ist, dass sie nicht entscheidbar ist, entscheidbar wäre. Das ist dann der Widerspruch, komme aber nicht weiter....
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:20 Do 01.06.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
