NQ

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

NQ is a queue-based programming language created by User K. It operates on an infinite 1-trit queue and a single flag trit, which initially holds the value 0.

Each trit is a trinary digit that can be in one of three states: 0, 1 or 2.

Instructions

Instructions are executed from left to right, once the instruction pointer reaches the end of the program it loops back to the start. The program can be of any length. Any character that isn't an instruction is ignored (treated as a comment).

Instruction	Description
+N	Enqueues the trit N. Can also be used as +(N1 N2 N3) to enqueue multiple trits at one.
lN	Same as +, but only runs on the first loop.
>N	Skips the next instruction unless the flag trit is equal to the trit N. Can also be used as >N(...) to skip the instructions in parentheses.
-	Dequeues the trit at the front of the queue and stores it in the flag trit.
r	Reads one trit of input from the user and enqueues it. Input must be a valid trit (0, 1 or 2).
R	Reads all trits of input from the user and enqueues all of them in order. Input must be a valid trit (0, 1 or 2).
W	Outputs the trit at the front of the queue using the following format: 0 → 1 → \n 2 → #
H	Halts the program.

Computational class

It is possible to implement cyclic tag with halt in NQ. Each instruction is in one of the the forms

- >2H >1+b>1+b>1+b>1+b...
- >2H >1+(bbbb...)

Where each b is a successive bit of the production, so for the production 010 the corresponding instruction is - >2H >0+0>0+1>0+0. Using the shorthand enqueue notation, this can also be expressed as - >2H >0+(010).

The normal reduction from tag systems to cyclic tag is used, except that halt symbols are replaced with 2 instead of a regular symbol.

Since the queue starts empty, the l instruction can be used to initialize a starting word. If one does not want to use the l instruction, then they can employ an alternate scheme. This scheme uses the ordinary 2-tag to cyclic tag encoding scheme, except that 0 is 1 and 1 is 2. In this scheme there are two forms:

- >2+(bbbb...)
- >2H

The first form is used for all productions, and the second is used for halting symbols.

An initial word can be supplied by prepending the following pattern to the program:

>0+(bbbb...)

In fact, this can be used to request a starting word from the user.

Example Programs

Hello, World!

+(2002000000200200000000002000200000000000200000202120020022002002000220000020002002200202202
0000020212222022220200200200200002020202002022000200022202120020200002002002002000020202020
0202000020020020012002002220020020022002000202000220020000020022202100000000000000000000021
000000000000000000002)W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-WH

This program displays the following output:

#  #      #  #          #   #           #     # #
#  #  ##  #  #   ##     #   #  ##  # ## #     # #
#### #### #  #  #  #    # # # #  # ##   #   ### #
#  # #    #  #  #  #    # # # #  # #    #  #  #  
#  #  ###  #  #  ##  #   # #   ##  #     #  ### #
                     #
                    #

Cat Program

r- take input (will eat away at the input if it was more than one trit long)
	hold 0 in memory if the input was 0
	>0+(022212000212000212000211200021200021200021022211)

	hold 1 in memory if the input was 1
	>1+(000021000021000021100002100002100002100000000001)

	hold 2 in memory if the input was 2
	>2+(022210000210000210000210222121212102221000000001)

output memory:
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-

In minimised form:

r->0+(022212000212000212000211200021200021200021022211)>1+(000021000021000021100002100002100002100000000001)
>2+(022210000210000210000210222121212102221000000001)W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-
W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-W-

2-tag system

From:

a -> bb
b -> abH

Starting on the word ba:

l(0110)
- >2H >1+(0101)
- >2H >1+(10012)
- >2H
- >2H

Or, without l:

  >0+(121211)
- >2+(121121)
- >2+(211121112)
- >2H
-
-
-