funktionale Reduktion in welche richtung?

 - (Informatik, Reduktion, mengenlehre)

1 Antwort

M1 ist also die Menge der Turingmaschinen, die angewendet auf ihre eigene Repräsentation als Gödelnummer sich selbst zurückliefern?

Ich würde das mittels Reduktion des initialen Halteproblems auf M1 lösen.

Es existiert definitiv eine Funktion s mit TM Ms, die in M1 liegt.(Beispielsweise die identitätsfunktion).

Wir wählen als Reduktionsfunktion:

f(x) = Wenn(x Gödelnummer einer det. 1-Band-TM; <Feste Maschine(x)>; 0);

(<> heißt hier, dass es sich um die Gödelnummer der TM in den Klammern handelt).

Wobei Feste Machine(x) eine det. 1-Band-TM mit folgendem Algorithmus sei:

1.) Die Eingabe sei y;

2.) Starte x mit leerem Band

3.) Starte Ms mit y

Die Feste Maschine(x) berechnet dabei dasselbe wie Ms, wenn x im initialen Halteproblem, liefert also auch die Identität und liegt somit in M1.

Was möchtest Du wissen?