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.
Lösungsversuch Klausur WS14/15
Source: https://fsi.cs.fau.de/dw/_media/pruefungen/grundstudium/bfs_2015-02-03_braindump.pdf
Hey, ich habe versucht, die Aufgabe 2 zu lösen. Stimmt das?
Zu zeigen: Hℇ <= L2b
FM:
- Die Eingabe sei y.
- Starte M mit ℇ.
- Falls y == 0 oder y == 1, halte.
f(x): - <FM>1, falls x=
- 0 , sonst
f ist total berechenbar.
“=>” x ∈ Hℇ: x= und M, gestartet mit ℇ, hält => f(x) = <FM>1 ∈ L2b.
“<=” x ∉ Hℇ: x≠ und M, gestartet mit ℇ, hält nicht (geht in eine Endlosschleife) => f(x) = <FM>1 ∉ L2b.
x ∉ Hℇ: x≠ => f(x) = 0 ∉ L2b.
Somit ist Hℇ nicht entscheidbar und x ∈ Hℇ <=> f(x) ∈ L2b.
Muss in der Form: f(x): - <FM>#1,0 falls x= sein, da du für 2 verschiedene Zahlen hälst.
Müsste denke ich so sein:
FM:
- Die Eingabe sei y.
- Falls y = #1,0
- Starte mit ℇ.
- halte.
- sonst
- laufe unendlich
„=>“ x ∈ Hℇ: => x=
=> FM gestartet mit ℇ, hält
=> f(x) = <FM>#1,0 ∈ L2b.
„<=“ x ∉ Hℇ: => x= aber FM, gestartet mit ℇ, hält nicht (geht in eine Endlosschleife) => f(x) = <FM>1 ∉ L2b.
x ∉ Hℇ: x≠ => f(x) = 0 ∉ L2b.
Da Hℇ nicht entscheidbar und x ∈ Hℇ <=> f(x) ∈ L2b.
2 Likes
Ob man M vor oder nach dem Vergleich startet dürfte doch keinen Unterschied machen?
Die Lösung von Cerox sieht wunderbar aus.
Erstmal danke!
Wäre es auch richtig? Ich habe beispielsweise so ne ähnliche Lösung für A20.
FM:
- Die Eingabe sei y.
- Starte M mit ℇ.
- Falls y = #1,0 halte.
mit:
4. Endlosschleife
ist das genau was ich gemacht hätte. Denke auch das man das braucht.
1 Like
Auf den 4.Punkt kann man verzichten, ist ja sowieso klar
Ich würde eher nicht drauf verzichten, es ist 1 zusätzliche Zeile, diese bringt dich nicht um 
Und da die Korrektur doch eher auf Feinheiten achtet, würde ich es einfach mal hin schreiben.