例1 　　　 自然是可计算的。 例2 　　将n依次与12，22，…作比较总可求得，所以是可计算的（表示不超过x的最大自然数）。 例3 第n个素数 　　可逐一检查n，能否被比n小的2，3，…除得尽来确定数n是否为素数，n一确定就是个有限过程，于是是可计算的。 例4 　　　 　　因π 的展开式是个无穷序列，所以一般不可计算。如p(4) 的计算，需在π的展开式中找4个5，这可能是个无限过程。 例5 　　　 　　　由于有无整数解还没有解决，所以S(n) 不可计算。