Menge entscheidbar? < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:28 Di 11.01.2011 | | Autor: | Teufel |
| Aufgabe | [mm] L=\{n\in \IN | \text{es gibt einen Primzahlzwilling }(p-1, p+1)\text{ mit }p\ge n\}
[/mm]
Ist die Menge entscheidbar?
(es ist unbekannt, ob es unendlich viele Primzahlzwillinge gibt) |
Hi!
Hier habe ich 2 Ansätze.
1. Ansatz:
1. Annahme: Es gibt nur endlich viele Primzahlzwillinge.
Dann ist L auch endlich und L ist entscheidbar.
2. Annahme: Es gibt unendlich viele Primzahlzwillinge.
Dann ist [mm] L=\IN [/mm] und damit auch entscheidbar.
[mm] \Rightarrow [/mm] L ist entscheidbar.
2. Ansatz:
Wenn man, ohne vorher zu überlegen, z.B. eine Turingmaschine drauf ansetzt Primzahlzwillinge [mm] $\ge [/mm] n$ zu finden, dann wird sie auch welche finden, wenn man nur lange genug wartet. Oder aber sie gerät in eine Endlosschleife. Damit wäre L aber nur semi-entscheidbar.
Welcher Ansatz ist denn richtig?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:42 Di 11.01.2011 | | Autor: | felixf |
Moin!
> [mm]L=\{n\in \IN | \text{es gibt einen Primzahlzwilling }(p-1, p+1)\text{ mit }p\ge n\}[/mm]
>
> Ist die Menge entscheidbar?
> (es ist unbekannt, ob es unendlich viele Primzahlzwillinge
> gibt)
> Hi!
>
> Hier habe ich 2 Ansätze.
>
> 1. Ansatz:
> 1. Annahme: Es gibt nur endlich viele Primzahlzwillinge.
> Dann ist L auch endlich und L ist entscheidbar.
>
> 2. Annahme: Es gibt unendlich viele Primzahlzwillinge.
> Dann ist [mm]L=\IN[/mm] und damit auch entscheidbar.
>
> [mm]\Rightarrow[/mm] L ist entscheidbar.
>
>
> 2. Ansatz:
> Wenn man, ohne vorher zu überlegen, z.B. eine
> Turingmaschine drauf ansetzt Primzahlzwillinge [mm]\ge n[/mm] zu
> finden, dann wird sie auch welche finden, wenn man nur
> lange genug wartet. Oder aber sie gerät in eine
> Endlosschleife. Damit wäre L aber nur semi-entscheidbar.
>
>
> Welcher Ansatz ist denn richtig?
Na, beide. Wenn du annimmst, dass du weisst, ob es endlich oder unendlich viele Primzahlzwillinge gibt, dann ist $L$ entscheidbar.
Wenn du das nicht annimmst, kannst du nur sagen, dass es semi-entscheidbar ist. Ob $L$ dann auch entscheidbar ist, kannst du nicht sagen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:49 Di 11.01.2011 | | Autor: | Teufel |
Hi!
Danke erstmal.
Meinst du, ich sollte ich das auch dann genau so auf das Blatt schreiben?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:43 Di 11.01.2011 | | Autor: | felixf |
Moin!
> Danke erstmal.
> Meinst du, ich sollte ich das auch dann genau so auf das
> Blatt schreiben?
Du musst das schon etwas genauer aufschreiben. So wie es da steht ist es streng genommen falsch, also beim 1. Ansatz: die Folgerung bei [mm] $\Rightarrow$ [/mm] gilt nur dann, wenn auch eine der beiden Voraussetzungen gilt und als gültig bekannt ist! Der Algorithmus zur Entscheidung haengt ja davon ab, welche der beiden Voraussetzungen gerade gilt.
Wenn du das etwas besser aufschreibst, ist es aber in Ordnung.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:04 Di 11.01.2011 | | Autor: | Teufel |
Aber eigentlich muss doch eine von beiden Annahmen gelten, oder? Und beide Annahmen liefern, dass L entscheidbar ist. Das verwundert mich etwas.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:07 Di 11.01.2011 | | Autor: | felixf |
Moin!
> Aber eigentlich muss doch eine von beiden Annahmen gelten,
> oder? Und beide Annahmen liefern, dass L entscheidbar ist.
> Das verwundert mich etwas.
Klar, eine von ihnen gilt. Allerdings weisst du nicht, welche! Damit kannst du keinen Algorithmus angeben, der $L$ entscheidet.
Ah ok, ich sehe ein Problem. Es haengt davon ab, was genau man unter "entscheidbar" versteht. Wenn es nur einen Algorithmus geben muss -- man ihn aber nicht kennen muss -- dann ist die Sprache $L$ sehr wohl entscheidbar. Wenn man den Algorithmus aber auch kennen muss, dann ist die Sprache $L$ nach bisherigem Wissensstand nur semi-entscheidbar.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:35 Di 11.01.2011 | | Autor: | Teufel |
Hm, also wir haben nie erwähnt, dass man den Algorithmus kennen muss. Nur, dass einer existiert, bzw. eben eine Turingmaschine existiert, die [mm] \chi_L [/mm] berechnet. Aber man kommt ja dennoch wieder auf 2 Sachen, je nach dem, wie man das Problem betrachtet. Egal ob es endlich oder unendlich viele Zwillinge gibt: L ist in beiden Fällen entscheidbar. Aber geht man ohne diese Vorüberlegung ran und sagt, dass z.B. eine Turingmaschine M alle Zahlen [mm] \ge [/mm] n durchprobiert, dann kommt man darauf, dass M irgendwann anhält und sagt "n [mm] \in [/mm] L" oder aber M rechnet unendlich lang weiter. Ich weiß auch nicht, welche Sichtweise da erwartet wird. :s
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:24 Sa 15.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
