gödelnummer < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:54 Sa 09.12.2006 | | Autor: | AriR |
hey leute
wir haben PRI und PI wie folt definiert
PRI ist die menge aller gödelnummer primitiv rekursiver funktionen
PI ist die menge aller gödelnummer partiell rekursiver funktionen
gilt dann nicht
[mm] PRI\subset PI\subset \IN
[/mm]
aber [mm] PRI\not=PI\not=\IN
[/mm]
oder?
|
|
| |
|
Hallo,
es gilt dann sicherlich die erste Inklusionskette, aber bei der zweiten gilt nur die erste Striktheit immer,
ob [mm] PI\subsetneq \IN [/mm] oder [mm] PI=\IN [/mm] gilt, hängt von der Wahl der Gödelisierung ab.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:50 Do 14.12.2006 | | Autor: | AriR |
danke schonmal für die antwort.
da man eine bijektion zwischen den rekursiven funktionstermen und PI hat, gibt es doch genau so viele rekursive funktionsterme, wie die mächtigkeit der menge PI oder?
wäre [mm] PI=\IN [/mm] oder auch [mm] PI\subset\IN [/mm] gäbe es also abzählbar viele rekursive funktionsterme oder?
und wenn man die menge der gödelnummer hat, da gibts doch immer genau so viele von, wie es rekursive funktionsterme gibt, müsste dann nicht jede form der gödelisierung zu einer gleichen mächtigkeit von PI führen, egal wie man das definiert, da jeder rekursive funktionsterm genau eine gödelnummer zugewiesen bekommt?
Gruß ari :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Fr 22.12.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
