Semi-Entscheidbarkeit < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:42 So 04.07.2010 | | Autor: | Lovelace |
| Aufgabe | Sei A die Menge der Zahlen, die sich als Differenz aus zwei
Primzahlen darstellen lassen, es gilt also
A = {x | es existieren Primzahlen p1 > p2 mit x = p1 − p2}.
Zeigen oder widerlegen Sie, dass A semi-entscheidbar ist. |
Hallo!
Also, nach der Definition, die mir vorliegt, ist eine Sprache dann als semi-entscheidbar zu bezeichnen, falls es eine deterministische Turingmaschine gibt, die A akzeptiert, d.h. L(M) = A.
Wenn also x ∈ A, dann stoppt die Maschine in endlich vielen Schritten, sonst läuft sie einfach weiter und man weiß nicht, ob sie irgendwann noch den Endzustand erreicht.
Heißt das, ich muss für die Lösung eine Turingmaschine konstruieren, welche die Differenz aus zwei Primzahlen errechnet?! Wie könnte denn sowas aussehen?! Hat mir da vielleicht jemand einen Tipp???
Liebe Grüße,
Lovelace
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:58 So 04.07.2010 | | Autor: | felixf |
Moin (Ada?) Lovelace,
und:
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Sei A die Menge der Zahlen, die sich als Differenz aus
> zwei
> Primzahlen darstellen lassen, es gilt also
> A = {x | es existieren Primzahlen p1 > p2 mit x = p1 −
> p2}.
>
> Zeigen oder widerlegen Sie, dass A semi-entscheidbar ist.
> Hallo!
>
> Also, nach der Definition, die mir vorliegt, ist eine
> Sprache dann als semi-entscheidbar zu bezeichnen, falls es
> eine deterministische Turingmaschine gibt, die A
> akzeptiert, d.h. L(M) = A.
>
> Wenn also x ∈ A, dann stoppt die Maschine in endlich
> vielen Schritten, sonst läuft sie einfach weiter und man
> weiß nicht, ob sie irgendwann noch den Endzustand
> erreicht.
>
> Heißt das, ich muss für die Lösung eine Turingmaschine
> konstruieren, welche die Differenz aus zwei Primzahlen
> errechnet?! Wie könnte denn sowas aussehen?! Hat mir da
> vielleicht jemand einen Tipp???
Du musst begruenden, dass es eine Turingmaschine gibt, welche alle Paare $(x + t, t)$ mit $t [mm] \in \IN$ [/mm] durchgeht und schaut ob sowohl $x + t$ wie auch $t$ Primzahlen sind. Ist dies der Fall, bricht sie ab und akzeptiert $x$. Andernfalls wird halt weitergesucht...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:48 So 04.07.2010 | | Autor: | Lovelace |
Hallo felixf und alle anderen, die dies vllt lesen!
Und erstmal danke für den herzlichen Empfang 
Zurück zu meiner Aufgabe: Um zu begründen, dass es eine Turingmaschine dieser Art geben muss müsste es ja ausreichen, wenn ich ein GOTO oder ein WHILE- Programm angebe, dass diesen Test leistet, da ja jedes Goto- und jedes While-Programm auch Turing-berechenbar ist, oder? Bin ich da auf dem richtigen Weg?
Ich habe mir das jetzt nochmal genauer überlegt und im Prinzip finde ich meinen Plan auch ganz gut=)
Dass die Funktion f(m,n) = m div n WHILE-berechenbar ist haben wir bereits in der Vorlesung bewiesen, jetzt müsste ich ja nur bei n=2 beginnen und hochwandern bis m/2, oder?! falls das ergebnis dann Element der natürlichen Zahlen ist, ist m keine Primzahl, falls nicht, geht es weiter mit n+1 ...
Im Endeffekt wäre eine solche Funktion/ Turingmaschine ja dann aber auch in endlichen Schritten fertig, d.h. das Problem ist definitiv entscheidbar, oder?! Wobei entscheidbare Funktionen ja auch immer semi-entscheidbar sind...
Ich bin für alle Tipps/ Hinweise dankbar,
viele Grüße,
(Ada) Lovelace
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:50 Mo 05.07.2010 | | Autor: | felixf |
Moin Ada,
> Zurück zu meiner Aufgabe: Um zu begründen, dass es eine
> Turingmaschine dieser Art geben muss müsste es ja
> ausreichen, wenn ich ein GOTO oder ein WHILE- Programm
> angebe, dass diesen Test leistet, da ja jedes Goto- und
> jedes While-Programm auch Turing-berechenbar ist, oder? Bin
> ich da auf dem richtigen Weg?
ja, so kannst du das machen.
> Ich habe mir das jetzt nochmal genauer überlegt und im
> Prinzip finde ich meinen Plan auch ganz gut=)
>
> Dass die Funktion f(m,n) = m div n WHILE-berechenbar ist
> haben wir bereits in der Vorlesung bewiesen, jetzt müsste
> ich ja nur bei n=2 beginnen und hochwandern bis m/2,
> oder?! falls das ergebnis dann Element der natürlichen
> Zahlen ist, ist m keine Primzahl, falls nicht, geht es
> weiter mit n+1 ...
Ja. Allerdings liefert $f(m, n)$ immer eine ganze Zahl zurueck, du muesstest Modulo-Rechnen und gucken ob der Rest 0 ist. Mit Hilfe von $f(m, n)$, Multiplikation und Subtraktion kannst du jedoch ein Modulo basteln: m MOD n = m - (m DIV n) * n
> Im Endeffekt wäre eine solche Funktion/ Turingmaschine ja
> dann aber auch in endlichen Schritten fertig, d.h. das
> Problem ist definitiv entscheidbar, oder?!
Nein: es ist entscheidbar, ob $(x + t, t)$ eine Loesung fuer $x$ ist (d.h. ob $x + t$ und $t$ Primzahlen sind); jedoch es ist nur semientscheidbar, ob $x$ in $A$ liegt, da du dieses Testen auf Loesung wenn du Pech hast fuer alle $t [mm] \in \IN$ [/mm] machen musst.
Du hast also zwei verschachtelte WHILE-Schleifen.
LG Felix
|
|
|
|
