|
タグシステム（）は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、ポスト正準系のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械（Post Tag Machine、PTM）とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。 == 定義 == タグシステムは三つ組 （''m''、''A''、''P''）で表され、それぞれは以下の意味を持つ。 * ''m'' - 正の整数であり、削除数（deletion number）と呼ぶ。 * ''A'' - 記号群の有限アルファベット。そのうちの1つが特別な停止記号（halting symbol）である。''A'' で構成される（空も含む）有限の文字列を単語（words）と呼ぶ。 * ''P'' - 生成規則群。''A'' に含まれる個々の記号 ''x'' に適用することを ''P''(''x'') で表す（生成するとも呼ぶ）。停止記号への生成規則の適用（''P''(H)）は後述するように計算には何の意味もないが、利便性のため ''P''(H) = H とされる。 ''m''-タグシステムと言った場合、''m'' は削除数を指す。タグシステムの定義は書籍によって異なるが、ここでの説明は Rogozhin のものに準じている。 * 停止単語（halting word）とは、停止記号で始まる単語か、長さが ''m'' 未満の単語である。 * 変換 ''t''（タグ操作とも）は、停止単語以外の単語について定義されており、単語 ''S'' の左端の記号を ''x'' としたとき、''t''(''S'') とは ''S'' の左端から ''m'' 個の記号を削除し、残った部分の右側に単語 ''P''(''x'') を追加したものである。 * タグシステムにおける計算とは、変換 ''t'' を繰り返すことで有限単語列を生成することであり、初期状態で何らかの単語が与えられ、停止単語が生成された時点で停止する。なお、この定義では、有限回の繰り返しの間に停止単語が生成されない場合を計算とは呼べない。 この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。 典型的な別の定義として、停止記号を使わず、''m'' 未満の長さの単語を全て停止単語とする定義もある。また、ポストが1943年に最初に発表した定義では、空文字列についてのみ停止するようになっていた。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「タグシステム」の詳細全文を読む スポンサード リンク
|