- ベストアンサー
※ ChatGPTを利用し、要約された質問です（原文：チューリングマシン テープのn次元拡張について ）
チューリングマシンのn次元拡張について
このQ&Aのポイント
- 通常のチューリングマシンは１次元のテープで、ヘッドが右か左に動くのですが、２次元や３次元に拡張した場合のチューリングマシンについての議論や解説の本やWebページを教えてください。
- また、テープの幅が１本幅ではなくｎ本幅で、ヘッドが複数のデータを読み書きできる場合についても通常のチューリングマシンに還元可能なのか教えてください。
- 質問が曖昧であることに謝罪しながら、このような拡張されたチューリングマシンに関する議論や解説について教えてください。
- riven（@leleleplus）
- お礼率36% (21/57)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
n 次元のセルに番号を付けて、一列に並べなおせば、 ヘッドの移動を隣のセルに限定せず、「何マス右へ」 とかを許した拡張チューリング機会で実装できます。 この「何マス右へ」は、機会の内部状態として 「右へあと k マス移動中」という値を定義し、 その状態の時には、テープの読みを無視して 歩数をカウントダウンしながら移動を続ける と定義すれば、通常のチューリング機会で実装できます。 テープを数本にすることについては、 アルファベットを旧アルファベットの ベクトルがなす集合にすれば、ただちに実現されます。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
回答No.2
ほぼ #1 と同じなんだけど.... とりあえず 2次元だけで考えます. 2次元の「テープ」は「座標 (a, b) にシンボル s がある」という形で表現できるので, これをずらっと並べて 1次元のテープができます (座標とシンボルを交互に並べる方が安全だと思う). ヘッドの上下左右への移動はたとえば「右に動く = (a, b) から (a+1, b) に動く」という形に処理できるので, 座標を使えばヘッドの移動を追いかけられそう. 面倒なら 2テープ TM にして 2本目に「ヘッドの現在位置」を記録しておけばいい. 実際に TM を作るのは厄介だけどイメージはそれほど難しくなさそう.
