m-タグシステムのチューリング完全性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/06 13:33 UTC 版)
「タグシステム」の記事における「m-タグシステムのチューリング完全性」の解説
任意の m > 1 である m について、m-タグシステムの集合はチューリング完全である。すなわち、あるチューリング機械 T について、T をシミュレートする m-タグシステムが必ず存在する。特に、2-タグシステムで万能チューリング機械のシミュレートが可能であることが、Wang（1963年）と Cocke & Minsky（1964年）で示されている。 逆に、あるチューリング機械でチューリング完全である m-タグシステムのクラスをシミュレートできることを示すことで、それが万能チューリング機械であることを示すことができる。例えば、Rogozhin（1996年）は 2-タグシステムのクラスの万能性を証明した。このときの 2-タグシステムのアルファベットは {a1, ..., an, H}、生成規則は {ananW1, ..., ananWn−1, anan, H}、Wk は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さな（4状態、6記号）のチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。
※この「m-タグシステムのチューリング完全性」の解説は、「タグシステム」の解説の一部です。
「m-タグシステムのチューリング完全性」を含む「タグシステム」の記事については、「タグシステム」の概要を参照ください。
ウィキペディア小見出し辞書の「m-タグシステムのチューリング完全性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- m-タグシステムのチューリング完全性のページへのリンク
