 Aufgabe: Algorithmen |
cyberjohn
Grünschnabel
Dabei seit: 25.11.2012
Beiträge: 9
 |
|
Meine Frage:
Hallo,
ich habe eine Aufgabe zu Algorithmen erhalten, weiß aber nicht wie man diese lösen kann. Die Aufgabe befindet sich im Anhang.
Meine Ideen:
a) Man kann X* nicht lösen, weil "*" überabzählbar ist und somit kann kein Algorithmus für beliebige Algorithmen gelten bzw. terminieren.
b) Könnte berechenbar sein f(alpha)=(w), aber aeX* ist überabzählbar und dadurch kann man die Aufgabe nicht terminieren.
Sei E eine beliebige Eigenschaft, die von mind. einer, aber nicht von allen berechenbaren Funktionen f: X*->X* erfüllt wird, dann gibt es keinen Algorithmus, der für beliebige Algorithmen (alpha)eX* ausgibt, ob f(alpha) die Eigenschaft erfüllt oder nicht. Das bedeutet, dass die Aufgabe, einem Algorithmus "anzusehen", ob die durch ihn berechenbare Funktion eine bestimmte Eigenschaft besitzt, nicht algorithmisch gelöst werden kann.
Sind meine Ideen schon auf den richtigen Weg oder ist mein Ansatz komplett falsch?
Mit freundlichen Grüßen,
cyberjohn
cyberjohn hat dieses Bild (verkleinerte Version) angehängt:
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von cyberjohn: 25.11.2012 14:15.
|
|
25.11.2012 14:09 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
ich gehe davon aus, dass X* der Kleene-Stern über einer Sprache oder einem Alphabet X ist. Demnach ist X* nicht überabzählbar und deine Annahme ist falsch.
Teil a) ist das Halteproblem für Turingmaschinen
Bei Teil b) bin ich mir nicht sicher. Das sieht aus wie eine Variation des Halteproblems. Damit wäre es auch nicht entscheidbar.
VG,
Karlito
|
|
|
25.11.2012 22:49 |
|
|
cyberjohn
Grünschnabel
Dabei seit: 25.11.2012
Beiträge: 9
|
|
Hallo Karlito,
vielen Dank für Deine schnelle Antwort! Ich habe das Halteproblem von Turingmaschinen bei Wikipedia durchgelesen. Da ich erst im 2. Semester Theoretische Informatik belegen werde, ist es für mich schwierig die Aufgaben im Bereich Programmierung zu verstehen.
Nochmals Dankeschön für Deine Unterstützung! 
Mit freundlichen Grüßen,
cyberjohn
|
|
|
27.11.2012 14:39 |
|
|
|
Aufgabe: Algorithmen
