Output every halting program (write a parallel interpreter)

Question

The goal of this challenge is to (eventually) output every possible halting program in a language of your choice. At first this may sound impossible, but you can accomplish this with a very careful choice of execution order.

Below is an ASCII diagram to illustrate this. Let the columns represent a numbering of every possible program (each program is a finite number of symbols from a finite alphabet). Let each row represent a singular step in execution of that program. An X represent the execution performed by that program at that time-step.

 step#  p1 p2 p3 p4 p5 p6
     1  X  X  X  X  X  X
     2  X  X  X  X  X  
     3  X  X     X  X
     4  X  X     X  X
     5  X  X     X
     6     X     X
     7     X     X
     8     X     X
     9     X     X
     ∞     X     X

As you can tell, programs 2 and 4 don't halt. If you were to execute them one-at-a-time, your controller would get stuck in the infinite loop that is program 2 and never output programs 3 and beyond.

Instead, you use a dovetailing approach. The letters represent a possible order of execution for the first 26 steps. The *s are places where that program has halted and is outputted. The .s are steps that haven't been executed yet.

 step#  p1 p2 p3 p4 p5 p6
     1  A  C  F  J  N  R  V
     2  B  E  I  M  Q  *  Z
     3  D  H  *  P  U
     4  G  L     T  Y
     5  K  O     X
     6  *  S     .
     7     W     .
     8     .     .
     9     .     .
     ∞     .     .

Requirements for the target language

The target language (the one being parallel-interpreted) must be Turing-complete. Other than that, it can be any language that's Turing-complete, including Turing-complete subsets of much larger languages. You are also free to interpret things like cyclic tag system rules. You are also allowed to create a language to test, as long as you can show why it is Turing-complete.

As an example, if you choose to test brainfuck, then it is best to test just the []-+<> subset, since input is not supported and output is just thrown away (see below).

When it comes to the "controller" program (which you are golfing), there's no special requirements. Normal language restrictions apply.

How to create an infinite list of programs

The majority of programming languages can be represented as a series of symbols from a finite alphabet. In this case, it is relatively easy to enumerate a list of every possible program in order of increasing length. The alphabet you use should be representative of the requirements of the target language. In most cases, this is printable ASCII. If your language supports Unicode as an additional feature, you should not test every possible combination of Unicode characters, just ASCII. If your language only uses []-+<> then don't test out the various combinations of "comment" ASCII characters. Languages like APL would have their own special alphabets.

If your language is best described in some non-alphabetic way, like Fractran or Turing Machines, then there are other equally valid methods of generating a list of all possible valid programs.

Interpreting an ever-growing list of programs

The key part of this challenge is to write a parallel interpreter for a growing list of programs. There are some basic steps for this:

• Add a finite number of programs to the list
• Interpret each program on the list individually for a finite period of time. This can be accomplished by performing one instruction step for each. Save all of the states.
• Remove all terminating/error-throwing programs from the list
• Output the cleanly halted* programs
• Add some more programs to the list
• Simulate each program in turn, picking up execution of older programs where it left off
• Remove all terminating/error-throwing programs from the list
• Output the cleanly halted* programs
• repeat

*You should only output programs that halt cleanly. This means that there were no syntax errors or uncaught exceptions thrown during execution. Programs which ask for input should also be terminated without outputting them. If a program produces output, you shouldn't terminate it, just throw the output away.

More rules

• You must not spawn new threads to contain the tested programs, as this offloads the work of parallelization onto the host OS / other software.
• Edit: To close potential future loopholes, you are not allowed to eval (or any related function) a part of the tested program's code. You can eval a codeblock from the interpreter's code. (The BF-in-Python answer is still valid under these rules.)
• This is code-golf
• The language you write your submission in does not need to be the same as the language you are testing/outputting.
• You should assume that your available memory is unbounded.
• When proving Turing-completeness, you may assume that input is hardcoded into the program, and output can be read off the program's internal state.
• If your program outputs itself, it is probably wrong or a polyglot.

Answer 1

subleq OISC in Python, 317 269 bytes

import collections
g=0
P={}
while 1:
    P[g]=[[0],collections.defaultdict(int,enumerate(list(int(x)for x in reversed(str(g)))))]
    g+=1
    for o,[a,p]in P.items():
        i=a[0]
        p[i+p[i+1]]-=p[i+p[i]]
        if p[i+p[i+1]]<=0:a[0]+=p[i+2]
        else:a[0]+=3
        if a[0]<0:print o;del P[o]

https://esolangs.org/wiki/Subleq

A subleq program is an extensible list of integers (p) and an instruction pointer (i). This subleq variant uses relative addressing, which the wiki talk page suggests is required for turing completeness with bounded values. Each tick, the operation p[i+p[i+1]]-=p[i+p[i]] is performed, and then i+=p[i+2] if the operation result was <=0, otherwise i+=3. If i is ever negative, the program halts.

This implementation tests every program whose initial state is comprised of one-digit non-negative integers (0-9) with an initial instruction pointer of 0.

Output:
21 (which represents the program [1 2 0 0 0 0 0...]
121
161
221
271
351
352
461
462
571
572
681
682
791
792

The output is reversed, for golfing reasons. The spec above could be restated in reverse, but then would not match the code used in the implementation, so I've not described it that way.

EDIT: The first program that exhibits simple unbounded growth is 14283, which decrements the value at memory location 6 and writes an explicit 0 (as opposed to the implicit 0 in every cell) to the next negative cell, every three ticks.

Answer 2

Bitwise Cyclic Tag in CJam, 98 87 84 77 bytes

L{Z):Z2b1>_,,1>\f{/([\:~]a2*}+{)~[\({1+(:X+\_0=Xa*+}{0+\1>}?_{]a+}{];p}?}%1}g

Since this is an infinite loop, you can't directly test this in the online interpreter. However, here is an alternative version that reads the number of iterations from STDIN for you to play around with. To test the full program, you'll need the Java interpreter.

BCT is a minimalist variant of Cyclic Tag Systems. A program is defined by two binary strings: a (cyclic) list of instructions and an initial state. To make my life easier when printing the programs, I have defined my own notation: each of the strings is given as a CJam-style array of integers, and the entire program is surrounded in [[...]], e.g.

[[[0 0 1 1] [0 1 1 1 0]]]

I'm also disallowing empty initial states or empty instruction lists.

Instructions in BCT are interpreted as follows:

• If the instruction is 0, remove the leading bit from the current state.
• If the instruction is 1, read another bit off the instruction list, call that X. If the leading bit from the current state is 1, append X to the current state, otherwise do nothing.

If the current state ever becomes empty, the program halts.

The first few halting programs are

[[[0] [0]]]
[[[0] [1]]]
[[[0 0] [0]]]
[[[0] [0 0]]]
[[[0 0] [1]]]
[[[0] [0 1]]]
[[[0 1] [0]]]
[[[0] [1 0]]]
[[[0 1] [1]]]
[[[0] [1 1]]]

If you want to see more, check out the version in the online interpreter I linked above.

Explanation

Here is how the code works. To keep track of the dovetailing we will always have an array on the stack which contains all the programs. Each program is pair of an internal representation of the program code (like [[0 1 0] [1 0]]) as well as the current state of the program. We'll only use the latter to do the computation, but we'll need to remember the former to print the program once it halts. This list of programs is simply initialised to an empty array with L.

The rest of the code is an infinite loop {...1}g which first adds one or more programs to this list and the computes one step on each program. Programs that halt are printed and removed from the list.

I'm enumerating the programs by counting up a binary number. The leading digit is stripped off to ensure that we can get all programs with leading 0s as well. For each such truncated binary representation, I push one program for each possible splitting between instructions and initial state. E.g. if the counter is currently at 42, its binary representation is 101010. We get rid of leading 1 and push all non-empty splittings:

[[[0] [1 0 1 0]]]
[[[0 1] [0 1 0]]]
[[[0 1 0] [1 0]]]
[[[0 1 0 1] [0]]]

Since we don't want empty instructions or states, we start the counter at 4, which gives [[[0] [0]]]. This enumeration is done by the following code:

Z):Z    e# Push Z (initially 3), increment, and store in Z.
2b1>    e# Convert to base 2, remove initial digit.
_,      e# Duplicate and get the number of bits N.
,1>     e# Turn into a range [1 .. N-1].
\       e# Swap the range and the bit list.
f{      e# Map this block onto the range, copying in the bit list on each iteration.
  /     e#   Split the bit list by the current value of the range.
  (     e#   Slice off the first segment from the split.
  [     
    \:~ e#   Swap with the other segments and flatten those.
  ]     e#   Collect both parts in an array.
  a2*   e#   Make an array that contains the program twice, as the initial state is the
        e#   same as the program itself.
}
+       e# Add all of these new programs to our list on the stack.

The rest of the code maps a block onto the list of programs, which performs one step of the BCT computation on the second half of these pairs and removes the program if it halts:

)~     e# Remove the second half of the pair and unwrap it.
[      e# We need this to wrap the instructions and current state back in an array
       e# again later.
\(     e# Bring the instruction list to the top and remove the leading bit.
{      e# If it's a 1...
  1+   e#   Append a 1 again (the instructions are cyclic).
  (:X+ e#   Remove the next bit, store it in X and also append it again.
  \_0= e#   Bring the current state to the top, get its first bit.
  Xa*+ e#   Append X if that bit was 1 or nothing otherwise.
}{     e# Else (if it's a 0...)
  0+   e#   Append a 0 again (the instructions are cyclic).
  \1>  e#   Discard the leading bit from the current state.
}?
_      e# Duplicate the current state.
{      e# If it's non-empty...
  ]a+  e#   Wrap instructions and state in an array and add them to the program
       e#   pair again.
}{     e# Else (if it's empty)...
  ];p  e# Discard the instructions and the current state and print the program.
}?

Answer 3

Brainfuck in Python, 567 bytes

A relatively simple solution, as Brainfuck is hardly the most difficult language to write an interpreter for.

This implementation of Brainfuck has the data pointer starting at 0, only allowed to take a positive value (considered an error if it tries to go to the left of 0). The data cells can take on values from 0 to 255 and wrap. The 5 valid instructions are ><+[] (- is unnecessary due to the wrapping).

I think the output is all correct now, however it is difficult to be sure that it is printing every possible solution so I may be missing some.

o="><+]["
A="[]if b%s1<0else[(p,a+1,b%s1,t+[0],h)]"
C="[(p,h[a]+1,b,t,h)if t[b]%s0else(p,a+1,b,t,h)]"
I=lambda s,i:i*">"if""==s else o[o.find(s[0])+i-5]+I(s[1:],i*o.find(s[0])>3)
s="";l=[]
while 1:
 s=I(s,1)
 r=[];h={}
 for i in range(len(s)):
    if s[i]=="[":r+=[i]
    if s[i]=="]":
     if r==[]:break
     h[r[-1]]=i;h[i]=r[-1];r=r[:-1]
 else:
    if r==[]:
     l+=[(s,0,0,[0],h)];i=0
     while i<len(l):
        p,a,b,t,h=l[i]
        if a>=len(p):print p;l[i:i+1]=[]
        else:l[i:i+1]=eval([A%("+","+"),A%("-","-"),"[(p,a+1,b,t[:b]+[(t[b]+1)%256]+t[b+1:],h)]",C%">",C%"=="][o.find(p[a])]);i+=1

The first few ouputs:

>
+
>>
+>
><
>+
++
[]
>>>
+>>

And a list of the first 2000: http://pastebin.com/KQG8PVJn

And finally a list of the first 2000 outputs with [] in them: http://pastebin.com/iHWwJprs
(all the rest are trivial as long as they're valid)

Note that the output is not in a sorted order, though it may appear that way for many of them, as the programs that take longer will be printed later.

Answer 4

slashes in Python, 640 498 bytes

g=2
P={}
while 1:
    b=bin(g)[3:]
    P[b]=[[0],['',''],[b]]
    g+=1
    for d,[a,b,c]in P.items():
        s=c[0]
        if a[0]:
            if s.count(b[0]):s=s.replace(b[0],b[1],1)
            else:a[0]=0
        else:
            if s[0]=='0':
                if len(s)==1:del P[d];continue
                s=s[2:]
            else:
                b[0]=b[1]=''
                a[0]=1
                t=p=0
                while t<2:
                    p+=1
                    if p>=len(s):break
                    if s[p]=='0':
                        if p+1>=len(s):break
                        b[t]+=s[p+1]
                        p+=1
                    else:t+=1
                if t<2:del P[d];continue
        c[0]=s
        if len(s)==0:print d;del P[d]

https://esolangs.org/wiki////

A slashes program is a string, in this interpreter limited to the characters '/' and '\'. In this implementation, / is '1' and \ is '0' to allow for some golfing with the use of python's bin(x). When the interpreter encounters a \, the next character is output and both characters are removed. When it encounters a /, it looks for search and replace patterns as /search/replace/ including escaped characters within the patterns (\\ represents \ and \/ represents /). That replace operation is then performed on the string repeatedly until the search string is no longer present, then interpretation continues from the beginning again. The program halts when it is empty. A program will be killed if there is an unclosed set of /patterns or a \ with no character after it.

Example output and explanations:
01 outputs '1' and halts
00 outputs '0' and halts
0101 outputs '11' and halts
0100 ...
0001
0000
010101
010100
010001
010000 ...
101110 replaces '1' with '', leaving '00', which outputs '0' and halts

Answer 5

Brachylog → Post correspondence problem, 10 bytes

≜;?{~c}ᵐ\d

Try it online!

Function which is a generator that generates all possible Post correspondence problems for which brute-forcing solutions eventually halts. (Brute-forcing solutions to the Post correspondence problem is known to be a Turing-complete operation.) The TIO link contains a header that converts a generator to a full program, and prints each output immediately as it's generated (thus, when TIO kills the program due to consuming more than 60 seconds of execution time, the output produced so far is visible).

This uses a formulation of the problem in which the strings are given as strings of digits, leading zeroes are not permitted except for 0 itself, solutions to the problem involving leading zeroes are not accepted, and a string of digits can be represented as either the number, or minus the number. Clearly, none of this has any impact on the Turing-completeness of the language (because there's no need for a Post correspondence problem to use the digit zero at all).

This program works via generating all possible solutions to problems, then working backwards to find the original programs that are solved by them. As such, an individual program can be output many times. It's unclear whether this invalidates the answer or not; note that all halting programs will eventually be output at least once (in fact, infinitely many times, as any program which has solutions has infinitely many solutions), and non-halting programs will never be output.

Explanation

≜;?{~c}ᵐ\d
≜           Brute-force all numbers:
 ;?           Pair {the number} with {itself}
   {  }ᵐ      For each pair element:
    ~c          Brute-force a partition of that element into substrings
        \     such that the two elements each have the same number of substrings
        \     and group together corresponding substrings
         d    and remove duplicated pairs {to produce a possible output}

Answer 6

Treehugger in Java, 1,299 1,257 1,251 1,207 1,203 1,201 1,193 1,189 bytes

import java.util.*;class I{static class N{N l,r;byte v;}static class T extends Stack<N>{{push(new N());}void p(){pop();if(size()==0)p();}int i,h;char[]s;}static void s(T t){if(t.i>=t.s.length){t.h=1;return ;}char c=t.s[t.i];if(c=='<'){if(t.peek().l==null)t.peek().l=new N();t.push(t.peek().l);}if(c=='>'){if(t.peek().r==null)t.peek().r=new N();t.push(t.peek().r);}if(c=='^')t.p();if(c=='+')t.peek().v++;if(c=='-')t.peek().v--;if(c=='['&&t.peek().v==0){int i=1;while(i>0){t.i++;if(t.s[t.i]==']')i--;if(t.s[t.i]=='[')i++;}return;}if(c==']'&&t.peek().v!=0){int i=1;while(i>0){t.i--;if(t.s[t.i]==']')i++;if(t.s[t.i]=='[')i--;}return;}t.i++;}static char[]n(char[]a){String b="<^>[+-]";int q=a.length;for(int i=q-1;i>=0;i--){int j=b.indexOf(a[i]);if(j<6){a[i]=b.charAt(j+1);return a;}a[i]='<';}a=Arrays.copyOf(a,q+1);a[q]='<';return a;}public static void main(String[]a){List<T>z=new ArrayList<T>();char[]c={};while(true){T t=new T();t.s=c;if(b(c))z.add(t);c=n(c.clone());for(T u:z)try{s(u);if(u.h>0){z.remove(u);System.out.println(u.s);break;}}catch(Exception e){z.remove(u);break ;}}}static boolean b(char[]c){int i=0;for(char d:c){if(d=='[')i++;if(d==']')i--;if(i<0)return 0>0;}return i==0;}}

Answer 7

SK combinator calculus in Haskell, 249 bytes

data C=H|S|K|C:$C deriving(Eq,Show)
n(a:$b)=m a*n b
n a=m a
m S=1
m K=1
m(S:$a)=n a
m _=0
f H=[S,K,S:$H,K:$H,S:$H:$H]
f a=[S:$b:$c:$d|b:$d:$(c:$e)<-[a],d==e,n b*n c*n d>0]++[K:$a:$H|n a>0]++do b:$c<-[a];[d:$c|d<-f b]++[b:$d|n b>0,d<-f c]
l=H:(f=<<l)

Try it online!

How it works

The call-by-value evaluation rules for the SK combinator calculus are as follows:

(a) Sxyz ↦ xz(yz), for x, y, z in normal form;
(b) Kxy ↦ x, for x, y in normal form;
(c) xy ↦ x′y, if x ↦ x′;
(d) xy ↦ xy′, for x in normal form, if y ↦ y′.

Since we are only interested in halting behavior, we expand the language slightly by introducing a symbol H that is not in normal form, but to which all normal forms “evaluate”:

(a) Sxyz ↦ xz(yz), for x, y, z in normal form;
(b′) KxH ↦ x, for x in normal form;
(c) xy ↦ x′y, if x ↦ x′;
(d) xy ↦ xy′, for x in normal form, if y ↦ y′;
(e) S ↦ H;
(f) K ↦ H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.

We consider any application Hx to be a run-time error to be treated as if it were an infinite loop, and we order evaluations such that no H is produced by (e)–(i) except in a context where it will be ignored (top level, any Kx☐, any ignored K☐, any ignored Sx☐ for x in normal form, any ignored S☐H). This way we do not affect the halting behavior of the usual terms lacking H.

The benefits of these modified rules are that every normalizable term has a unique evaluation path to H, and that every term has a finite number of possible preimages under ↦. So instead of using the dovetailing approach, we can do a much more efficient breadth-first search of all reverse evaluation paths from H.

n checks whether a term is in normal form, f finds all possible preimages of a term, and l is a lazy infinite list of normalizable terms produced by breadth-first search from H.

Answer 8

"Purple without I/O" in Ceylon, 662

import ceylon.language{l=variable,I=Integer,m=map,S=String}class M(S d){l value t=m{*d*.hash.indexed};l I a=0;l I b=0;l I i=0;I g(I j)=>t[j]else 0;value f=m{97->{a},98->{b},65->{g(a)},66->{g(b)},105->{i},49->{1}};value s=m{97->((I v)=>a=v),98->((I v)=>b=v),65->((I v)=>t=m{a->v,*t}),66->((I v)=>t=m{b->v,*t}),105->((I v)=>i=v)};I&I(I)x{throw Exception(d);}I h(I v)=>f[v]?.first else x;shared void p(){(s[g(i)]else x)(h(g(i+1))-h(g(i+2)));i+=3;}}shared void run(){value a='!'..'~';{S*}s=expand(loop<{S*}>{""}((g)=>{for(c in a)for(p in g)p+"``c``"}));l{M*}r={};for(p in s){r=[M(p),*r];for(e in r){try{e.p();}catch(x){print(x.message);r=r.filter(not(e.equals));}}}}

Purple is a self-modifying one-instruction language which was asked to interpret here. As input and output are not relevant for this task, I removed the o symbol's meaning from the interpreter, such that the (potentially) valid symbols are just a, b, A, B, i and 1 (the last one just for reading, not for writing).

But as Purple is self-modifying (and using its source code as data), potentially also programs containing other than those characters are useful, so I opted to allow all printable (non-whitespace) ASCII characters in the code (other ones might be useful as well, but are not as easily printed).

(You can modify the interpreter to instead take as string of allowed characters as a command line argument – switch the commented line defining a below. Then the length becomes 686 bytes.)

My "parallel" interpreter thus creates all finite strings from those characters (in increasing length and lexicographical order) and tries each of them.

Purple will halt without error whenever the command to be read from the tape for execution is not valid – thus there are no invalid programs and many, many halting ones. (Most halt even at the first step, only some of the programs with length 3 come to the second step (and will halt then), the first non-halting ones have length 6.

I think the very first non-halting program in the order tried by my interpreter is aaaiaa, which in the first step sets the a register to 0 (which it already was), and the second and every following step sets the instruction pointer back to 0, causing it to execute iaa again.

I reused part of the code written for my interpreter of "standard" Purple, but due to the removal of input and output, my parallel interpreter becomes even slightly shorter than that, while including the additional logic for executing multiple programs at once.

Here is a commented and formatted version:

// Find (enumerate) all halting programs in (a non-I/O subset of) Purple.
//
// Question:  https://codegolf.stackexchange.com/q/51273/2338
// My answer: https://codegolf.stackexchange.com/a/65820/2338

// We use a turing-complete subset of the Purple language,
// with input and output (i.e. the `o` command) removed.

import ceylon.language {
    l=variable,
    I=Integer,
    m=map,
    S=String
}

// an interpreting machine.
class M(S d) {
    // The memory tape, as a Map<Integer, Integer>.
    // We can't modify the map itself, but we
    // can replace it by a new map when update is needed.
    l value t = m {
        // It is initialized with the code converted to Integers.
        // We use `.hash` instead of `.integer` because it is shorter.
        *d*.hash.indexed
    };

    // three registers
    l I a = 0;
    l I b = 0;
    l I i = 0;

    // get value from memory
    I g(I j) =>
            t[j] else 0;

    // Map of "functions" for fetching values.
    // We wrap the values in iterable constructors for lazy evaluation
    //  – this is shorter than using (() => ...).
    // The keys are the (Unicode/ASCII) code points of the mapped
    // source code characters.
    value f = m {
        // a
        97 -> { a },
        // b
        98 -> { b },
        // A
        65 -> { g(a) },
        // B
        66 -> { g(b) },
        // i
        105 -> { i },
        // 1
        49 -> { 1 }
    };

    // Map of functions for "storing" results.
    // The values are void functions taking an Integer,
    // the keys are the ASCII/Unicode code points of the corresponding
    // source code characters.
    value s = m {
        // a
        97 -> ((I v) => a = v),
        // b
        98 -> ((I v) => b = v),
        // Modification of the memory works by replacing the map with
        // a new one.
        // This is certainly not runtime-efficient, but shorter than
        // importing ceylon.collections.HashMap.
        // A
        65 -> ((I v) => t = m { a->v, *t }),
        // B
        66 -> ((I v) => t = m { b->v, *t }),
        // i
        105 -> ((I v) => i = v)
    };


    // Exit the interpretation, throwing an exception with the machine's
    // source code as the message.  The return type is effectively `Nothing`,
    // but shorter (and fits the usages).
    I&I(I) x {
        throw Exception(d);
    }

    // accessor function for the f map
    I h(I v) =>
            f[v]?.first else x;

    // a single step
    shared void p() {
        (s[g(i)] else x)(h(g(i + 1)) - h(g(i + 2)));
        i += 3;
    }
}

// the main entry point
shared void run() {
    // the alphabet of "Purple without I/O".
    value a = '!'..'~';
    //// possible alternative to use a command line argument:
    // value a = process.arguments[0] else '!'..'~';

    // an iterable consisting of all programs in length + lexicographic order
    {S*} s =
            // `expand` creates a single iterable (of strings, in this case)
            // from an iterable of iterables (of strings).
             expand(
        // `loop` creates an iterable by applying the given function
        // on the previous item, repeatedly.
        // So here we start with the iterable of length-zero strings,
        // and in each iteration create an iterable of length `n+1` strings
        // by concatenating the length `n` strings with the alphabet members.
        loop<{S*}>{ "" }((g) =>
                {
                    for (c in a)
                        for (p in g)
                            p + "``c``"
                }));

    // This is a (variable) iterable of currently running machines.
    // Initially empty.
    l {M*} r = {};

    // iterate over all programs ...
    for(p in s) {
        // Create a machine with program `p`, include it
        //  in the list of running machines.
        //
        // We use a sequence constructor here instead of
        //  an iterable one (i.e. `r = {M(p, *r)}` to prevent
        // a stack overflow when accessing the deeply nested
        // lazy iterable.
        r = [M(p), *r];
        // iterate over all running machines ...
        for(e in r) {
            try {
                // run a step in machine e.
                e.p();
            } catch(x) {
                // exception means the machine halted.
                // print the program
                print(x.message);
                // remove the machine from the list for further execution
                r = r.filter(not(e.equals));
            }
        }
        // print(r.last);
    }
}