Hilberts 10tes Problem unent. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:34 Di 15.12.2015 | | Autor: | duduknow |
Hi,
für ein multivariates Problem $p$ mit ganzzahligen Koeffizienten ist es unentscheidbar, ob es $x [mm] \in \mathbb{Z}^n$ [/mm] gibt mit $p(x) = 0$.
Ich verstehe nicht, wieso das ein unentscheidbares Problem ist. [mm] $\mathbb{Z}^n$ [/mm] ist abzählbar: Was hindert mich daran, für ein gegebenes Polynom alle Vektoren durchzuprobieren? Wenn das Polynom eine ganzzahlige Nullstelle hat, terminiert das Durchprobieren irgendwann, andernfalls nie. Dann wäre das aber ein semientscheidbares Problem.
Wieso klappt das also nicht?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:24 Mi 16.12.2015 | | Autor: | felixf |
Moin!
> für ein multivariates Problem [mm]p[/mm] mit ganzzahligen
> Koeffizienten ist es unentscheidbar, ob es [mm]x \in \mathbb{Z}^n[/mm]
> gibt mit [mm]p(x) = 0[/mm].
>
> Ich verstehe nicht, wieso das ein unentscheidbares Problem
> ist. [mm]\mathbb{Z}^n[/mm] ist abzählbar: Was hindert mich daran,
> für ein gegebenes Polynom alle Vektoren durchzuprobieren?
> Wenn das Polynom eine ganzzahlige Nullstelle hat,
> terminiert das Durchprobieren irgendwann, andernfalls nie.
> Dann wäre das aber ein semientscheidbares Problem.
Ein semientscheidbares Problem kann auch unentscheidbar sein. Unentscheidbar heisst, dass es nicht entscheidbar ist.
Beim Halteproblem kannst du ein Programm ja auch so lange laufen lassen, bis es terminiert (die Anzahl Programmschritte, die das Programm durchläuft, ist ebenfalls abzählbar) und somit ist das Halteproblem semientscheidbar. Es ist trotzdem auch unentscheidbar. (Siehe auch ![[]](/images/popup.gif) erstes Beispiel hier.)
LG Felix
|
|
|
|
