締切済み

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

2009/01/20 14:25

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

squall88
お礼率81% (117/144)

数学・算数
回答数1
ありがとう数2

みんなの回答 （1）
専門家の回答

みんなの回答

Tacosan
ベストアンサー率23% (3656/15482)

2009/01/20 19:21 回答No.1

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

関連する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
チューリング完全とは何か？

プログラムのチューリング完全性とか万能チューリング機械ってあるじゃないですか。これって、どんな挙動のプログラムでも１言語で書けるって事ですか？色々と調べてみたのですが、どのサイトもどの資料も説明が難しかったので、ここで質問してます。私の認識は下の通りです。チューリング完全のプログラムは、FORTRAN、Ｃ言語、Java、JavaScriptなど。チューリング不完全のプログラムは、TeX、HTML、SQLなど。要するに、 TeXは数式や楽譜の作成くらいの機能に制限されている。その一方で、FORTRANは数学的計算は勿論、３Ｇゲームや通販サイトなどFORTRAN１言語だけで何でも出来て、ありとあらゆるシステム構築に使えるって事ですか？チューリングは、戦前イギリスの数学者の名前。彼は次の命題の証明をした。どんな複雑なコンピューターシステムでも中身を分析すれば、四則演算や条件分岐や反復など数種類の小さな基本的システムパーツの組合せになっている。FORTRANやＣ言語はこれを全て含んでいるから、FORTANは何でも出来る。一方、SQLは惜しいがチューリング完全に必須の基本的システムパーツが数種類だけ欠けていて、限界がある。SQLオンリーでゲームを作ろうとすれば、テトリスくらいなら出来るけど、ぷよぷよを作ろうとすれば別の言語を足す事になる。正しいですか？
コンピューターサイエンスのチューリングとは何者なの

コンピューターサイエンスのチューリングとは何者なのでしょうか？チューリングの計算理論とは何なのか、分かりやすく説明してください。
神の不存在証明

チューリングマシンの停止問題というのがあるというのを知りました。これは、決定論の否定が成立している証拠と考えていいですよね？つまり、「世界の未来を完全に予測するのは不可能」という事ですよね？同時に、この事から「あらゆる事を知る事が出来る存在」つまり、神（God)は存在しない、という事になりますか？チューリングマシンの停止問題は神の不存在証明だと思うのですが、それについて教えて下さい。
チューリング機械の状態遷移図

h(x)=0(x=0のとき),定義されない(x>0のとき) のチューリング機械の状態遷移図を書けという問題なのですが、x>0のときというのが難しいです。チューリング機械ではx≠0ということは指定できないですよね？こういった場合はどのように書けばいいのでしょうか？あと、「定義されない」ということなんですが最終的に空白なマスにとどまっていればいいのでしょうか？
問題の意味がわかりません。。

ある問題を解かなければならないのですが、問題の意味がよくわかりません。問題１入力ワード x(｜x｜=n)に対して、'timer'として用いる関数ｔ(n)=nのk乗(k=1,2,3...) と　t(n)=2のn乗が　time-constructible function であることを示せ。即ち、 deterministic Turing machine Tで　T(x)が　c・t(｜x｜)steps (c:定数)で停止するようなものをそれぞれ答えよ。問題2 Σ={0,1}の2-tape deterministic Turing machine の動きを 1-tape deterministic Turing machime でシミュレートするにはどうすればよいか？　 quintuples で説明せよ。このような問題はどのように答えればいいんでしょうか？よろしくお願いします！
巡回セールスマン問題: NPについて

　NP問題である巡回セールスマン問題について質問です．　NP問題には，「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば，その答えがYesであることを(問題の入力サイズに関する)多項式時間以内に確認することができる決定問題」などの定義があります．このふたつめの定義について質問です．　巡回セールス問題における解を確かめる「証拠」とはいったいどのようなものなのでしょうか?
人工生命に詳しい方教えて下さい

ＰＣ上で生物をシミュレートすることは、現在はどこまで可能ですか？熱帯魚を育成するＰＣソフトで有名な物に『アクアゾーン』がありますけどこれは背景や熱帯魚や動きや反応等は本物と見分けがつかない程リアルですよね。そこで同じように小動物のハムスターをシミュレートすることは可能でしょうか？以下の条件でどこまで可能ですか？・背景やハムスターのグラフィックは本物並みにリアル・ハムスターの動きや反応は本物と見分けがつかないくらい自然でリアル　つまり動物のチューリングテストをパスしているようなもの・生命活動もリアルにシミュレート・ハムスターには心がある。心と言っても曖昧なので　心とは以下の5つの機能を持っていると定義する。知能、感情、意思、記憶と学習、意識。よろしくお願い致します。
フィットネスマシーン

フィットネスのマシーンで、ボートを漕ぐような動きをするマシーンのことをなんと言うのでしょうか？検索で調べているのですが、なかなか見つかりません。よろしくお願いします。
ワインディングマシーン

タグホイヤーの WJ201C用のワインディングマシーンを探しています　少し教えて下さい　時計を　床面に対して垂直に　設置するタイプと垂直と水平の間ぐらいの角度で設置するタイプとあるようなのですが　この後者のタイプを想定して自分の手で大体の角度を決めて再現してみるとローターが回っていないような感じなのですが問題なく回るのでしょうか（バッククリスタルなのでローターの動きは確認できます）中々理想のワインディングマシーンが見つかりません上記ホイヤー所有の方　ご自身で使用中のマシンを教えて頂けないでしょうかまた動作しそうなマシンをご存知の方でも結構です　商品名や品番等　教えて頂けないでしょうか
チューリングの停止性問題

チューリングの有名な停止性問題ですが、「全てのプログラムMと全てのデータIに対して、（１）M(I)が有限時間で停止するなら、H（M, I)は有限時間でYESを出力して停止する。（２）M(I)が無限ループに入って停止しないなら、H(M, I)は有限時間でNOを出力して停止する。ようなプログラムHは存在しない。」という趣旨だと思うのですが、人間（優秀なプログラマー）がM(I)を解読すれば、そのプログラムが有限時間で終わるか無限ループになるかは判断できるように思うのですが、この停止性問題はこの人間の判断もできないと言っているのでしょうか？それとも人間には判断できるが、それをプログラムに書いて機械に判断させることはできないといっているだけなのでしょうか？

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

みんなの回答

関連するQ&A

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

チューリングマシン

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

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

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

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

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

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

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

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

チューリング完全とは何か？

コンピューターサイエンスのチューリングとは何者なの

神の不存在証明

チューリング機械の状態遷移図

問題の意味がわかりません。。

巡回セールスマン問題: NPについて

人工生命に詳しい方教えて下さい

フィットネスマシーン

ワインディングマシーン

チューリングの停止性問題

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

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

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

みんなの回答

関連するQ&A

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

チューリングマシン

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

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

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

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

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

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

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

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

チューリング完全とは何か？

コンピューターサイエンスのチューリングとは何者なの

神の不存在証明

チューリング機械の状態遷移図

問題の意味がわかりません。。

巡回セールスマン問題: NPについて

人工生命に詳しい方教えて下さい

フィットネスマシーン

ワインディングマシーン

チューリングの停止性問題

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

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

チューリングマシン　　　　　　　　　　　　　　　

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

カテゴリ
一覧

専門家に質問してみよう
専門家登録