Vorlesung 7 Seidl

S. 15

Reduktionsmaschine
Aus €w€w€ wird €w€

w=a^i b^i c^i

S. 18

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.