R + S
Jump to navigation
Jump to search
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.
the code implicity loops.
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:
Counter
+
Rotate Right
RRRRRRR
Invert bit 1
R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRR
Bit 2 = bit 2 xor bit 1
RR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRR RRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRR
Bit 3 = Bit 3 xor (Bit 2 and Bit 1)
RRR++++++++++++++++++++++++++++++++RRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRR
RNG
Has a period of 256.
RRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRR++++++++++++++++++++++++++++++++++++++++++++++
Swap bits
#include <iostream>
#include <stdint.h>
#include <bit>
int bits = 8;
std::string genxor(int from, int to) {
std::string out = "";
if ((from == 0) & (to == 1)) {
for (int i = 2; i < bits; i++) {
out += "R";
}
for (int i = 0; i < (1 << bits) >> 2; i++) {
out += "+";
}
out += "R";
for (int i = 0; i < (1 << bits) >> 1; i++) {
out += "+";
}
out += "R";
return out;
}
if ((to - from + bits) % bits == 1) {
for (int i = from; i < bits; i++) {
out += "R";
}
out += genxor(0,1);
for (int i = 0; i < from; i++) {
out += "R";
}
return out;
}
throw -1;
}
std::string genswap() {
std::string out = "";
out += genxor(bits - 1,0);
for (int i = 0; i < bits-1;i++) {
out += genxor(i,i+1);
}
for (int i = bits - 3; i > 0;i--) {
out += genxor(i,i+1);
}
for (int i = 0; i < bits - 1;i++) {
out += genxor(i,i+1);
}
for (int i = bits - 3; i > 0;i--) {
out += genxor(i,i+1);
}
out += genxor(bits - 1,0);
return out;
}
int main()
{
std::string code = genswap();
std::cout << code;
}
generates code to swap first and last bit.
Result:
RRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR+++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRR R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++RRRRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++RRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR+++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR+++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRR++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRR RRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR+++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R+++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRRRRRRRRR+++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRRRRRRR+++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++R++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++RRRRRRRR
16 bit Example programs
RNG 2
RRRRRRRRR {+}19923 RRR {+}11957 RRRR {+}1
output is first bit
Period of 65536
Minimized RC4 (unfinished)
note: we would need only 12, or even 9 bits if we compress the S array into an integer 0-23. in the case of 12 bits however have no idea how the entries could then be swapped, and we would have to uncompute j which is only possible if S is valid (with no identical entries). in the case of 9, thats just not happening now is it.
Sketch:
Memory layout:
MSB LSB
| | | | | | | | | | | | | | | |
S[0] S[0] S[1] S[1] S[2] S[2] S[3] S[3] i i j j aux aux out out
1: uncompute output.
1.1 out -= S[aux]
1.1.1 rotate S left by aux
1.1.2 subtract S[0] from out
1.1.3 rotate S right by aux
1.2 aux -= S[i]
1.2.1 rotate S left by i
1.2.2 subtract S[0] from aux
1.2.3 rotate S right by i
1.3 aux -= S[j]
1.3.1 rotate the array left by j
1.3.2 subtract S[0] from aux
1.3.3 rotate the array right by j
2. increment i
3. j += S[i]
3.1 rotate S left by i
3.2 add S[0] to j
3.3 rotate S right by i
4. swap S[i] with S[j]
4.1 swap S[i] with aux
4.1.1 rotate S left by i
4.1.2 swap S[0] with aux
4.1.3 rotate S right by i
4.2 swap S[j] with out
4.2.1 rotate S left by j
4.2.2 swap S[0] with out
4.2.3 rotate S right by j
4.3 swap S[i] with out
4.3.1 rotate S left by i
4.3.2 swap S[0] with out
4.3.3 rotate S right by i
4.4 swap S[j] with aux
4.4.1 rotate S left by j
4.4.2 swap S[0] with aux
4.4.3 rotate S right by j
5. compute output.
5.1 add S[i] to aux
5.1.1 rotate S left by i
5.1.2 add S[0] to aux
5.1.3 rotate S right by i
5.2 add S[j] to aux
5.2.1 rotate S left by j
5.2.2 add S[0] to aux
5.2.3 rotate S right by j
5.3 add S[aux] to out
5.3.1 rotate S left by aux
5.3.2 add S[0] to out
5.3.3 rotate S right by aux
Extensions
Irreversible Hardware Variant
M Toggle first bit, Then if all bits apart from the LSB are set, toggle the MSB
D Toggle first bit, Then if all bits apart from the LSB are set, set the MSB
R rotates the value left by 1.
Irreversible Software Variant
+ Increment
0 If Register is One, set to zero
R rotates the value left by 1.
Every R + program is also valid in This variant.
Examples
Truth machine
(3 bit)
+++++0++R++RR
Output is first to second bits, 00 = 0, 01 = 1, 11 = space Instead of halting on zero it prints an infinite amount of Spaces
Reset register
(4 bit)
0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0
Reset first bit
(4 bit)
++0++0++0++0++0++0++0++0
bit 0 = bit 0 and bit 1
(4 bit)
++++0++++0++++0++++0
bit 0 = bit 0 or bit 1
(4 bit)
RR++++++++R++++++++R ++++0++++0++++0++++0 RRR++++++++R
Invert both inputs, and, invert output.
Shift right
(6 bit)
++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0++0 RRRRR
It's a zero bit and rotate right under the hood.
general PRNG
[ inverse output function ] [ state update function ] [ output function ]
Example: 7 bit
RRRRR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ RRR+++++++++++++++++++++++++++++++++++++++ RR++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++RRRRRR +++++++++++++++++++++++++RRRRR ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++RRRR +++RR
consists of a LFSR and a Nonlinear output transformation.
Syntatic sugar
It should be acceptable to, instead of writing the programs themselves write a program in any language to generate the code.
I am working on removing the Unusable for programming category. I will prove its use by implementing RC4 and a truth machine.
Alternitively, {x}n can be a repetition, for example {+}128
Minimality proof of 'R+' and 'R+0' (informal)
Multiplication of x and y is essentially applying x after y
Axiom: Every Sbox is either reversible or irreversible. Axiom: a Reversible Sbox multiplied by a Sbox is reversible iff the second Sbox is. Axiom: a Irreversible Sbox multiplied by Any Sbox is irreversible. Axiom: a Reversible Sbox Sbox multiplied by Any Sbox is irreversible. Proof: Two Sboxes A B can't generate arbitrary permutation X. Case 1: A is reversible and B is irreversible. If X is reversible you cant use B as it would be reversible. A alone cant generate X. Case 2: A is irreversible and B is reversible. Same as Case 1 but swap A and B Case 3: A is reversible and A is reversible. Cant generate X if irreversible Case 4: A is Ireversible and B is ireversible. Cant generate X if reversible