Aufgabe: Algorithmen |
| 25.11.2012, 14:09 | Auf diesen Beitrag antworten » |
| cyberjohn | Aufgabe: Algorithmen 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 |
|
|
|
| 25.11.2012, 22:49 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| 27.11.2012, 14:39 | Auf diesen Beitrag antworten » |
| cyberjohn | 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 |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
