>>133計算可能であればfごとにアルゴリズムが存在し、そのアルゴリズムの複雑さに対応する帰納的公理化可能な理論が存在します。
>>134合ってはいますが、計算不可能関数も特定の言語で記述できますし。
1階述語論理による文をオラクルで与えられた適当な視点(集合論の何かしらの完全無矛盾拡大とか)から読み解くとか。