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.
berechenbarkeit vs. terminierung
und hier gleich der naechste battle:
was ist eigentlich der unterschied von berechenbarkeit und terminierung? gibt es funktionen die berechenbar sind und nicht terminieren und umgekehrt? oder wie hat man das ganze einzuordnen?
Eine funktion ist berechenbar, wenn du für sie einen Algorithmus in einer Programmiersprache angeben kannst. Dann ist sie demnach entweder partiell korrekt oder total korrekt.
Eine Funktion, die weder partiell noch total korrekt ist, ist auch nicht berechenbar!
äh ich denke eine Funktion die terminiert ist auch berechenbar. wenn sie nicht terminiert gibt´s ja kein ergebnis.
Ueberleg dir mal folgendes:
Eine funktion ist dann berechenbar wenn du sie in einen ALgorithmus ueberfuehren kannst. So lautet die definition.
Aussagen ueber terminierung sind hier gar keine gemacht. es kann ja sein dass dei funktion richtig arbeitet nur einfach nicht haelt.
Im Prinzip ist es glaub ich so dass du bei mue-rekursion berechenbare funktionen definierst die nicht immer halten muessen. Damit hast du schon mal festgestellt: nicht jede berechenbare funktion , terminiert fuer alle eingaben.
Aber etz ueberleg dir fuer die andere richtung (terminierung => berechenbarkeit): terminierung betrachtest du sowieso nur dann wenn du feststellen willst on ein Programm partiell oder total korrekt ist. das aber wiederum setzt voraus dass die im programm umgesetzte funktion berechenbar ist. Ansonsten macht terminierung keinen sinn.
Also kurz: Dich interessiert die Terminierung nur wenn eine funktion total oder partiell berechenbar ist. deshalb muss dich nicht interessieren ob aus einem das andere folgt oder andersherum oder ueberhauptnicht
Wenn du mit Terminierung die Terminierungsfunktionen meinst, dann würd ich folgendes sagen:
Mit der Terminierungsfunktion zeigt man die totale Korrektheit, also dass der Algorithmus auf jeden Fall terminiert.
Primitiv Rekursive Funktionen sind total und berechenbar, also du kannst eine Terminierungsfunktion für primitiv rekursive Funktionen angeben.
Die primitiv rekursiven Funktionen sind aber auch eine Teilmenge der µ-rekursiven Funktionen, d.h. es gibt µ-rekursive Funktionen, die nur partiell korrekt sind, dennoch berechenbar, aber du kannst dafür keine Terminierungsfunktion angeben, weil sie eben nur partiell korrekt sind.
Schau dir dazu mal die Funktion quot(m,n) im Skript (steht gleich nach dem Kapitel zur primitiven Rekursion) an. Da wirst du dich mit einer Terminierungsfunktion schwer tun, dennoch ist quot(m,n) berechenbar.
vielen dank an alle, ich denke, ich hab’s geschnallt, auch wenn ich hoffe, dass sowas morgen nicht so genau drankommt. vor allem mue-rekursion - da kann ich nur die definition runterschreiben, verstanden hab ich das nicht wirklich und will es jetzt auch gar nicht mehr verstehen.
ich kann dich in sofern beruehgen als dass mir gesagt wurde dass mue-rekursion eher stoff der TI vorlesung ist. Aber zu sachen verstaendnis:
wenn du mue-rekursion auf eine funktion anwendest machst du nix anders als zu fragen: was ist deine kleinste nullstelle f(x)? hast du denn ueberhaupt eine nullstelle ?
Naja und etz gibts folgende moeglichkeiten:
1)Die Funktion hat eine Nullstelle dann ist das automatisch die kleinste,
2)Die Funktion hat mehrere Nullstellen, dann muss gelten dass es keine Nullstelle y gibt die kleiner ist als y0 und
3)letzte moeglichkeit : f hat gar keine nullstellen dann hat sich das problem fuer dich erstmal erledigt. Wert deiner mue-rek ist dann unspec(takulaer)
Mehr brauchst du im moment net drueber wisssen