タイプのないラムダ計算のサブセットを強く正規化する表現力/圧縮力は何ですか?

$ Lambda $を強く正規化するラムダ項の集合とする。
$ mathtt {NF}: Lambda rightarrow Lambda $を通常の形に評価します。
$ lvert x rvert: Lambda rightarrow mathbb {N} $とする
記号の数による用語のサイズ。
次の関数はよく定義されているようです:

$$ f_ Lambda: mathbb {N} rightarrow mathbb {N} $$ $$ f_
Lambda(n)= max_ { lambda、 lvert t rvert leq n} lvert
mathtt {NF}(t) rvert $$

$ f_ Lambda $の成長率はどれくらいですか?

急成長する階層でいくつかの下限と上限を定義できますか?

ベストアンサー

単純にタイプされたラムダ計算の項の最大ブローアップは、非基本的なものである(2↑↑O(n)、例えば[1]ページ72参照)。これはあなたが求めているものではありませんが、型付きラムダ計算は型なしラムダ計算の強く正規化されたサブセットなので、下限を与えるはずです。

一般的な質問に答えることができるかどうかはわかりません。型なしラムダ計算はチューリング完全であり、強く正規化するフラグメントは、終結プログラムのセットと等価である。この集合のメンバーシップはすでに決めることができないので、通常の書式のサイズの上限を示すことはできません。

[1] Morten HeineSørensenとPawel Urzyczyn。 Curry-Howard
Isomorphismの講義、論理学と数学の基礎の研究の巻149。 Elsevier Science
Inc.、ニューヨーク、ニューヨーク、米国、2006年。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です