Goedel's first incompleteness theorem の証明はいくつか知られていますが、いずれもどこかで論理式を自然数にコード化する部分(Goedel numbering)が含まれます。
直接的で分かりやすい numbering の方法として、素数のべき乗の積をとるものがあります。証明にはこれで十分です。この方法の望ましくない側面は、コードになる自然数の大きさが式の長さの階乗のオーダー(以上)になるというところです。一方で、Chinese Remainder Theorem と pairing function の組み合わせを使う、より洗練された方法もあります。
今回見つけた論文 "A Space-efficient Goedel Numbering with Chinese Remainder Theorem" は、CRT を使いつつコードをできるだけ効率よい小さい数にする方法が述べられています。結果となる空間のオーダーは、「メモリ上のプログラムを1つの大きな base 256 の数と見なすこと」という numbering の大雑把なイメージとつじつまが合っていると考えられます。
実際の内容を見ると、具体的なアルゴリズムの説明とその分析が述べられています。計算時間のオーダーも悪くないようです。これは非常に興味深いので実装してみたいです。