ResPlicate

From Esolang
(Redirected from Resplicate)
Jump to: navigation, search
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.

Thanks, User:boily! Thoily!

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)

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