>>27
宿題は自分で，と言いたいところだけど
大学の後輩だったらどうしようと思ったので一応説明してみるテスト。

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

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

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

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

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