Ndeql

From Esolang
Jump to: navigation, search

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

External resources