R + S

R+S is a very simple esoteric programing language.
It is reversible and can't be turing complete because it cant have infinite memory. its only memory is a finite width register of some arbitrary amount of bits.

it can simulate all reversible n to n mappings because it can simulate X,CX,CCX, etcetera.

it can simulate all irreversible n/2 to n/2 mappings because it can leave the input in one half and generate the output from it.

Instructions:

+ increments the value. (wrapping)
R rotates the value left by 1.
Sswaps the first and second bit of the value.

the S instruction is redundant, it can be replaced by xors and rotations.

8 bit Example programs:

Rotate Right

RRRRRRR

Invert bit 1

R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRR

Bit 2 = bit 2 xor bit 1

RR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ RRRRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRR

RNG

If you keep running it you will get a period of 256. RRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRR++++++++++++++++++++++++++++++++++++++++++++++

Swap bits

#include <iostream>
int bits = 6;

std::string genxor(int from, int to) {
	std::string out = "";
    
	if (from == 0 & to == 1) {
		for (int i = 0; i < from; i++) {
			out += "R";
		}
		out += "RR";
		for (int i = 0; i < (1 << bits) >> 2; i++) {
			out += "+";
		}
		for (int i = 0; i < bits - 1; i++) {
			out += "R";
		}
		for (int i = 0; i < (1 << bits) >> 1; i++) {
			out += "+";
		}
		for (int i = 0; i < bits - 1; i++) {
			out += "R";
		}
		return out;
	}
	if ((to - from + bits) % bits == 1) {
		for (int i = 0; i < (bits - from) % bits; i++) {
			out += "R";
		}
		out += genxor(0,1);
		for (int i = 0; i < from; i++) {
			out += "R";
		}
		return out;
	}
    out += genxor(from,to - 1);
    out += genxor(to - 1, to);
    out += genxor(from,to - 1);
    out += genxor(to - 1, to);
    return out;
}

std::string genswap() {
    std::string out = "";
    out += genxor(bits - 1,0);
    out += genxor(0,bits - 1);
    out += genxor(bits - 1,0);
    return out;
}

int main()
{
    std::cout << genswap();
}

generates code to swap first and last bit.

Cant show result, its 40960 characters for 8 bits