-PR-
解決済み

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

  • 困ってます
  • 質問No.972153
  • 閲覧数487
  • ありがとう数5
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 84% (351/415)

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

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


規則を設計・・・って解答例としてどういう解答が考えられるのでしょうか?
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル13

ベストアンサー率 48% (730/1515)

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

でもいいかもしれません。
お礼コメント
usui323

お礼率 84% (351/415)

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

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

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

大変参考になりました。
親切な解答ありがとうございました。
投稿日時 - 2004-08-25 12:00:14

その他の回答 (全1件)

  • 回答No.1
レベル13

ベストアンサー率 48% (730/1515)

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

以下のような感じでどうでしょう。
「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
でもいいでしょう。たぶん。
お礼コメント
usui323

お礼率 84% (351/415)

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

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

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

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

私はチューリングマシンの話なんかも全然知らないんですけどね(^_^;)
投稿日時 - 2004-08-23 15:06:52


このQ&Aのテーマ
このQ&Aで解決しましたか?
関連するQ&A
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-

特集


開業・独立という夢を持つ人へ向けた情報満載!

ピックアップ

-PR-
ページ先頭へ