>>743
つづき

1977年、パリスとハーリントンは、ラムゼーの定理の一種であるパリス＝ハーリントンの定理が、一階算術の公理体系であるペアノ算術の下では決定不能だが、より大きな二階算術の体系では証明できることを証明した。カービーとパリスは後にグッドスタインの定理（自然数の数列に関する命題であり、パリス・ハーリントンの原理よりもいくらか易しい）がペアノ算術では決定不能であることを示した。

計算機科学で応用される Kruskal の木定理（英語版）はペアノ算術では決定不能だが集合論では証明できる。実際、Kruskalの木定理（またはその有限版）は、可述主義（英語版）[注 4]と呼ばれる数学的哲学に基づいて構築されたもっと強い体系の下でも決定不能である。これに関連し、更に一般的な graph minors 定理（英語版）（2003年）は計算複雑性理論に影響する。

グレゴリー・チャイティンはアルゴリズム情報理論における決定不能命題を発見し、その状況下で新たな不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能ないかなる理論においても、どのような数であっても {\displaystyle c}c よりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 {\displaystyle c}c が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。

つづく