質問: チューリングマシンに関して質問です。 現在チューリングマシンの計算能力に関して勉強していたのですが、 チューリングマシンと等価なアーキテクチャとしてn-テープのチューリングマシンは 1-テープのチューリングマシンでシミュレートできる、などのことを勉強しました。 そこでまた、「テープに一度しか書き込めない」チューリングマシンでも、 等価である、ということを知りました。 しかし、その方法がわかりません。 たしか、普通のチューリングマシンでは文字列をコピーする時は どこまで書き込んだかをチェックを文字列につけることで実行できたと思います。 しかし、このアーキテクチャではチェックのつけようがない訳ですから、 文字列のコピーさえままならない気がします。 コピーさえできればテープの右に新しい状態を次々に書き込んでいけばできそうなのですが。。。 わかる方、どうか詳しく解説していただけませんか?
回答: ご参考に http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%A...