Part Bに入りました。いよいよ算術です。なぜか新井敏康著『数学基礎論』ではPAオンリーでロビンソンの算術Qは出てきません。 算術Qで不思議なのはやはり、p.69の でしょうか。公理A4でがあるので、これは加法の交換法則の特殊なもの すら成立していないこと…

またもや重箱の隅をつついて遊ぶ探究ではありますが、p.54 補題4.15で『 AがREならば [tex:\forall y が再帰的でないことの証明(ほとんどRiceの定理の証明)： 再帰的であると仮定して、その特性関数をとする。 また と定義すると は(定理4.19)をREとして特徴…

PART A 第４講に入りました。テキストのこの講はかなり駆け足というか猛ダッシュで、クリーネの標準型定理が説明だけなのは肩すかしをくらったような感がありますが、計算論のどの教科書にも載っている内容だからということなのかもしれません。私もちょこち…