人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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

●質問者: kabisuke
●カテゴリ:コンピュータ 学習・教育
✍キーワード:アーキテクチャ コピー シミュレート チューリングマシン テープ
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● ffmpeg
●60ポイント

ご参考に

http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%A...

◎質問者からの返答

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

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

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

示されてはいないです。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ