Reduktionsmaschine Aus €w€w€ wird €w€
w=$a^i b^i c^i$
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.
