Formal models for reversible computation; Measuring the degree of reversibility
Researchers
Armando Matos
-
Relate certain sub-classes of a reversible language with groups of integer tuple transformations
Primitive recursive functions can be characterized by a register language (LOOP) working with non-negative integers. Similarly a group G of (tuple) integer reversible transformations can be characterized by an integer register reversible language (SRL) which we introduced in 2003 [1]. Just as sub-classes of programs of LOOP have been shown to correspond exactly to well known classes of integer functions, we have also shown that SRL programs with FOR nesting at most 1 correspond exactly to the group of unimodular matrices.
Ongoing and future work:- Solve several computability questions associated with SRL programs, such as "is it decidable if two given SRL programs are equivalent?"
- Find natural descriptions of the sub-groups of (reversible) integer transformations which correspond to SRL programs with FOR nesting at most m for m>=2.
-
Towards a new definition of reversibility
(This is a recent topic of research; thus what is mentioned below is mainly "future work") Several computations previously considered reversible, such as Bennett's reversible Turing machine, involve the usage of arbitrarily large memory which is assumed to be initially blank; this memory is used to save the information lost during the (otherwise) irreversible computation. In these cases, the "setup" of the computation is highly non-reversible; we have for instance to erase a large number of cells of a tape. However, we think that the setup phase can not be ignored. In order to include the setup of the experiment, we propose to use other ways of measuring the irreversibility of a computation; one possibility is to assume that initially the entropy is maximum (K(x)=n) and define that, at any instant the reversibility is n-K(x) where x is the current configuration, n=|x| and K() is the Kolmogorov complexity function.
