Untere Schranke

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

• D(M, x)$\iff$ Maschine M hält bei Eingabe x in ≤f (| x|) Schritten.
• D(M, x) ist klein und kann schnell berechnet werden.

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

• konstruiere Programm E₀(x):
  if E(¬D(x, x)) then stop else Endlosschleife.
• Beweise: Rechnung E₀(E₀) hält nach > f (| E₀|) Schritten.

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