最初のタグシステムの定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/06 13:33 UTC 版)
「タグシステム」の記事における「最初のタグシステムの定義」の解説
上述の定義は、ポストが1943年に発表した当時のものとは異なる。ポストの定義では停止記号がなく、空の単語についてのみ停止するようになっていて、タグ操作 t は次のように定義されていた。 空でない単語 S の左端の記号を x としたとき、t(S) は最初に単語 P(x) を S の右に追加し、次に左端から m 個の記号を削除する。記号数が m 個未満なら、全記号を削除する。 下線を引いた部分は、m-タグシステムのチューリング完全性を考慮したものである。
※この「最初のタグシステムの定義」の解説は、「タグシステム」の解説の一部です。
「最初のタグシステムの定義」を含む「タグシステム」の記事については、「タグシステム」の概要を参照ください。
- 最初のタグシステムの定義のページへのリンク