TMの停止問題は非可解であることの証明。 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析する。 TM停止問題が非可解 インスタンスとしてTM Mと列ρ。 Mがρに対して停止…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。