![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
通常のチューリングマシンは1次元のテープで、ヘッドが右か左に動くのですが、
これを2次元、3次元・・・に拡張した場合のチューリングマシンについての議論を調べています。
(2次元の場合、平面上のセルでヘッドが東西南北に動くようものを想定しています)
いずれも、通常のチューリングマシンに還元可能されるとのことですが、
このあたりの議論や解説が載っている本、あるいはWebページがありましたら教えてください。
ついでに、ヘッドのアルファベット読み取り・書き込みが1個のデータでなくn個のデータの場合(テープが一本幅ではなくn本幅)にも通常のチューリングマシンに還元可能とのことですが、上記のn次元チューリングマシンでも通常のチューリングマシンに還元可能なのでしょうか。
数学は素人同然なので、質問が曖昧であることにはあらかじめ謝罪しておきます。
No.1ベストアンサー
- 回答日時:
n 次元のセルに番号を付けて、一列に並べなおせば、
ヘッドの移動を隣のセルに限定せず、「何マス右へ」
とかを許した拡張チューリング機会で実装できます。
この「何マス右へ」は、機会の内部状態として
「右へあと k マス移動中」という値を定義し、
その状態の時には、テープの読みを無視して
歩数をカウントダウンしながら移動を続ける
と定義すれば、通常のチューリング機会で実装できます。
テープを数本にすることについては、
アルファベットを旧アルファベットの
ベクトルがなす集合にすれば、ただちに実現されます。
No.2
- 回答日時:
ほぼ #1 と同じなんだけど....
とりあえず 2次元だけで考えます. 2次元の「テープ」は「座標 (a, b) にシンボル s がある」という形で表現できるので, これをずらっと並べて 1次元のテープができます (座標とシンボルを交互に並べる方が安全だと思う).
ヘッドの上下左右への移動はたとえば「右に動く = (a, b) から (a+1, b) に動く」という形に処理できるので, 座標を使えばヘッドの移動を追いかけられそう. 面倒なら 2テープ TM にして 2本目に「ヘッドの現在位置」を記録しておけばいい.
実際に TM を作るのは厄介だけどイメージはそれほど難しくなさそう.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
座標(x,y)間(=2点)の...
-
「原点に返る」と「原点に戻る...
-
同一円弧上の座標を求めたいの...
-
幾何ができる人の頭って
-
重分積分の極座標変換について
-
【数学】 解説の下から4行目が...
-
平板間の電気力線を複素ポテン...
-
「0でない2つのVのベクトルu,v...
-
座標
-
角度から楕円の座標を計算したい
-
高さh、幅wの長方形a,b,c,dがあ...
-
グラフが異なる2点でX軸の正の...
-
ある傾いた長方形の2点の座標を...
-
長方形を回転させたときの縦方...
-
遠近法の計算方法を教えてくだ...
-
大学の複素数の問題なんですが...
-
複素数平面についてです ①xy平...
-
円弧3点の座標から円の中心座...
-
数学の質問です 原点0から出発...
-
距離、方位角から座標を求める方法
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
座標(x,y)間(=2点)の...
-
重分積分の極座標変換について
-
右下の小さい数字について
-
楕円と回転行列について
-
「原点に返る」と「原点に戻る...
-
なぜベクトルの外積の向きが右...
-
距離、方位角から座標を求める方法
-
距離と方向角から座標を求める...
-
複素数平面についてです ①xy平...
-
三角関数 範囲が-πからπのとき...
-
「0でない2つのVのベクトルu,v...
-
測量座標と算数座標の違い
-
数学 絶対値
-
等角螺旋(らせん)の3次元的...
-
楕円の円周上の座標を求める計...
-
高校1年の数学なのですが 因数...
-
【数学】 解説の下から4行目が...
-
二つの球面が交わってできる円...
-
複素数平面と座標平面の対応に...
-
出題ミスだね?
おすすめ情報