通常のチューリングマシンは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で質問しましょう!
似たような質問が見つかりました
- 計算機科学 チューリングマシンの計算不可能なものは停止性問題以外にありますか? 1 2022/07/12 20:26
- Visual Basic(VBA) 表にフィルターをかけ、絞ったデータ(可視化セルのみ)を一次元配列として変数に入れるという動作を書きた 3 2023/06/16 00:31
- 宇宙科学・天文学・天気 四次元空間について 1 2022/07/01 17:11
- アニメ 四次元空間について 1 2022/07/01 16:06
- 物理学 ひも理論についての質問です。 ひも理論を調べてみると、元々素粒子を座標として表していた(便宜上)が、 5 2022/04/17 19:21
- Excel(エクセル) excelの列幅高さが勝手に変わる(特定のPCだけ) 8 2022/07/14 16:51
- 物理学 『四次元温度』 2 2022/05/09 11:07
- 物理学 相対性理論と円運動について。 1 2023/01/30 11:39
- 物理学 量子力学 生成消滅演算子 2 2022/08/04 23:17
- 政治 立憲・小川淳也議員「消費税は最低でも25%必要。所得税や相続税も強化して福祉国家に」 動画 http 8 2023/01/02 08:19
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
座標(x,y)間(=2点)の...
-
「原点に返る」と「原点に戻る...
-
画像の数学の問について。 最初...
-
座標を回転させる計算方法を教...
-
距離と方向角から座標を求める...
-
2次関数(数I)
-
二次関数 (2)のAB=2√3である...
-
距離、方位角から座標を求める方法
-
斜距離の算出公式はありますか?
-
数IIの「図形と方程式」の質問...
-
【数学】 解説の下から4行目が...
-
右下の小さい数字について
-
座標値 世界測地系と日本測地系...
-
複素数平面と座標平面の対応に...
-
楕円の円周上の座標を求める計...
-
三点を通る円の中心座標と半径...
-
高校1年の数学なのですが 因数...
-
二点の座標から角度を求めるには?
-
俯角のあるベクトル強度の求め方
-
メビウスの輪と複素数は関係な...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
座標(x,y)間(=2点)の...
-
「原点に返る」と「原点に戻る...
-
距離、方位角から座標を求める方法
-
距離と方向角から座標を求める...
-
複素数平面と座標平面の対応に...
-
y=(x-p)2+qの式はどういった場...
-
複素数平面についてです ①xy平...
-
媒介変数を使っての体積の出し...
-
楕円の角度とは?
-
N点間の中心と重心の求め方
-
重分積分の極座標変換について
-
なぜベクトルの外積の向きが右...
-
二点の座標から角度を求めるには?
-
ABの距離を求めよ。 A(-a,a) B(...
-
【数学】 解説の下から4行目が...
-
エクセルでグラフの作り方 軌...
-
楕円の円周上の座標を求める計...
-
「0でない2つのVのベクトルu,v...
-
数学Bの座標空間の問題
-
測量座標と算数座標の違い
おすすめ情報