5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

計算機科学の質問はここでしろ!

28 :名無しさん@お腹いっぱい。:2006/09/23(土) 12:21:13 ID:xSlS4u2k0
>>27
宿題は自分で,と言いたいところだけど
大学の後輩だったらどうしようと思ったので一応説明してみるテスト。

2テープTuring機械Mを元に新しい1テープ9記号Turing機械M'を作るとき
一番大事なところを説明してみる。
入力文字列の長さをn, Γ={1,2,3,4,5,6,7,8,#}としよう。
iを自然数として,M'のテープの中身は以下のように作る。

元テープ1のiマス目の記号:aaabbb###
元テープ2のiマス目の記号:ab#ab#ab#
 ↓
新テープ のiマス目の記号:12345678#

あとはMの1ステップをシミュレーションするのに
M'がnステップかけていいならシミュレーションできそうでそ。

きちんとした証明にするには最初と最後はどうするかとか
いろいろあるけど,本質的な部分はこれだけ。

結果だけ聞けばインチキくさいと思うかもしれないが,
そのインチキくさい手法は誰にでも思いつけるわけじゃないってことで。




19 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)