情報処理学会 第79回全国大会講演要旨

可逆プログラミング言語RWHILEの計算モデルは、万能可逆チューリング機械と同じ計算能力があるとされている。しかし、筆者の知る限りにおいて、その具体的な証明についてはこれまで報告が無かった。本稿では任意の可逆チューリング機械を、意味が同じRWHILEプログラムに変換できることを示す。このことにより、万能可逆チューリング機械のRWHILEプログラムが構成できることを示す。