ttp://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
ttp://en.wikipedia.org/wiki/Turing_machine
ttp://en.wikipedia.org/wiki/Non-deterministic_Turing_machine

チューリングマシンと非決定性チューリングマシンの違いは
遷移函数が一価か多価も許すかの違い。