Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
2 TheoInf Fragen
Kann mir jemand das Grundschema sagen, wie man von einer Funktion nachweist, dass sie primitiv-rekursiv ist? Ich blicke die Beweise aus der Uebung leider nicht.
Und kann mir noch jemand sagen, wann eine Turing-Maschine etwas als korrekte Eingabe erkannt hat? Muss der Schreib-Lesekopf am Ende des Bandes ankommen, oder muss das Band geloescht sein?
Sorry fuer die Anfaenger-Fragen :red:
Die Klasse der primitiv rekursiven Funktionen ist identisch mit der Klasse der Loop berechenbaren Funktionen. Lässt sich eine Funktion als Loop Programm schreiben, so ist sie automatisch auch primitiv rekursiv. Alternativ kann man auch zeigen, dass Funktionen die auf trivialen Funktionen beruhen ebenfalls primitiv rekursiv sind. Zum Beispiel kann man die Multiplikation durch mehrfache Anwendung der Addition darstellen. Addition wiederum als mehrfache Ausführung der Nachfolgefunktion. Die Nachfolgefunktion ist lt Def prim.rek. Das ganze steht aber auch so im schöning.
Turing Maschinen akzeptieren im allegemeinen nicht nur sachen sondern rechnen irgendwas. Wann das Ding in den Fertig Zustand übergeht ist an sich Festlegungssache. Wenn du das Ding als Band malst, kannst du dir selber festlegen, wann der Endzustand erreicht ist. Wenn du Tabellen malst, kannst ja dann auch irgendeinen Zustand zum Endzustand erklären.
Hat auch zufällig jemand Lösungen zu unserer letzten TI Klausur für Aufgabe II-4 und II-5 parat? Die beiden kommen mir etwas Sinologisch vor 
Was gegen Sinologen, aehm?? 
II-4:
die Funktion G(x,y) = { 0 falls x<= y;
undef sonst }
nachdem wir nach der letzten Komponente minimalisieren sollen, müssen wir das x verschwinden lassen. Wir suchen also den kleinsten x Wert, für den die Funktion G(x,y) = 0 ist. Nun wendet man das Verfahren aus dem Schöning an:
x0: = 0; y:= f(0, x1, …, xn);
WHILE y != 0 DO
xo:= x0 + 1; y:= f(x0, x1, … , xn);
END
da wir in der Aufgabe bloß noch mit y rechnen müssen, kommt für da für
μG(y) = 0 heraus.
II-5:
F(x,y) soll in etwa so aussehen:
F(x,0) = x; F(x,1) = f(x); F(x,2) = f²(x) ; …
für den Fall F(x,0) brauchen wir einen Spezialfall, nämlich:
F(x, 0) = g(x) = id = x; Identitätsfunktion.
für alle anderen Fälle brauchen wir sowas:
F(x, y) = h( F(x,y-1), f(x) );
h(x,y) muss also sowas in der Form f(x)^(y) = f(x)^(y-1) ° f(x) machen
also ist h(a,b) = a ° b (° ist die Verknüpfung zwischen Fkt)
also so haben wir uns das überlegt - hat da jemand ne Meinung zu?