ResPlicate

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
Category:Computational models
Category:2014
Category:Queue-based
Category:Turing complete
Category:Turing tarpits
Category:Implemented
Category:Self-modifying