Untere Schranke

Für Maschine M und Eingabe x sowie Funktion f : $ \mathbb {N}$$ \mathbb {N}$ (z. B. n $ \mapsto$ 22n) konstruiere Formel D(M, x) mit

Für jedes Entscheidungsverfahren E für Presburger-Arithmetik:

bleibt zu zeigen, daß man solche D konstruieren kann.



2014-07-06