ResPlicate
| Paradigm(s) | Post-like |
|---|---|
| Designed by | User:Quintopia |
| Appeared in | 2014 |
| Computational class | Turing complete |
| Reference implementation | See below |
| Influenced by | Muriel,Self-BCT |
| Influenced | Bauberqueue |
| File extension(s) | .res |
ResPlicate is a game/computational model/language/THING imagined by User:Quintopia in 2014. It is inspired by languages like Muriel and Self-BCT and the code-copying premise used by languages like ETAS and MiniMAX.
The Program/Data
A ResPlicate "program" is a sequence of finitely many nonnegative integers in a queue. Although any nonnegative integers are allowed, the only positive integers that will ever appear in the queue during execution are those that were there when the program started, so it is possible to do anything this automaton is capable of doing with only a finite subset of the integers.
The Process
At each step, x and then y is popped from the queue. Then, a sequence of x integers is popped from the queue in such a way that popping an empty queue yields 0 (zero). Finally, y copies of this sequence is pushed to the queue. Since this entire sequence happens every step, ResPlicate has only a single state.
Note: The word "step" always refers to this process throughout this article. The word "cycle" refers to the sequence of steps which brings a sequence of numbers just pushed back to the front of the queue. Since the queue may grow within each cycle, a single cycle may not contain a fixed number of steps.
The Name
The name of this language is a portmanteau of Slice, Replicate, and Splice, which is what the preceding process would be described as if the queue were DNA.
Examples
Some starting sequences will eventually delete themselves. For instance, any sequence which consists of nothing but 0s, 1s, and 2s, with no more than two 2s in a row, though this is not a necessary condition. Here's another self-deleting sequence:
32123
123123
12333
3333
330330330
0330033033033
30033033033
033033
3033
e
Or this one:
22112221
22211111
11112121
121211
21111
111
1
e
Sometimes even sequences which seem at first to be growing will eventually self-delete. For instance, the (hex) sequence 63A162F1 deletes itself after 168 steps, growing to a maximum length of 174, while (6 3 10 1 6 2 65 1) deletes itself after 1147 steps, reaching a max length of 614!
Other sequences will grow forever. For instance any sequence containing only numbers greater than 2 and of length at least 2 more than the largest such number will grow forever, though again, this is not necessary. For instance:
4321234
4212321232123
123212312321232
21231232123233
123212323323
21232332333
233233323
33323323232
323232323323323
2323323323323323
323323323323232323
3323323232323332332
23232323332332233233233
2323332332233233233232323
...
Other sequences will reach a steady state oscillation. The simplest oscillator is a string of at least four 2's, which will always remain the same, and this is somewhat of an attractor for sequences which do stabilize. For instance, (6 3 10 1 6 2 27 1) converges to the four-twos oscillator after 337 steps and (6 3 10 1 6 2 45 1) converges to the 204-twos oscillator after 1233 steps. However, other period lengths are possible. In fact, it is possible to create oscillators of any period. Here are some nice ones (indentations removed for length).
A short period 12 oscillator:
62816281 816281816281 8162818162 62818162 818162818162 6281628181 81816281816281 628181628181 8181818162818162 81816281818162 816281628181 8162816281 62816281 ...
The period-2 family of oscillators 43(4043)^k grows and shrinks by six every step:
434043 404340434043 434043 ...
This small sequence becomes a period 2 oscillator on the fourth step:
4242 42004200 0000420042 00420042 420042 00420042 ...
Other sequences grow forever, but nonmonotonically. For instance, the following evolves into a period-3 pattern that grows by three every third step:
62716380 716380716380 3806380716 80716063063063063063063063063 3063063063063063063 63063063063063 063063063063063063063063 3063063063063063063063 63063063063063063 063063063063063063063063063 3063063063063063063063063 63063063063063063063 ...
Noteworthy Patterns and Conjectures
- A sequence consisting only of at least four twos is a period 1 oscillator. No other period 1 oscillators exist.
- The entire family 6281(6k)281 seems to evolve into oscillators with periods of increasingly large multiples of 3, while the family 6281(6k+9)281 seems to always evolve into the all-twos oscillator. Conjecture: For x!=5, the sequence 6281x281 never grows without bound.
- The sequence 8 2 12 1 8 2 12 1 2k 1 evolves into a period five oscillator for k=1,2,3,4, a period 4 oscillator for k=6, a period 6 oscillator for k=8, a period 7 oscillator for k=9, and deletes itself for k=5,7,10,11,12,13,14,15,....
- The family 6 3 10 1 6 2 (2k) 1 for k at least 12 always becomes an oscillator of period k-1. The family 6 3 10 1 6 2 (2k+1) 1 shows unpredictable behavior, though most of them delete themselves. Many of these do so despite having long strings of twos. For instance, for k=46, at one point it becomes 78 2's followed by a single 1, yet eventually dies.
- The sequence 3 1 6 3 2 1 4 n eventually fills the queue with nothing but the numbers 0 and n. When n not in {2,4,5,7,8,9,10}, the 0's eventually disappear.
- The command sequence 4 2 x y 4 2 prepends x y to itself. More generally, the template n+2 2 {n numbers} n+2 2 prepends an arbitrary sequence of n numbers to itself.
- From this we can construct 4 2 4 2 4 2 4 2 a b c d which appends a b c d to itself.
- From this we can construct the prefix 4 2 4 2 4 2 4 2 0 x n 1 0 x n 1, which can be prepended to any length n sequence to make it self-preserving, including as a block inside a larger sequence (as long as it is not disturbed by the rest of the sequence).
- Based on this, here is a sequence which grows asymptotically as O(n1/2), and could also be modified to contain arbitrary sequences: 19 2 4 2 4 2 4 2 4 2 0 1 1 1 0 1 1 1 1 19 2
- And the block 4 2 4 2 4 2 4 2 0 x n+4 2 0 x n+4 2 n 0 {n numbers} 2n+24 2 will evolve into a sequence which appends two copies of itself to the queue every 6 cycles, but, unfortunately, not when included in a larger sequence.
- Combining two of the above, the block 4 2 (n+22) m 4 2 4 2 4 2 4 2 4 2 0 x n 1 0 x n 1 {n numbers} will after two cycles have turned into m copies of itself, and may be included inside a larger sequence.
- We can cause a command of length n to be executed every m cycles using the template n+2m+2 2 2(n+2m+1) 1 2(n+2m+1)-2 1 2(n+2m+1)-4 1 ... 2(n+2m+1)-2(m-1) 1 {n commands} n+2m+2 2
- No sequence with fewer than 3 numbers can avoid annihilation (obviously), and the first sequence (in shortlex order) which does not annihilate is 142. The first sequence which grows forever is 153. Conjecture: The first sequence which becomes an oscillator with period greater than one is 2242.
Alternative Versions
Input/Output
- Output can be added to the language by interpreting the pair 0 n to mean output the character with ASCII value n. Since 0 n would normally just be discarded, this has no effect on the normal behavior of a sequence. This extension suggested by User:Ais523. User:Oerjan wishes to point out that this deprives the output language of using 0 x for NOP padding, which is used in several of the above patterns. User:Quintopia answers that he has always found a workaround to any problem this would present in practice, (such as using 1 0 0 or 2 0 0 0 instead), that one can always let x be a non-printable character, and that it is unlikely there is a more fitting way to handle output within the language.
- Since the current interpreter treats negative counts identically to zero counts, negative counts can be used for out-of-band signalling for an input extension. One option is to let 0 -n accept a byte x of input and enqueue the digit x-n+1. Thus, the pair 0 -49 would correctly convert a numerical character to its corresponding digit in the queue. This extension based on a suggestion by User:Oerjan.
ResPairate-M
This language remains universal even with the restriction that sequences have even length and all numbers in odd positions are even. Sequences in this family will always evolve to other sequences in this family, and every pair of numbers will always be moved together as a block. Thus, with this restriction in place, it is possible to replace consecutive pairs of numbers 2n m in a ResPlicate program with new symbols (n,m). This will yield a program in a new language ("ResPairate") with the following semantics: In each cycle, a single symbol (n,m) is popped. Then a sequence of n symbols is popped and pushed m times. Since this language is equivalent to evaluating the original restricted ResPlicate program, it is also universal.
Since ResPlicate is universal when the repeat count m is bounded, ResPairate is also. The language in which m is required to be less than or equal to M shall be called ResPairate-M. ResPairate-2 has been proved universal.
Implementations
Python
As you might expect from the simplicity of ResPlicate, a simulator can be written in only a few lines of code. (A barebones Python interpreter is seven commands.) The following Python 2.6 code includes a number of different debug flags and the I/O extensions described above, and can be imported into other modules for experimental purposes.
#ResPlicate Interpreter by Quintopia, based on code by nooodl
from collections import deque
import sys
class PatternRepeated(LookupError):
def __init__(self, value):
self.value = value
def __str__(self):
return "Pattern repeated with period "+str(self.value)
def popsafe(q): # return 0 if empty #1
try: return q.popleft() #2
except IndexError: return 0 #3
def remember(q,count,prev = {},cyclenums = {}):
row = prev.setdefault(len(q),[])
copy = hash(tuple(q))
if copy in row: raise PatternRepeated(count-cyclenums[copy])
row.append(copy)
cyclenums[copy]=count
def run(q,haltonrepeat=True,quiet=True,prlen=False,maxlength=0,io=False,summary=False):
q= deque(q)
count = 0; maxl = len(q); repeat = 0
prev={}; cyclenums={}
nocheck = (io and min(q)<0) or not haltonrepeat
quiet = quiet or summary
try:
while len(q)>0 and (maxlength==0 or len(q)<=maxlength): #4
if len(q)>maxl: maxl=len(q)
if not quiet: print ' '.join(map(str, q)).join('()')
if prlen: print(len(q))
if not nocheck: remember(q,count,prev,cyclenums)
if summary: print ' '.join(map(str, list(q)[0:q[0]+2])).join('()')
x = popsafe(q); y = popsafe(q) #5,6
if io and x==0:
if y>=0:
try: sys.stdout.write(chr(y))
except ValueError: pass
else: q.append(ord(sys.stdin.read(1))+y+1)
else: q.extend([popsafe(q) for _ in xrange(x)] * y) #7
count+=1
if maxlength>0 and len(q)>maxlength:
if len(q)>maxl: maxl=len(q)
if not quiet: print ' '.join(map(str, q)).join('()')
if prlen: print(len(q))
except PatternRepeated as e: repeat = e.value
except KeyboardInterrupt: raise KeyboardInterrupt(list(q),count,maxl,repeat)
return (list(q),count,maxl,repeat)
if __name__=="__main__":
import optparse
parser = optparse.OptionParser(description="ResPlicate Interpreter by Quintopia.", usage="%prog [options] [arguments]")
parser.add_option('-n', help="Set the simulation to halt when the queue exceeds this length.", metavar="<value>", action="store", dest="maxlength", type=int, default=0)
parser.add_option('-q', '--quiet', help="Turn off verbose output.", dest="quiet", action="store_true", default=False)
parser.add_option('-l', help="Print the length of the queue at each step.", dest="prlen", action="store_true", default=False)
parser.add_option('-i', '--io', help="Run with I/O extension.", dest="io", action="store_true", default=False)
parser.add_option('-c', '--continue', help="Do not check for and halt on repeated/periodic sequences.", dest="haltonrepeat", action="store_false", default=True)
parser.add_option('-f', '--file', help="Load a ResPlicate program from a file.", metavar="<filename>", action="store", dest="filename", type=str, default=None)
parser.add_option('-o', '--command', help="Display only the numbers that were popped each cycle.", dest="summary", action="store_true", default=False)
(options, args) = parser.parse_args()
if options.filename is not None:
try: openfile = open(options.filename,"r")
except IOError: print("File '"+options.filename+"' not found.");
else: args = openfile.read().split(); openfile.close()
if len(args)>0:
if len(args)==1: args=args[0].split()
try: (final,count,maxl,repeat) = run(map(int, args),options.haltonrepeat,options.quiet,options.prlen,options.maxlength,options.io,options.summary)
except KeyboardInterrupt as e: print "Simulation interrupted by user."; (final, count, maxl, repeat) = e.args
except ValueError: parser.error("All arguments must be integers unless the -f flag is used to specify a file.")
if options.quiet:
if len(final)<100: print "Final sequence: "+' '.join(map(str, final)).join('()')
else: print "Final sequence: "+(' '.join(map(str,final[0:100]))+"...").join('()')
if repeat>0: print "Pattern repeated with period "+str(repeat)+"."
print "Simulation proceeded for "+str(count)+" steps, with queue reaching a maximum length of "+str(maxl)+" and a final length of "+str(len(final))+"."
else:
parser.error("No program to execute.")
Sample Output
$ python q.py 6 2 8 1 6 2 8 1 (6 2 8 1 6 2 8 1) (8 1 6 2 8 1 8 1 6 2 8 1) (8 1 6 2 8 1 8 1 6 2) (6 2 8 1 8 1 6 2) (8 1 8 1 6 2 8 1 8 1 6 2) (6 2 8 1 6 2 8 1 8 1) (8 1 8 1 6 2 8 1 8 1 6 2 8 1) (6 2 8 1 8 1 6 2 8 1 8 1) (8 1 8 1 8 1 8 1 6 2 8 1 8 1 6 2) (8 1 8 1 6 2 8 1 8 1 8 1 6 2) (8 1 6 2 8 1 6 2 8 1 8 1) (8 1 6 2 8 1 6 2 8 1) (6 2 8 1 6 2 8 1) Pattern repeated with period 12 Simulation proceeded for 12 steps, with queue reaching a maximum length of 16 and a final length of 8. $ python q.py -iqf cat.resp hi! hi! sup! sup! ^CSimulation interrupted by user. Final sequence: (4 2 0 -1 4 2 4 2 4 2 4 2 4 2 1 0 0 0 1 0 0 0) Simulation proceeded for 57 steps, with queue reaching a maximum length of 29 and a final length of 22. $ python q.py -qln 25 6 3 0 6 3 0 6 3 8 18 16 11 21 19 14 24 22 17 27 Final sequence: (0 6 3 0 6 3 0 6 3 0 6 3 0 6 3 0 6 3 0 6 3 0 6 3 0 6 3) Simulation proceeded for 10 steps, with queue reaching a maximum length of 27 and a final length of 27.
C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace resplicate
{
class Program
{
static Queue<ulong> q;
static List<string> mem;
static long longest;
static void Main(string[] args)
{
ulong steps = 0; longest = 0;
q = new Queue<ulong>();
mem = new List<string>();
foreach (string v in args)
{
ulong val;
if (ulong.TryParse(v, out val))
{
q.Enqueue(val);
}
else
{
return;
}
}
print_queue();
memorize();
do
{
while(!Console.KeyAvailable)
{
steps++;
ulong x = safe_dequeue(q);
ulong y = safe_dequeue(q);
ulong[] tmp = new ulong[x];
while(x > 0)
{
tmp[tmp.Length - (int)x] = safe_dequeue(q);
x--;
}
while(y > 0)
{
foreach (ulong v in tmp)
q.Enqueue(v);
y--;
}
print_queue();
if(memorize())
{
Console.WriteLine("Cycle detected");
break;
}
if (q.Count == 0)
break;
}
break;
} while (Console.ReadKey(true) == null);
Console.WriteLine("Steps {0}\nLongest {1}", steps, longest);
}
static void print_queue ()
{
Console.Write("( ");
foreach (ulong v in q)
Console.Write("{0} ", v);
Console.WriteLine(")");
}
static ulong safe_dequeue (Queue<ulong> q)
{
try
{
return q.Dequeue();
}
catch(InvalidOperationException e)
{
return 0;
}
}
static bool memorize ()
{
string _q = "";
foreach (ulong v in q)
_q = _q.Insert(_q.Length, v.ToString());
if (mem.Contains(_q))
return true;
mem.Add(_q);
longest = Math.Max(longest, q.Count);
return false;
}
}
}
Haskell
import qualified Data.Map as M main = interact $ unlines . interpret M.empty . map read . words interpret m k@(x:y:xs) | Just _ <- M.lookup k m = ["..."] -- Pattern repeated | (a,b) <- splitAt x $ xs ++ repeat 0 = unwords (show<$>k) : interpret (M.insert k () m) ( zipWith const (drop x xs) b ++ ([1..y]>>a) ) interpret _ _ = [] -- Less than 2 elements in queue
Sample Output
$ echo "6 2 8 1 6 2 8 1" | runhaskell Main.hs 6 2 8 1 6 2 8 1 8 1 6 2 8 1 8 1 6 2 8 1 8 1 6 2 8 1 8 1 6 2 6 2 8 1 8 1 6 2 8 1 8 1 6 2 8 1 8 1 6 2 6 2 8 1 6 2 8 1 8 1 8 1 8 1 6 2 8 1 8 1 6 2 8 1 6 2 8 1 8 1 6 2 8 1 8 1 8 1 8 1 8 1 8 1 6 2 8 1 8 1 6 2 8 1 8 1 6 2 8 1 8 1 8 1 6 2 8 1 6 2 8 1 6 2 8 1 8 1 8 1 6 2 8 1 6 2 8 1 ...
Useful Programs
The following programs are normal program type example things that use the I/O extensions described in the Alternate Versions section.
Cat
(Does not halt/delete itself on newline or EOF...that would be a much longer program.)
4 2 0 -1 4 2 4 2 4 2 4 2 4 2 1 0 0 0
Hello World
0 72 0 101 0 108 0 108 0 111 0 32 0 87 0 111 0 114 0 108 0 100 0 33 0 10
Truth-machine
0 -49 13 1 48 8 1 0 0 4 2 0 49 4 2 48 0
Powers of Two (in Unary)
6 2 0 48 8 2 6 2 6 2 0 10 8 1 6 2
Counting Up From Zero (in Unary) or Looping counter
8 2 4 2 0 48 4 2 8 2 4 2 0 10 4 2
ROT13 encoder/decoder
785 2
1 1 768
0 -1
3 256 769 0 0
769 1 767 1 0 0 1 0 1 1 0 2 1 0 3 1 0 4 1 0 5 1 0 6 1 0 7 1 0 8 1 0 9 1 0 10 1 0 11 1 0 12 1 0 13 1 0 14 1 0 15 1 0 16 1 0 17 1 0 18 1 0 19 1 0 20 1 0 21 1 0 22 1 0 23
1 0 24 1 0 25 1 0 26 1 0 27 1 0 28 1 0 29 1 0 30 1 0 31 1 0 32 1 0 33 1 0 34 1 0 35 1 0 36 1 0 37 1 0 38 1 0 39 1 0 40 1 0 41 1 0 42 1 0 43 1 0 44 1 0 45
1 0 46 1 0 47 1 0 48 1 0 49 1 0 50 1 0 51 1 0 52 1 0 53 1 0 54 1 0 55 1 0 56 1 0 57 1 0 58 1 0 59 1 0 60 1 0 61 1 0 62 1 0 63 1 0 64 1 0 78 1 0 79 1 0 80
1 0 81 1 0 82 1 0 83 1 0 84 1 0 85 1 0 86 1 0 87 1 0 88 1 0 89 1 0 90 1 0 65 1 0 66 1 0 67 1 0 68 1 0 69 1 0 70 1 0 71 1 0 72 1 0 73 1 0 74 1 0 75 1 0 76
1 0 77 1 0 91 1 0 92 1 0 93 1 0 94 1 0 95 1 0 96 1 0 110 1 0 111 1 0 112 1 0 113 1 0 114 1 0 115 1 0 116 1 0 117 1 0 118 1 0 119 1 0 120 1 0 121 1 0 122 1 0 97
1 0 98 1 0 99 1 0 100 1 0 101 1 0 102 1 0 103 1 0 104 1 0 105 1 0 106 1 0 107 1 0 108 1 0 109 1 0 123 1 0 124 1 0 125 1 0 126 1 0 127 1 0 128 1 0 129 1 0 130
1 0 131 1 0 132 1 0 133 1 0 134 1 0 135 1 0 136 1 0 137 1 0 138 1 0 139 1 0 140 1 0 141 1 0 142 1 0 143 1 0 144 1 0 145 1 0 146 1 0 147 1 0 148 1 0 149 1 0 150
1 0 151 1 0 152 1 0 153 1 0 154 1 0 155 1 0 156 1 0 157 1 0 158 1 0 159 1 0 160 1 0 161 1 0 162 1 0 163 1 0 164 1 0 165 1 0 166 1 0 167 1 0 168 1 0 169 1 0 170
1 0 171 1 0 172 1 0 173 1 0 174 1 0 175 1 0 176 1 0 177 1 0 178 1 0 179 1 0 180 1 0 181 1 0 182 1 0 183 1 0 184 1 0 185 1 0 186 1 0 187 1 0 188 1 0 189 1 0 190
1 0 191 1 0 192 1 0 193 1 0 194 1 0 195 1 0 196 1 0 197 1 0 198 1 0 199 1 0 200 1 0 201 1 0 202 1 0 203 1 0 204 1 0 205 1 0 206 1 0 207 1 0 208 1 0 209 1 0 210
1 0 211 1 0 212 1 0 213 1 0 214 1 0 215 1 0 216 1 0 217 1 0 218 1 0 219 1 0 220 1 0 221 1 0 222 1 0 223 1 0 224 1 0 225 1 0 226 1 0 227 1 0 228 1 0 229 1 0 230
1 0 231 1 0 232 1 0 233 1 0 234 1 0 235 1 0 236 1 0 237 1 0 238 1 0 239 1 0 240 1 0 241 1 0 242 1 0 243 1 0 244 1 0 245 1 0 246 1 0 247 1 0 248 1 0 249 1 0 250
1 0 251 1 0 252 1 0 253 1 0 254 1 0 255
787 1
785 2
Computational class
ResPlicate can be proven Turing-complete via simulating tag systems.
External resources
- Tag system to ResPlicate compiler (notes on the construction are also available)
- Tag system to ResPairate-2 compiler, with extensive design comments