|
可逆チューリングマシン（） とは、可逆計算を行うことができるチューリングマシンである。 可逆チューリングマシンの構成法について説明する。一般のチューリングマシンは、通常決定的である。すなわち（チューリングマシン#決定的と非決定的を参照）状態 q と、テープ上のヘッドの位置にある記号（以下、単に「記号」とする） s の組 (q, s) に対して、その時にすべき動作が唯一である。この時、動作した直後の状態と記号だけから見て、どのような動作をした直後かが決定できるなら、そのチューリングマシンは逆に動くことができるわけである。つまり「逆方向にも決定的」であるのが、可逆チューリングマシンである。 もう少し形式的には（普通は5ツ組を使うが、ここでは便宜上4ツ組に修正したものを使う）、 * 状態 q で任意の記号の時は、状態 q' に遷移し記号を書き換えずに方向 d に動く、という規則を /, d, q' とする。 * 状態 q 記号 s の時は、状態 q' に遷移し動かずに記号を s' に書き換える、という規則を s, s', q' とする。 このチューリングマシンの全ての規則のうちから任意の同じでない 2 個の規則 b1, c1, q'1 と b2, c2, q'2 を選んだ時に、 * q1=q2 かつ ( b1=b2 または b1=/ または b2=/ ) が成立することがないチューリングマシンは決定的である。 * さらに q'1=q'2 かつ ( c1=c2 または b1=/ または b2=/ ) が成立することもないチューリングマシンは可逆である。 可逆チューリングマシンは、すべての単射な計算可能関数を計算できる。 == 参考文献 == * 森田憲一「計算における可逆性 : 可逆チューリング機械と可逆論理回路」 『情報処理』Vol. 35, No. 4, pp. 306～314, (1994), 情報処理学会 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「可逆チューリングマシン」の詳細全文を読む スポンサード リンク
|