Frage zu Gödelnummern

Dr. Jekyll

Graue Eminenz

Posts: 439

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: Lohnsklave

1

Wednesday, March 22nd 2006, 3:21pm

Moin! Hier eine Frage an die Experten:

Ist die Abbildung von einer TM auf eine Gödelnummer bijektiv? Einer TM ist eine eindeutige Gödelnummer zugeordnet, das ist klar. Aber gilt das auch umgekehrt? Sprich, können (oder müssen sogar) zwei TM, die zwar dieselbe Funktion berechnen, aber einen unterschiedlichen Aufbau haben, die gleiche Gödelnummer haben?

Wenn ich nun von einer Funktion ausgehe mit der Gödelnummer x kann es ja mehrere (sogar unendlich viele) TMs geben, die diese Funktion berechnen. Haben die alle dann die gleiche Gödelnummer wie die Funktion?
Oder ist jeder TM eine Gödelnummer zugeordnet, und ein und dieselbe Funktion hat dann mehrere Gödelnummern, je nachdem welche konkrete TM man gerade betrachtet, die diese Funktion berechnet...

Total vergödelt:
Doc.

Wer in einem gewissen Alter nicht merkt, daß er hauptsächlich von Idioten umgeben ist, merkt es aus einem gewissen Grunde nicht. [Curt Goetz]

This post has been edited 1 times, last edit by "Dr. Jekyll" (Mar 22nd 2006, 3:21pm)

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Wednesday, March 22nd 2006, 4:16pm

RE: Frage zu Gödelnummern

Quoted

Original von Dr. Jekyll
Ist die Abbildung von einer TM auf eine Gödelnummer bijektiv? Einer TM ist eine eindeutige Gödelnummer zugeordnet, das ist klar. Aber gilt das auch umgekehrt? Sprich, können (oder müssen sogar) zwei TM, die zwar dieselbe Funktion berechnen, aber einen unterschiedlichen Aufbau haben, die gleiche Gödelnummer haben?

Die Abbildung ist bijektiv. Jede Turingmaschine (beschrieben durch das übliche Tupel) wird auf eine Gödelnummer abgebildet. Welche Funktion eine Maschine berechnet, ist für die Abbildung nicht von Bedeutung.

Also:
Verschiedene TMs, aber gleiche berechnete Funktion -> verschiedene Gödelnummern
Identische TMs (also im Grunde nur eine, eventuell abgesehen von Umbenennung von Zuständen etc., das wäre dann Definitionssache) -> identische Gödelnummern

Mit dieser Einsicht wird vermutlich auch der Satz von Rice klarer: Wählt man dort eine Menge von Funktionen, die aus genau einer Funktion besteht, so ist es unentscheidbar, ob eine gegebene TM (eindeutig kodiert durch ihre Gödelnummer) diese Funktion berechnet. Die zu entscheidende Sprache ist in diesem Fall also die Menge aller Gödelnummern, deren zugehörige TMs diese Funktion berechnen. Diese Menge ist nicht nur unendlich (da jede TM so erweitert werden kann, daß sie trotzdem noch dieselbe Funktion berechnet; das hast Du ja bereits geschrieben), sonder schlimmer noch: nach dem Satz von Rice unentscheidbar.

Quoted

Total vergödelt:
Doc.

Jetzt wieder entgödelt?

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

This post has been edited 4 times, last edit by "Joachim" (Mar 22nd 2006, 4:19pm)

Go to the top of the page