BuK/IIm20/Vorlesung 7 Seidl

Wiki-Quelltext dieser Seite.

=== S. 15 ===
Reduktionsmaschine<br/>
Aus €w€w€ wird €w€

w=$a^i b^i c^i$

[[Bild:Fseidl_Photo_2021-05-07_16-03-26.jpg]]

=== S. 18 ===
[[Bild:Fseidl_Photo_2021-05-07_16-48-28.jpg]]

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

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