チューリングマシンに関して質問です。


現在チューリングマシンの計算能力に関して勉強していたのですが、
チューリングマシンと等価なアーキテクチャとしてn-テープのチューリングマシンは
1-テープのチューリングマシンでシミュレートできる、などのことを勉強しました。

そこでまた、「テープに一度しか書き込めない」チューリングマシンでも、
等価である、ということを知りました。
しかし、その方法がわかりません。
たしか、普通のチューリングマシンでは文字列をコピーする時は
どこまで書き込んだかをチェックを文字列につけることで実行できたと思います。
しかし、このアーキテクチャではチェックのつけようがない訳ですから、
文字列のコピーさえままならない気がします。
コピーさえできればテープの右に新しい状態を次々に書き込んでいけばできそうなのですが。。。
わかる方、どうか詳しく解説していただけませんか?

回答の条件
  • 1人2回まで
  • 登録:2008/01/23 14:44:59
  • 終了:2008/01/27 20:06:21

回答(1件)

id:ffmpeg No.1

ffmpeg回答回数1202ベストアンサー獲得回数92008/01/25 03:38:38

id:kabisuke

ご回答ありがとうございます。

しかし、さすがにwikipediaの内容は調べてあります。

この記事には一回書き込みTMが通常のTMと等価である事は

示されてはいないです。

2008/01/25 07:32:45
  • id:punkaholic
    punkaholic 2008/01/26 00:00:04
    答えではないのでコメントで失礼します.
    "write once turing machine"とかでぐぐると
    http://www.cs.ucr.edu/~neal/2004/cs215/wikidb/uploads/xxx_hw3sol.pdf
    とかが見つかります.で,これは前に挙げたSipserの本の練習問題の解答のようです(原著第一版では3.10).

    「計算論の基礎」は解答がついている,と聞いたことがあるので,日本語版にアクセスできるのならそれをみれば書いてあるかもしれません.

    ...自分できちんと理解する元気がないので↑の極概要だけ抜き出すと
    -「2回」書き込みのみのTMは通常のTMと等価であることを示す.方法:一つの動作をするたびに入力を新しくコピーする(コピーするために二回の書き込みが必要??).
    -これをさらに一回書き込みのTMに変換する.方法:一つのセルを二つでシミュレートする(片方は一回目の書き込みよう,もう片方は二回目用)
    という感じのようです.
  • id:kabisuke
    前回の質問から再度ありがとうございます。
    なるほど、これは丁度私が求めていた問題そのものですね。
    英語力が無いので少し解釈に自身は無いのですが、
    テープを状態保存用と書き込み用と二倍に使って、
    右にガンガン増やしていけばいい、ということみたいですね。

    ・・・ということは
    テープの初めの入力部分は書き込んでもいいって解釈できるんですかね。
    つまるところ。。。

    |a|b|c| | | | | | | | | | |
    と入力があったら
    |a+|b+|c+|#|a*| |b| |c| |#| | |
    のようにいちどコピーして始めてしまえば、
    (+はコピーのときに使うチェック、*はヘッドの位置の記憶用)
    あとは状態遷移関数に基づいて#の横に新しい状態をコピーする
    (二回目以降のコピーのためのチェックはまだ書き込んでいない空白を利用)
    ようにすればいける、と。

    ちなみにSipser本の日本語版、図書館から借りてみてみたところ
    日本語の解答はついていませんでした。。。
    日本語での問題の記述はこうです。

    3.10
    一度書き込みチューリング機械(write-once Turing machine)は、各々のテープのマス目(テープの入力部分を含む)を高々一回だけ変更できる単一テープTMである。Turing機械モデルのこの変形は、普通のTuring機械モデルと等価であることを示せ。
  • id:punkaholic
    punkaholic 2008/01/27 19:54:20
    >入力部分への書き込み
    そうみたいですね.入力自体はTMがおこなうものではないので,ということでしょうか,たぶん.
  • id:kabisuke
    英語の問題を見ても入力部分を書き換えてよい、
    とおそらく解釈できるのでこの考え方でよさそうです。
    ありがとうございました。この質問は打ち切ります。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません