チューリングマシンのn次元拡張について
- 通常のチューリングマシンは１次元のテープで、ヘッドが右か左に動くのですが、２次元や３次元に拡張した場合のチューリングマシンについての議論や解説の本やWebページを教えてください。
- また、テープの幅が１本幅ではなくｎ本幅で、ヘッドが複数のデータを読み書きできる場合についても通常のチューリングマシンに還元可能なのか教えてください。
- 質問が曖昧であることに謝罪しながら、このような拡張されたチューリングマシンに関する議論や解説について教えてください。
- ベストアンサー
チューリングマシン テープのn次元拡張について
通常のチューリングマシンは１次元のテープで、ヘッドが右か左に動くのですが、 これを２次元、３次元・・・に拡張した場合のチューリングマシンについての議論を調べています。 （２次元の場合、平面上のセルでヘッドが東西南北に動くようものを想定しています） いずれも、通常のチューリングマシンに還元可能されるとのことですが、 このあたりの議論や解説が載っている本、あるいはＷｅｂページがありましたら教えてください。 ついでに、ヘッドのアルファベット読み取り・書き込みが１個のデータでなくｎ個のデータの場合（テープが一本幅ではなくｎ本幅）にも通常のチューリングマシンに還元可能とのことですが、上記のｎ次元チューリングマシンでも通常のチューリングマシンに還元可能なのでしょうか。 数学は素人同然なので、質問が曖昧であることにはあらかじめ謝罪しておきます。
- riven（@leleleplus）
- お礼率36% (21/57)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
n 次元のセルに番号を付けて、一列に並べなおせば、 ヘッドの移動を隣のセルに限定せず、「何マス右へ」 とかを許した拡張チューリング機会で実装できます。 この「何マス右へ」は、機会の内部状態として 「右へあと k マス移動中」という値を定義し、 その状態の時には、テープの読みを無視して 歩数をカウントダウンしながら移動を続ける と定義すれば、通常のチューリング機会で実装できます。 テープを数本にすることについては、 アルファベットを旧アルファベットの ベクトルがなす集合にすれば、ただちに実現されます。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
ほぼ #1 と同じなんだけど.... とりあえず 2次元だけで考えます. 2次元の「テープ」は「座標 (a, b) にシンボル s がある」という形で表現できるので, これをずらっと並べて 1次元のテープができます (座標とシンボルを交互に並べる方が安全だと思う). ヘッドの上下左右への移動はたとえば「右に動く = (a, b) から (a+1, b) に動く」という形に処理できるので, 座標を使えばヘッドの移動を追いかけられそう. 面倒なら 2テープ TM にして 2本目に「ヘッドの現在位置」を記録しておけばいい. 実際に TM を作るのは厄介だけどイメージはそれほど難しくなさそう.
関連するQ&A
- チューリングマシンとオートマトンでできることの違い
チューリングマシンとオートマトンでできることの違いは、具体例で言うとどういうことでしょうか？ 計算理論の本を一生懸命読んでいて、数式が多くてまだ完全に理解できてないのですが、私の理解した範囲で書くと、 ●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」 ですよね。 そして、ネットで調べると、「オートマトン」の例として自動販売機があって、これは非常に理解できました。 「チューリングマシン」の例としてはコンピュータがあって、これはこれで理解できました。 しかし、自動販売機にできなくてコンピュータにできること、の違いがよく分かりません。自動販売機にテープをつけると具体的にどういうメリットがあるのでしょうか？ 他の例でも良いので、チューリングマシンとオートマトンでできることの違いを具体例で教えていただけると幸いです。 ぜひ、よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- チューリングマシンの状態数について
この質問で言うチューリングマシンは、 「使用できる文字が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が計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。 よろしくお願いいたします。 ((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)
- ベストアンサー
- C・C++・C#
- アドレス格納のための二次元配列のメモリ動的確保
アドレス格納のための二次元配列のメモリ動的確保 二次元配列のためにメモリを動的確保しなければならないのですが、 その配列に格納したいものが 「DATA型のポインタ」です。（DATA型はtypedefした構造体です。） プログラム実行中にmallocで確保した、数あるDATA型の構造体の、その先頭アドレスを リストアップするための配列です。 この場合、どのような形でmallocすればよいのでしょうか？ 教えていただけるとありがたいです。よろしくお願いいたします。 -- たとえば ｍ×ｎ のint型の配列は、 ◆ int *i; ◆ i = (int *)malloc( m * n * sizeof(int) ); となりますよね。 この要領がでやるのが一般的にわかりやすいものだとするならその方法でやりたい （後発の人が自分のソースコードを読む可能性があるため）のです。 -- 同様にｍ×ｎの「DATA型のポインタを格納するための二次元配列」を動的確保したい場合、 ◆ DATA *d; ◆ d = (DATA *)malloc( m * n * sizeof(DATA) ); この文にどのように付け加えたら良いのでしょう？ もうあと一歩な気がするのですが（笑）。しかし参考書等で勉強しましたがわかりませんでした・・・。 わかる方、どなたかよろしくお願いいたしますm(_ _)m あとこれだけ通ればコンパイルが通るんです!!!!! たぶん（笑）
- ベストアンサー
- C・C++・C#
- チューリングマシン
チューリングマシン 現在の状態 0 0 0 0 1 1 1 読んだ文字 0 1 X □ 0 0 1 ーーーーーーーーーーーーーーーー...以下略 次の状態 1 2 0 終 1 3 1 書く文字 □ □ □ □ ０ X X 移動方向 右 右 右 右 左 右 「０」「１」が連続して書かれていて、調べたい０，１の前後は□になっています。 左から一文字ずつ消していき、その際左端が０なら１を、１なら０を1つ消す。 このチューリングマシンは、このようにして「０」「１」の数がちょうど等しいかどうかを調べるものらしいのですが、どうして次の状態に２，３がでてくるのか?また、なぜ左に戻ったりするのか？などいまいちよくわかりません。 詳しく載っているサイトか、説明をお願いします。
- 締切済み
- 数学・算数
- チューリングマシンについて
計算理論の勉強をしています。 チューリングマシンが、ある言語を「判定する」というのと「認識する」ということの違いがよくわかりません。 どなたか解説していただけないでしょうか。
- ベストアンサー
- 数学・算数
- チューリングマシンについて
Σ={0,1}の2-tape 決定性チューリングマシンの動きを、 1-tape 決定性チューリングマシンでシミュレートするにはどうすればよいか？ quintuples で説明せよ。 という問題なのですが、どう解けばいいのか分かりません。 どなたか分かる方、よろしくお願いします！
- 締切済み
- 数学・算数
- C++ 数値データファイルから2次元配列への格納法
C++ 初心者です。 以下のような半角スペースと+ 又は - の符号付きの数値データファイル"data"を読み込んで2次元配列に収納するプログラムを教えて頂きたいです。 (アンダーバー"_"で、半角スペースを表します) ___-10.2__20.1_ _30.3___________-50.3___ ______3.1____-9.2__ なお、C++の参考書に、「通常の配列はあらかじめサイズを決めて作成しなければならないが、vectorにはメモリが許す範囲でいくつでも要素を追加できる」と書いてあり、この点を活かしたプログラムを作成したいので、最初にデータ数を決めないで、データファイルの最後にくるまで読み込めるようなプログラムにしたいです。 プログラム中で、 for 又は while () { ___________for 又は while() { ______________________cout << "n[" << i << "][" << j << "]= " << n[i][j] << endl; ___________} } のように記述して以下のように出力されるようにしたいです。 n[0][0]= -10.2 n[0][1]= 20.1 n[1][0]= 30.3 n[1][1]= -50.3 n[2][0]= 3.1 n[2][1]= -9.2 すみませんが、わかる方がいらっしゃいましたら、宜しくお願いします。
- ベストアンサー
- C・C++・C#
- テープへのバックアップについて
テープへのバックアップについての質問です。 本日、テープへのバックアップを行いました。 計画性のなさを反省して、今質問をしているところです。 やりたかったことは、システムバックアップ＋rawデバイスのバックアップです。 （システムバックアップは必須でrawデバイスのバックアップは必ずしも必須ではない） 以下の手順で行いました。 まず、システムバックアップを取るために以下のコマンドを投入。 ufsdump 0ucf /dev/rmt/0n / ufsdump 0ucf /dev/rmt/0n /usr ・ ・ ・ ufsdump 0ucf /dev/rmt/0n /opt そして、次にrawデバイスのバックアップを取るために以下のコマンドを投入。 dd if="rawデバイス名" of=/dev/rmt/0n ところが、rawデバイスの容量はそれほど大きくないのに、1時間半たっても終わりません。 時間的な制約があったのとバックアップが取れていないんじゃないかと思い、途中でctrl+Cで強制終了して終えてしまいました。 （結果的にはctrl+C投入後、inとoutのサイズが表示されたのでバックアップが取れていたのでしょうか？？） 後で調べてわかったのですが、基本的にrawデバイスのバックアップをテープに取得する場合は、「rawデバイス１つ：テープ１本」という１：１対応が基本ということでよろしいでしょうか？ そこで、質問です。 今回、システムバックアップを取ったあとに、同じテープに続けてrawデバイスのバックアップを取ろうとして途中で終えてしまいました。 この場合、テープ内のシステムバックアップのデータは有効なのでしょうか？（つまり、正常にリストア可能な状態にあるのかどうかということ） システムバックアップを取ったあとに、ddコマンドをうってしまったのでシステムバックアップデータが上書きされていないか心配です。 やはり、再度システムバックアップを取り直した方が無難でしょうか？ （時間的な制約があり、できれば再度取り直しは避けたいのですが・・・） 以上です。 わかりにくい質問で申し訳ございませんが、知識をお持ちの方ご回答よろしくお願い致します。
- ベストアンサー
- Solaris系OS
- PHP で Excel を2次元配列で取出したい
PHP で Excel ファイルのデータを取り出して、単純な２次元配列にしたいのですが、なかなかうまく行かず、ここ２～３日、はまっています。サポートをお願い頂けたら幸いです。 ＜これまでやった事＞ ・ネット情報を参考に、phpspreadsheet が使える環境にし必要処理を実施後、以下のように rangeToArray 関数を使い、 print_r で中身を見ると、エクセルの A1 から N7 まで、連想配列として取り出されます。 $data = $sheet->rangeToArray("A1:N9"); print_r($data); 連想配列の型式で、 Array ( [0] => Array ( [0] => (A1 のデータ）[1] => (A2 のデータ）..... [12] => (A13のデータ）) [1] => Array ( [0] => （A2のデータ） [1] =>（B2のデータ）....... が表示されます。 しかし私には以下のような単純な２次元配の方が理解しやすいので、 $data[0][0] ならば A1 のデータ、$data[12][0] ならば A13 のデータ、 $data[2][6] ならば C7 のデータを意味し、 例えば、C1 に「コスト」 というタイトル名が表示されている場合、 $cost = $data[2][0]; で C1 の内容を $cost という変数に入れたいのですが、どうすれば良いのでしょうか？ なお、現在は、$data 変数に添え字 [0][5] を入れると文法エラーでます。 ちなみに、私は連想配列の理解に追いついていけないほど、PHP の初心者です。 以上、コメントを頂けたら幸いです。よろしくお願いいたします。
- ベストアンサー
- PHP
- テープオートローダーへのバックアップ
Symantec Veritas Backup Exec9.0でテープオートローダー（Power Vault 122T）へのバックアップを検討しております。 素朴な疑問なのですが、仮にテープ1本あたり80GBの容量があるとして、バックアップデータが100GBあるとき、自動的に複数本のテープに分けてバックアップをとってくれるのでしょうか？ そうでない場合、Backup Exec側で何を設定すればよいでしょうか…。
- ベストアンサー
- その他（ITシステム運用・管理）
