User:PkmnQ/qoob derivatives

This is still a work in progress. It may be changed in the future.

This page details some qoob derivatives.

Dequeue (-)

An additional construct can be defined as follows:

• - Dequeue a value and discard it

With this, the dequeuing aspect of [] becomes less useful, so these variations can be considered:

[] still dequeues

Any mention of "qoob + -" should be assumed to refer to this unless specified otherwise.

This variation can be compiled into regular qoob using the following substitutions:

qoob + -	qoob
0	0
1	10
-	[]
[	[[]
]	]

[] peeks

Regular qoob is easily compiled into this variation by replacing [...] with [-...].

In the other direction, this variation can be compiled into regular qoob using the following substitutions:

qoob + - variation	qoob
0	100
1	1010
-	[][]
[	[]0[[]1010[[]10[1]0]
]	[]0]100[[]10[1]0]

This requires dequeuing and re-enqueuing the entire queue every loop iteration. A more efficient compilation may be possible.

Roll (=) and invert (*)

Two more constructs can be defined as follows:

• = Dequeue a value from the front of the queue and enqueue the same value at the back
• * Dequeue a value from the front of the queue and enqueue the opposite value at the back

This variation can be compiled into regular qoob using the following substitutions:

qoob + = + *	qoob
0	010
1	100
=	[1]0[1]0
*	[0]1[0]0
[	[[][]
]	][]

0, *, [] subset

This variation, similarly to regular qoob, can have tag systems compiled into it. For m-tag systems with s non-halting symbols and one halting symbol using an initial string of length n:

• Each non-halting symbol that produces p non-halting symbols is given an index i (zero-indexed, ranging from 0 to s-1), and is encoded as 10 0i 102p0 0s-i-1. The halting symbol is encoded as 0s+1.
• The main loop of the program contains m sets of s+1 inner loops. The first loop of each set consists of just an empty loop. In the first set, the remaining s loops are the compiled productions, while in the second set, the remaining loops only discard the 2p zeroes in each symbol without enqueuing anything.
  • The compiled version of a production consists of each symbol's representation concatenated, with 1s being replaced by *s.
• The initial string is represented using 2n 0s, followed by each symbol's representation concatenated, with 1s being replaced by *s, similarly to productions.

Here's an example tag system being compiled to this variation:

Productions:
a -> ccbaH
b -> cca
c -> cc
Initial string: baa

Queue representations:
a -> 10 1000000000 0        0
b -> 10 0          10000000 0
c -> 10 0          0        100000
H ->  0 0          0        0

Qoob variant program:
000
*00*00000000 *0*00000000000 *0*00000000000
[
 [] [*000*00000 *000*00000 *00*00000000 *0*00000000000 0000] [*000*00000 *000*00000 *0*00000000000] [*000*00000 *000*00000]
 [] [[][][][][][][][]] [[][][][][][]] [[][][][]]
]

Here's an adapted version of the Python program given on qoob#Computational_class for this construction:

def tag_to_qoop(m, productions, indata, halting=[]):
    # ensure a consistent order, strictly unnecessary
    ordered = list(productions.items())
    # Construct the one-hot vectors
    lookup = {
        s: "*0" + "0" * i + "*" + "0" * (2 * len([j for j in p if j not in halting])) + "0" + "0" * (len(productions) - i - 1)
        for i, (s, p) in enumerate(ordered)
    }
    # And the halting symbols
    for s in halting:
        lookup[s] = "0" * (len(productions) + 1)
    print(lookup)
    lookup = str.maketrans(lookup)
    # Put the input at the start
    program = "".join(["00" for j in indata if j not in halting]) + indata.translate(lookup)
    # Overarching loop
    program += "[[]"
    # Productions
    for s, p in ordered:
        program += "[" + p.translate(lookup) + "]"
    # Empty discard productions
    for _ in range(1, m):
        program += "[]"
        for s, p in ordered:
            program += "[" + "[]" * (2 * len([j for j in p if j not in halting])) + "]"
    program += "]"
    return program

# Example
halt_system = {
    "a": "ccbaH",
    "b": "cca",
    "c": "cc",
}

print(tag_to_qoop(2, halt_system, "baa", halting=["H"]))

1, *, [] subset

This section is still a work in progress. It may be changed in the future.

Duplicate (:)

This section is still a work in progress. It may be changed in the future.