Diskussion:gödelisieren

Definition[Bearbeiten]

Letzter Kommentar: vor 7 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

In der Wikipedia werden weitere Bedingungen genannt (Abzählbarkeit der Wörter, Berechenbarkeit etc.):

„Sei $M$ die (abzählbare) Menge der Wörter einer formalen Sprache. Eine Funktion

g\colon M\to \mathbb {N}

wird Gödelisierung genannt, wenn^[1]

$g$ injektiv und berechenbar,
die Bildmenge $g(M)$ entscheidbar sowie
die auf $g(M)$ definierte Umkehrfunktion von $g$ berechenbar ist.

$g(m)$ nennt man dann die Gödelnummer von $m$ .“

↑ Hans Hermes: Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit, 2. Auflage. Springer, Berlin 1971; S. 4, ISBN 3-540-05334-4, ISBN 0-387-05334-4.

Zumindest die Injektivität würde ich erwähnen („injektiv zuordnen“? (nur ein Scherz:) „injizieren“?), dafür vielleicht „natürliche Zahlen“ durch „Nummern“ (oder im distributiven Singular „eine Nummer“) ersetzen, denn (en-WP): „Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as Turing machines that manipulate strings rather than numbers.“ -- IvanP (Diskussion) 20:18, 7. Jan. 2017 (MEZ)Beantworten

Ach so, da es eine Funktion sein soll: „Wörter einer formalen Sprache auf Nummern (insbesondere: natürliche Zahlen) injektiv abbilden“ -- IvanP (Diskussion) 20:23, 7. Jan. 2017 (MEZ)Beantworten

@Ivan: Nur zu! --Peter -- 21:57, 8. Jan. 2017 (MEZ)Beantworten

[1] Hans Hermes: Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit, 2. Auflage. Springer, Berlin 1971; S. 4, ISBN 3-540-05334-4, ISBN 0-387-05334-4.

[1]