BuK/IIm20/Vorlesung 7 Belkouchi

Wiki-Quelltext dieser Seite.

== Folie 18 ==

A:P' ist entscheidbar

B:P ist reduzierbar auf P'

C:P ist entscheidbar

[[Bild:Soufiane_S18.PNG]]


wenn P' entscheidbar ist und P ist reduzierbar auf P', dann P ist entscheidbar.

wenn P nicht entscheidbar ist und P ist reduzierbar auf P', dann P' ist nicht entscheidbar.