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.