Ndeql
Ndeql is a non-deterministic variation on Sceql thought of by User:Koen as a continuation of the Knight Shuffling Tower idea. Just like Sceql, it provides a single queue of bytes as the only form of memory available to programs. However, that queue has a particularity: it goes with n variables, holding one byte each, which all act as its front element. For every "pop" operation, one of the n variables is selected: it is used as the front value, then replaced with the next value in the queue.
Just like Sceql, the queue in Ndeql can only grow and never shrink: data can never be removed from it once enqueued into it. Initially the queue is empty, and there are 3 variables, each holding a 0.
Instructions
| Instruction | Description | |
|---|---|---|
?
|
RAND | Create a new variable, initially holding a 0. |
=
|
NEXT | Select one variable. Enqueue the byte it holds. Dequeue a byte and store it in that variable. |
-
|
DEC | Select and decrement one variable (wrapping). |
_
|
INC | Select and increment one variable (wrapping). |
\
|
BEGIN | Select one variable, and skip to the instruction after the matching END if it is zero. |
/
|
END | Go back to the corresponding BEGIN. |
!
|
GROW | Enqueue a new zero byte. |
&
|
INPUT | Read a byte from stdin and enqueue it (0 for EOF). |
*
|
OUTPUT | Select a variable. Write the byte it holds to stdout, then enqueue it. Dequeue a byte and store it in that variable. |
Computational class
Sceql was Turing-complete. Ndeql's non-determinism creates fundamental problems:
- Variables start out as zero.
- When a variable is zero, there is a nonzero probability that it will not be changed, but will be selected for all
\commands, leading the program to halt without further iteration.
There is therefore no way to guarantee that a program will complete an arbitrary large computation.
See also
- Sceql, the deterministic language Ndeql is based on.
- Knight Shuffling Tower, a similarly nondeterministic queue-based language.
External resources
- Interpreter in C.