This flashcard is just one of a free flashcard set. See all flashcards!
39
Beweis: Satz von Rice Korrektheit
Korrektheit:
Falls Eingabe keine Korrekt GN ist, verwirft
korrekterweise die Eingabe. Bei Eingaben der Form 
gilt:
:
=> M hält auf
=> M* berechnet f
=> <M*>
L(S)
=>
akzeptiert <M*>
=> akzeptiert w
:
=> M hält nicht auf
=> M* berechnet u
=>
=> verwirft <M*>
=> verwirft w.
2.Fall:
wähle f aus 
Falls Eingabe keine Korrekt GN ist, verwirft
korrekterweise die Eingabe. Bei Eingaben der Form gilt::=> M hält auf
=> M* berechnet f
=> <M*>
L(S)=>
akzeptiert <M*>=>
akzeptiert w: => M hält nicht auf
=> M* berechnet u
=>
=>
verwirft <M*>=>
verwirft w.2.Fall:
wähle f aus 