>>295
横からつっこむけど，Turing機械Mはある入力xを受理しない場合は無限ループに突入しても問題ないはず。