WORKS 2016-2019 - in construction
For those eventually interested:
the following list of papers and internal reports gives some idea
about current research topics.
2018
Armando B. Matos
Connecting total reversible programs
In this note we study some questions related to the connection of
bijective total “blocks”, which are SRL programs, in a tree. To one
of the nodes of the tree, as selected by the user, initial input
values are are assigned. Those blocks may correspond for instance to
SRL programs or to reversible digital circuits.
A tree of programs uses implicitly the copy operation. This cloning
is of course forbidden in a SRL program, but we show that its use
does not cause any inconsistency, because, as the tree has no loops,
what we get is a collection of parallel computations, that depend on
the tuple which is fixed.
2018
Luca Roversi, Luca Paolini, and Armando B. Matos
Enigma machines and the for/swap language
Consider the language ESRL and two of its sub-languages:
ForSwap (only for’s and swap’s and Enigma (only for’s and rotations).
We compare powers of finite permutations, pi^nn with n in N, with powers
of ForSwap sequences, Pr^n with n in N. For fixed input x it is shown
that the sequence Pr^n, n = 0, 1, . . . is periodic. The lengths of
the possible periods are studied. An upper bound on the maximum
number of possible configurations of a computation is established.
The possibility of implementing Enigma machines (which are inherently
reversible) in the language For-Swap is discussed.
2018
Luca Roversi Luca Paolini Armando Matos
<--! ptower.pdf -->
SRL transformations can grow as fast as any primitive recursive function
Also:
<--! tower2.pdf -->
Armando B. Matos1, Luca Roversi, and Luca Paolini
The maximum growth rates of primitive recursive functions
and of SRL transformations are essentially the same
An explicit construction of SRL programs that grow asymptotically
as fast as any primitive recursive program is described. In more
detail, we show that for every positive integer k there is a SRL
program such that, if some register are initialised with n and the
others with zero, the final contents k of any register exceeds 2^(k)n
(Knuth's notation, [Knu76]).
It is known that, for every k >= 0, the function f_k(n) = 2^(k)n is
primitive recursive (PR), and that the function g(k,n) = 2^(k)n is
not PR (the binary k-2 Ackermann function is
a(k,n) = [2^(k-2)(n+3)] - 3). Thus, in terms of this k-hierarchy, the
final values of the registers of SRL computations can be as large as
any PR function.
As it is possible to simulate a SRL computation by a Loop program,
representing integers x in Z by a pair non-negative integers, the
final contents of registers of SRL computation can be exactly as large
as the values of primitive recursive functions.
2019
Luca Roversi, Luca Paoli, and Armando Matos
The usefulness of a
reduction: from Diophantine equations to SRL fixed points
2019
(Slides)
Armando B. Matos
Forward/backward SRL machines -
Changing the time direction in reversible computations
Define a possible computation machine for SRL programs.
The machine
- uses a finite number of registers;
- has a tree-like structure;
- represents the instantaneous configuration of the computation;
- has a user controlled forward/backward time switch;
- may eventually be useful for a reversible physical implementation.