再帰性と予測不能性

再帰的列挙とは、新しいものが古いものから一定の規則によって出現する過程のことである。そのような過程には、びっくりすることがたくさんあるように思われる。再帰的に定義されるその種の数列には、行動の複雑さのある本質的な増大が伴うらしく、先に進めば進むほど、予測がさらに困難になる。
このような考えをさらに推し進めると、適度に複雑な再帰的システムはどんな予定されたパタンからも逃れられるくらい強力であるらしい。そして、これこそ知性の要件のひとつではなかろうか？自分自身を再帰的に呼び出す手続きから成るプログラムを考えるだけでなく、もっと技巧的な、自分自身を修正できるプログラム―自分自身に働きかけて拡大し、改良し、一般化し、修理できるプログラムを発明するのはどうだろうか？この種の「もつれた再帰性」はおそらく知性の核心部分にかかわっている。
ゲーデル・エッシャー・バッハ、p.165

再帰って昔理解するのにすごく苦労した覚えがある。直感的にはあーなるほどと思うのだけど、本当にこれでできるのか？という疑念がいつまでも抜けなかった。フィボナッチ数列くらいなら問題ないんだけれどクイックソートとかハノイの塔とか木に関する再帰的アルゴリズムは今でもちょっと不思議だなーと思ってしまう。再帰は慣れればすごくわかりやすいけど理解するのにコツがいると思う。

再帰のアルゴリズムは、上に挙げたのぐらいしか知らないけど、ホフスタッターさんが言うようなもっと複雑なのはどんなのがあるのだろう？