可逆チューリングマシン（） とは、可逆計算を行うことができるチューリングマシンである。可逆チューリングマシンの構成法について説明する。一般のチューリングマシンは、通常決定的である。すなわち（チューリングマシン#決定的と非決定的を参照）状態 q と、テープ上のヘッドの位置にある記号（以下、単に「記号」とする） s の組 (q, s) に対して、その時にすべき動作が唯一である。この時、動作した直後の状態と記号だけから見て、どのような動作をした直後かが決定できるなら、そのチューリングマシンは逆に動くことができるわけである。つまり「逆方向にも決定的」であるのが、可逆チューリングマシンである。もう少し形式的には（普通は5ツ組を使うが、ここでは便宜上4ツ組に修正したものを使う）、このチューリングマシンの全ての規則のうちから任意の同じでない 2 個の規則 [q, b, c, q'] と [q, b, c, q'] を選んだ時に、可逆チューリングマシンは、すべての単射な計算可能関数を計算できる。

出典:wikipedia