>>761
>帰納的という言葉からは有限回で終わるような印象を受ける
基本的には殆どの関数は原理的には計算可能です。しかし、現実的に計算可能か否かとなると話は別です。
私は先の文で現実的にはコンピュータで計算不可能な関数を定義できるという意味で書いたつもりですが、
どうやらうまく伝わらなかったようです。
うまく書けるか否か分かりませんが、現実的に計算可能か否かが怪しくなるものの例を１つ挙げます。

m、n を限りなく大きい自然数とする（正確にはm、nは非負の整数でもよい）。関数Ackを
if m=0　　　　　
Ack(m,n) = n+1
if n=0
Ack(m,n) = Ack(m-1,1)
else
Ack(m,n) = Ack(m-1,Ack(m,n-1))
で定義する。すると、これは計算可能ですが、終了するまでにとてつもない時間がかかります。
（例えば１度 m = n 100 としてコンピュータに頼らず計算してみて下さい）。
ちなみに、これはよく知られています。

そうでなくても、単純に
8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8^8
のような数をコンピュータで計算させて値を画面に現実に出力させることが出来るか否かすら
怪しいでしょう（何桁の数になるか分かりませんので）。
私はコンピュータにこのような単純作業が出来るかどうかすら疑わしいです。
また、先のような数がとんでもなく膨大な冪乗になれば、
今度は時間的に計算可能かどうかが怪しくなってくるでしょう。

以上、コンピュータにとって現実的には恐らく不可能であろうと思われるものの例を挙げました。
私はコンピュータを用いて行う数学はさほど得意ではありませんので、
実際のところはどうかは分かりかねます。もしかしたら、後者の冪乗の計算では、
私の知らないところで実際に計算が出来てしまうアルゴリズムが存在するのかも知れません。
が、普通に考えればやはり存在しない可能性の方が高いでしょう。