停止検出器はどれくらい良いことができますか?

ほぼすべての他のチューリングマシンが停止しているかどうかを判断できるチューリングマシンはありますか?

チューリングマシンのいくつかの列挙$ mathbb {N} rightarrow {M_i }
$と、自然数の集合の “サイズ”という概念があるとします。 cdot | $と定義します。

$$ f(i)= | {n:M_i text {M_n text {halts} }
|を判断することはできません。

異なる$ |に対して$ f $の最小値のどのような特徴付けが存在するか? cdot | $?たとえば、$ | S
| $は、$ S $にある$ k $までの数の割合の変化です。 $ f(i)= 0 $の$ i $がありますか?

ベストアンサー

真か偽かはエンコーディングに依存するため、これは「いい」プロパティではありません。

Davidらの 漸近的にほぼすべての$ lambda $
-termsが強く正規化されている

、これはタイトルで何が表示されているかを証明します。しかし、この論文はまた、SKIコンビネータ(ラムダ項が組成的に埋め込まれることができる)の反対が成り立つことを示している。

ラムダ計算では、 reduction
はチューリングマシンのステップに相当し、強い正規化はすべてのリダクションシーケンスが最終的に通常のフォームになるという性質です。
(与えられたラムダ項には多くの有効な減少があるかもしれないので、強い正規化は、ある非決定論的チューリング機械が常に停止すると言っているようなものです。)漸近的にほとんどすべての$
λda-termsが強く正規化しているという事実は、 1では、大きなラムダ項を減らすと常に通常の形になります。

しかし、ラムダ項は、意味を保存した形で、 などの結合計算に変換できます。 SKIコンビネータ
(逆もまた同様)、コンビネータ計算では、漸近的にすべての用語ループが発生します。

返信を残す

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