GNAW

GNAW is an esoteric programming language and an OISC created by User:Rainwave in 2026. The name stands for Goto Nearest And Write.

Language semantics

GNAW operates on a right-unbounded tape where each cell stores a single integer, initially 0. A pointer is set to point to the first cell.

GNAW only has one instruction, making it a One Instruction Set Computer (OISC). The instruction takes two arguments, written as x y;. When executed, the pointer moves to the nearest cell with the value $x$ (relative to the pointer's current position) and then sets its value to $y$. More formally, find $P'$ such that $|P-P'|$ is minimized and $T[P']=x$, then set $P\leftarrow P'$ and $T[P']\leftarrow y$. If there's more than one such cell, the result is an undefined behavior. If there's no such cell, the result is also an undefined behavior.

A GNAW program consists of a list of instructions wrapped in an implicit loop, which means that the execution wraps around to the first instruction after the last instruction is executed.

Computational class

GNAW is Turing complete as The Exasperation Machine can be compiled into it.

To show this, we will map each TEM cell into a block with the following layout

0-block
[BEGIN][?][?][_][_][SET][_][ONE][_][CENTER][_][ZERO][_][_][_][_][_][_][END]

1-block
[BEGIN][?][?][_][_][SET][_][ZERO][_][CENTER][_][ONE][_][_][_][_][_][_][END]

Note that labels like BEGIN and CENTER correspond to unique integers.

One interesting observation that we can make about GNAW is that at any point of the program execution, we can statically determine the number of occurrence of each integer in the tape. This means that any attempt to represent the value of a TEM cell using existence/absence of a marker integer is bound to fail. However this limitation does not stop us from encoding 0 and 1 into GNAW.

Looking at the above block layout, we represent 0 and 1 based on the order of a ZERO and ONE pair. The two ? cells are also a pair of ZERO and ONE but their order is not important. Basically, when we want to set the value, either the true ZERO and ONE pair get swapped or the ? pair which we don't care.

Between each TEM instruction, we expand the tape right by one. This guarantees that we won't run off the tape's right boundary because TEM instructions can only move the tape head by at most one cell. Assuming the pointer is currently at CENTER, we can expand the tape as follows:

• Save the current position with CENTER POS;
• Go to the end of the tape with 0 0;
• Use a sequence of 0 y; instructions for each integer in a 0-block to append it to the end of the tape.
• Finally, return to our previously saved position with POS CENTER;.

Mapping each TEM instruction is then fairly straightforward, assuming the pointer is normalized at CENTER between each cycle. For the sake of brevity, we'll denote X X; as #X;.

Instruction	Mapping
>	#END; #BEGIN; #CENTER;
<	#BEGIN; #END; #CENTER;
/	#ONE; #BEGIN; #CENTER;
\	#ZERO; #END; #CENTER;
1	#SET; ONE TEMP; ZERO ONE; TEMP ZERO; #CENTER;
0	#SET; ZERO TEMP; ONE ZERO; TEMP ONE; #CENTER;

We also need to initialize the first block. To do that, we use a sequence of 0 y; instructions for each integer in a 0-block (but replacing BEGIN with INIT), followed by INIT BEGIN; #CENTER;. Then at the end of the program, we add the following code

BEGIN INIT; 0 BEGIN; INIT 0;

Note: The above construction uses a sacrificial ? pair to try to mimic TEM's idempotent write behavior. Though as Rainwave later found out, with Alternating Exasperation Machine, we could have just flipped the true pair directly, thus simplifying the construction a lot.

Implementations

GNAW interpreter by User:Xylochoron, written as a Wolfram Notebook.