可逆チューリングマシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

可逆チューリングマシン: Reversible Turing machine) は、その可能な動作の全てが可逆な動作であるチューリングマシンである。結果としてそれが行う計算は、可逆な計算となる。

構成法について説明する。通常の場合の多くの議論で対象とされているチューリングマシンは決定的である。すなわち(チューリングマシン#決定的と非決定的を参照)状態 q と、テープ上のヘッドの位置にある記号(以下、単に「記号」とする) s の組 (q, s) に対して、その時にすべき動作が唯一である。この時、動作した直後の状態と記号だけを見て、どのような動作をした直後かが決定できるなら、そのチューリングマシンは逆に動くことができるわけである。つまり「逆方向にも決定的」であるのが、可逆チューリングマシンである。

もう少し形式的には(チューリングマシンの形式的な記述には、普通は5ツ組を使うが、ここでは便宜上4ツ組に修正したものを使う)、

  • 状態 q で任意の記号の時は、状態 q' に遷移し記号を書き換えずに方向 d に動く、という規則を [q, /, d, q'] とする。
  • 状態 q 記号 s の時は、状態 q' に遷移し動かずに記号を s' に書き換える、という規則を [q, s, s', q'] とする。

このチューリングマシンの全ての規則のうちから任意の同じでない 2 個の規則 [q1, b1, c1, q'1] と [q2, b2, c2, q'2] を選んだ時に、

  • q1=q2 かつ ( b1=b2 または b1=/ または b2=/ ) が成立することがないチューリングマシンは決定的である。
  • さらに q'1=q'2 かつ ( c1=c2 または b1=/ または b2=/ ) が成立することもないチューリングマシンは可逆である。

可逆チューリングマシンは、すべての単射計算可能関数を計算できる。

参考文献[編集]