• 締切済み

チューリングマシンについて

Σ={0,1}の2-tape 決定性チューリングマシンの動きを、 1-tape 決定性チューリングマシンでシミュレートするにはどうすればよいか？　 quintuples で説明せよ。 という問題なのですが、どう解けばいいのか分かりません。 どなたか分かる方、よろしくお願いします！

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

たぶん, オートマトンについてちょっと詳しい本なら書いてあるんじゃないでしょうか. 手元にある本だと 「計算理論とオートマトン言語理論」, 丸岡章, サイエンス社 にはある.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • チューリングマシンの限界について

    第２次世界大戦前、チューリングのアイデアによって数学上の さまざまな問題を解くチューリングマシンが考え出され、 同時にチューリングマシンの限界も提示されました。 それは、数学的問題の中にはアルゴリズムに変換できない問題 は、チューリングマシンによっても解くことができない問題が 存在していることを示したそうです。 チューリングマシンをコンピュータに置き換えると、私はこれを 「解決策を、人間が論理的に置き換えることができるものは、 全てコンピュータで処理することができる」と解釈していましたが、 数学上の問題で論理的に置き換えることができない問題とは 具体的にどんな問題でしょうか？ 数学にはあまり詳しくないのでよろしくお願いします。

  • チューリングマシン　　　　　　　　　　　　　　　

    チューリングマシン　　　　　　　　　　　　　　　 現在の状態 0　0　0　0　1　1　1　　　　　　　　　 読んだ文字 0　1　X　□ 0　0　1　　　　　　　　　 ーーーーーーーーーーーーーーーー...以下略　　　 次の状態　 1　2　0　終 1　3　1　　　　　　　　　 書く文字　 □ □ □ □ ０ X　X　　　　　　　　 移動方向　 右 右 右 　 右 左 右　　　　　　　　　 「０」「１」が連続して書かれていて、調べたい０，１の前後は□になっています。 左から一文字ずつ消していき、その際左端が０なら１を、１なら０を1つ消す。 このチューリングマシンは、このようにして「０」「１」の数がちょうど等しいかどうかを調べるものらしいのですが、どうして次の状態に２，３がでてくるのか?また、なぜ左に戻ったりするのか？などいまいちよくわかりません。 詳しく載っているサイトか、説明をお願いします。　　　　　　　　　　　　　　　　　　

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

    人からこのような問題を聞かれましたが、全く意味がわからず困っています。 無限にテープ上に、英小文字が適当に並んでいる。 現在チューリングマシンが読んでいるところから右側にある、sinという文字列を見つけたら、cosと書き換えたい。 この問題を解くための、チューリングマシンの規則を設計しなさい。（最小限） 規則を設計・・・って解答例としてどういう解答が考えられるのでしょうか？

  • チューリングマシンについて

    計算理論の勉強をしています。 チューリングマシンが、ある言語を「判定する」というのと「認識する」ということの違いがよくわかりません。 どなたか解説していただけないでしょうか。

  • 多数のチューリングマシンで複雑系は、作れるか？

    １個のチューリングマシンは、複雑系ではないと思います（多分ですが） 多数のチューリングマシンで複雑系は、作れるのでしょうか？ 多数のチューリングマシンが、途中経過を　やりとりすると、結果がカオスになってもいいような気がします。 どうなのでしょうか？ PS。 カオスをｆ(x)とすると、ｘとｘ＋dx　で、カオスなら結果が異なるので、 デジタルな系では、どんなに複雑でも、カオスは、発生しない ということで、いいでしょうか？ もし、そうなら、デジタルな系では、複雑系を作れない　ということで合ってますか？

  • チューリングマシンとオートマトンでできることの違い

    チューリングマシンとオートマトンでできることの違いは、具体例で言うとどういうことでしょうか？ 計算理論の本を一生懸命読んでいて、数式が多くてまだ完全に理解できてないのですが、私の理解した範囲で書くと、 ●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」 ですよね。 そして、ネットで調べると、「オートマトン」の例として自動販売機があって、これは非常に理解できました。 「チューリングマシン」の例としてはコンピュータがあって、これはこれで理解できました。 しかし、自動販売機にできなくてコンピュータにできること、の違いがよく分かりません。自動販売機にテープをつけると具体的にどういうメリットがあるのでしょうか？ 他の例でも良いので、チューリングマシンとオートマトンでできることの違いを具体例で教えていただけると幸いです。 ぜひ、よろしくお願いいたします。

  • チューリングマシン テープのn次元拡張について　

    通常のチューリングマシンは１次元のテープで、ヘッドが右か左に動くのですが、 これを２次元、３次元・・・に拡張した場合のチューリングマシンについての議論を調べています。 （２次元の場合、平面上のセルでヘッドが東西南北に動くようものを想定しています） いずれも、通常のチューリングマシンに還元可能されるとのことですが、 このあたりの議論や解説が載っている本、あるいはＷｅｂページがありましたら教えてください。 ついでに、ヘッドのアルファベット読み取り・書き込みが１個のデータでなくｎ個のデータの場合（テープが一本幅ではなくｎ本幅）にも通常のチューリングマシンに還元可能とのことですが、上記のｎ次元チューリングマシンでも通常のチューリングマシンに還元可能なのでしょうか。 数学は素人同然なので、質問が曖昧であることにはあらかじめ謝罪しておきます。

  • 状態遷移図とチューリングマシンとは

    アルゴリズムについて学んでいた際、 「状態遷移図」と「チューリングマシン」という言葉が出てきました。 この二つはどういう関係と意味を持っているのでしょうか？ 調べてみたのですがオートマトンやら難しい計算式ばかり出てきてあまり理解できませんでした。 計算式を見て理解できないならそれまでなのかもしれませんが、 何か比較的簡単な説明を頂けないでしょうか？ お願いします。

  • チューリングマシンの状態数について

    この質問で言うチューリングマシンは、 「使用できる文字が0,1,Xだけのもの」とします。 自然数nに対し、 「空列を入力して動作を開始すると、有限ステップで停止して、停止したときにテープに書き残されている文字数がn以上」 であるようなチューリングマシンを全て集めた集合をKnとします。 そして、 g(n)= min{size(M) | M∈Kn } とします。ただし、size(M)はチューリングマシンMの状態数であり、minは「最小値」を意味します。 各nに対してKnは非空集合なので、g(n)の値はどんなnに対しても一意に定義されます。 すなわち、gは自然数上の全域関数です。 ビジービーバー関数は「状態数」から「その状態数のチューリングマシンが書き残せる最大字数」を求めるものでありますが、 この関数gは「字数」から「それ以上の字数を書き残せるチューリングマシンの最小状態数」を求めるものです。 このgが計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。 よろしくお願いいたします。 ((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)

  • オートマトンとチューリングマシンの違い？？

    チューリングマシンとオートマトンの類似点と相違点の考察って言うレポートをだされたのですが、指定の量まで今一つたりないんです。 いろいろなＨＰとか本を検索してみたのですが、どうも同じようなことが書いてあってぜんぜん進みません(＞＜)それにあまり時間もないので・・・ レポートのことを質問するのはよくないと思うという人もいるとは思いますが、切羽詰っているので教えてください。お願いしますm(_ _)m

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する