Mathematik für Faule: Effizientes Rechnen/Berechenbarkeit

Satz (Die Goodstein-Abhängige kann nicht durch ein "for"-Programm berechnet werden):

Beweis: Es sei irgendein beliebiges For-Programm $P$ gegeben. Wir wollen beweisen, dass es die Goodstein-Abhängige nicht berechnen kann. Es sei $n$ die maximale Anzahl der For-Programme, aus denen ein Unterprogramm von $P$ besteht, und $k$ die maximale Tiefe eines Unterprogramms von $P$. Dann sieht man durch Induktion über den Aufbau von $P$, dass die maximale Anzahl an Inkrementen, die von $P$ durchgeführt werden können, durch

$x\uparrow ^{k-2}n$

beschränkt ist, wobei $x$ die größte Input-Variable ist. Die höheren Operationen können also nicht berechnet werden. $\Box$