チューリングマシンについての問題。

人からこのような問題を聞かれましたが、全く意味がわからず困っています。

無限にテープ上に、英小文字が適当に並んでいる。
現在チューリングマシンが読んでいるところから右側にある、sinという文字列を見つけたら、cosと書き換えたい。
この問題を解くための、チューリングマシンの規則を設計しなさい。（最小限）


規則を設計・・・って解答例としてどういう解答が考えられるのでしょうか？

No.2 ベストアンサー 回答者： liar_adan 回答日時： 2004/08/23 17:41

1:(s) _R2, (not s) _R1

というのは、「状態1」の記述で、
「文字がsならば_R2の動作を行い、
s以外ならば_R1の動作を行う」
というつもりで書いています。

いろいろ記号はあると思いますが、
手元にあった本を参考にして、似た書き方を使っています。

いま思いつきましたが、1回書き換えるだけならば

1:(s) _R2, (not s) _R1
2:(i) _R3, (not i) _R6
3:(n) sL4, (not n) _R6
4: oL5
5: c(停止)
6: _L1

でもいいかもしれません。

この回答へのお礼

解答ありがとうございました。

意味がわかりました。
なるほど、こういう風に書くこともできるのですね。

C言語などでプログラムしろといわれれば簡単ですが、
設計しなさいとはどう書いて良いのかわかりませんでした。

大変参考になりました。
親切な解答ありがとうございました。

お礼日時：2004/08/25 12:00

No.1 回答者： liar_adan 回答日時： 2004/08/23 11:51

なんだか課題のような気もしますが…面白そうなので答えます。

以下のような感じでどうでしょう。
「cR6」は「cを書き込んで右に行って状態6に遷移」の意味です。
「_L4」は「何も書かず左に行って状態4に遷移」です。
一度書き換えを行ったら停止するようにしています。

1:(s) _R2, (not s) _R1
2:(i) _R3, (not i) _R8
3:(n) _L4, (not n) _R8
4: _L5
5: cR6
6: oR7
7: s(停止)
8: _L1

また
1:(s) _R2, (not s) _R1
2:(i) _R3, (not i) _L8
3:(n) _L4, (not n) _L8
4: _L5
5: cR6
6: oR7
7: s(停止)
8: _R1
でもいいでしょう。たぶん。

この回答へのお礼

解答ありがとうございます。
解答なしだろうと思っていたので、非常にうれしいです。

こういう問題ってこのような解答の仕方をするものなのでしょうか？

1:(s) _R2, (not s) _R1

というのはどういう意味なのでしょうか？
ちょっと、このような書き方をはじめて見ましたので。

私はチューリングマシンの話なんかも全然知らないんですけどね(^_^;)

お礼日時：2004/08/23 15:06