Small Universal Reversible Counter Machines

International audienceA k-counter machine (CM(k)) is an automaton with k counters as an auxiliary memory. It is known that CM(k) are universal for \\k\backslashge 2\\ . As shown by Morita reversible CM(2) are universal. Based on results from Korec we construct four small universal reversible counter machines highlighting different trade-offs: (10, 109, 129), (11, 227, 270), (9, 97, 116) and (2, 1097, 1568), where in parentheses we indicated the number of counters, states and instructions, respectively. Since counter machines are used in many areas, our results can be the starting point for corresponding reversible universal constructions