プロが教える店舗&オフィスのセキュリティ対策術

通常のチューリングマシンは1次元のテープで、ヘッドが右か左に動くのですが、
これを2次元、3次元・・・に拡張した場合のチューリングマシンについての議論を調べています。
(2次元の場合、平面上のセルでヘッドが東西南北に動くようものを想定しています)

いずれも、通常のチューリングマシンに還元可能されるとのことですが、
このあたりの議論や解説が載っている本、あるいはWebページがありましたら教えてください。

ついでに、ヘッドのアルファベット読み取り・書き込みが1個のデータでなくn個のデータの場合(テープが一本幅ではなくn本幅)にも通常のチューリングマシンに還元可能とのことですが、上記のn次元チューリングマシンでも通常のチューリングマシンに還元可能なのでしょうか。

数学は素人同然なので、質問が曖昧であることにはあらかじめ謝罪しておきます。

A 回答 (2件)

n 次元のセルに番号を付けて、一列に並べなおせば、


ヘッドの移動を隣のセルに限定せず、「何マス右へ」
とかを許した拡張チューリング機会で実装できます。
この「何マス右へ」は、機会の内部状態として
「右へあと k マス移動中」という値を定義し、
その状態の時には、テープの読みを無視して
歩数をカウントダウンしながら移動を続ける
と定義すれば、通常のチューリング機会で実装できます。

テープを数本にすることについては、
アルファベットを旧アルファベットの
ベクトルがなす集合にすれば、ただちに実現されます。
    • good
    • 0

ほぼ #1 と同じなんだけど....



とりあえず 2次元だけで考えます. 2次元の「テープ」は「座標 (a, b) にシンボル s がある」という形で表現できるので, これをずらっと並べて 1次元のテープができます (座標とシンボルを交互に並べる方が安全だと思う).

ヘッドの上下左右への移動はたとえば「右に動く = (a, b) から (a+1, b) に動く」という形に処理できるので, 座標を使えばヘッドの移動を追いかけられそう. 面倒なら 2テープ TM にして 2本目に「ヘッドの現在位置」を記録しておけばいい.

実際に TM を作るのは厄介だけどイメージはそれほど難しくなさそう.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!