hat-tun https://blog.hatena.ne.jp/hat-tun/ hat-tunの日記 https://hat-tun.hatenadiary.org/ レポート 証明 アルゴリズム TMの停止問題は非可解であることの証明。 L={ρi| TMρiは列ρiに対して停止して受理しない} という言語が必ず停止するTMで認識できないことは証明されているとする。 まず問題を分析する。 TM停止問題が非可解 インスタンスとしてTM Mと列ρ。 Mがρに対して停止するかどうかという問題が止まらない停止するTMで解けない＝Mがρに対して停止するかどうかはわからない。 次に、背理法による証明を試みる。 TM停止問題が必ず停止するTM Mhが存在すると仮定する。 ここでMhは、インスタンスとしてTM Mと列ρをとる。 この仮定から、言語Lを認識するTM Tが存在してしまうことを示す。＝ １つ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhat-tun.hatenadiary.org%2Fentry%2F20081222%2F1229960572" title="TM停止問題 - hat-tunの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-12-22 00:42:52 rich https://hat-tun.hatenadiary.org/entry/20081222/1229960572 1.0 100%