決定可能かどうかは、
それをMのn番目の元を計算する計算量の少ないチューリング機械があるかどうかにかかっている。
厳密にはステップ数がO(n^p)であればいい。
(1)〜(4)はF(n)がチューリング機械でステップ数O(n^p)(pは定数)で計算できるのですべて決定可能。
ところが、素数n番目の素数はどうやってもO(n^n)かかる。
よって計算不能。