Orakel

Einfache Sprache

Def. Orakel

Ein Orakel für eine Sprache $A$ ist eine “Konstrukt”, dass für eine Eingabe $w$ ausgibt ob $w$ teil von $A$ ist. Dafür braucht das Orakel nur “einen Schritt”, kann die Information also sofort generieren.