kcufniarb (ais523)

For brainfuck, see kcufniarb (Buckets).

kcufniarb is a declarative language based on brainfuck, created by User:ais523 in 2026. The primary difference from brainfuck is that in brainfuck, the tape starts as all-zeroes and could contain anything at the end of the program, whereas in kcufniarb, the tape ends as all-zeroes and could contain anything at the start of the program. A kcufniarb implementation works by searching for an initial tape configuration that causes the program to halt with the tape as all-zeroes.

The language was initially designed by starting with the name and designing a language to fit it; the name itself was inspired by seeing way too many names of brainfuck derivatives.

Specification

In kcufniarb, a "tape" is infinite in both directions, stores unbounded integers (which could be negative, positive, or zero), and has a pointer to a particular tape element.

A kcufniarb program specifies a function from tapes to tapes, expressed as an imperative program with the following commands (which are identical to those of brainfuck):

<	Move the tape pointer to the left
>	Move the tape pointer to the right
+	Increment the tape element pointed to by the tape pointer
-	Decrement the tape element pointed to by the tape pointer
[	Jump to the matching ] if the tape element pointed to by the tape pointer is zero
]	Jump to the matching [ if the tape element pointed to by the tape pointer is nonzero

If there is a finitely initialized (i.e. only finitely many tape elements are nonzero) input to this function that produces an output whose elements are all zero, then the program halts. Otherwise, it enters an infinite loop.

Mismatched square brackets are a syntax error. Any syntax that is not a command is either treated as a comment and ignored, or used for interpreter-specific extensions.

I/O extension

I/O commands are optional in kcufniarb, but if implemented, work slightly differently to brainfuck. One major difference is that I/O in kcufniarb is non-interactive, i.e. all input is read before the program starts executing, and all output conceptually produced only after execution ends (although an implementation is allowed to produce a prefix of the output "early" if it can prove that if the program halts, it will necessarily produce that output). The I/O commands are also slightly different:

,	Set the tape element pointed to by the tape pointer to the character code of one character read from input
.	Output the tape element pointed to by the tape pointer as the character with that character code
;	Set the tape element pointed to by the tape pointer to an integer read from input
:	Output the tape element pointed to by the tape pointer as an integer

Integer I/O expects integers to be written in decimal (with an optional leading minus sign). When reading integers, any leading whitespace is ignored, and any trailing nondigits after the integer are left in the input to be read by future commands. When writing integers, normally the integer is printed as-is with no delimiters, but if two or more : commands execute with no . commands in between, a newline is added in between the printed integers.

When running a program that uses I/O, the interpreter must search for an initial tape that, when run through the program given the input provided by the user, produces an all-zero tape. If it finds one, it halts, and produces the output that that program produced. If it doesn't find one, the program is an infinite loop. It is possible that there is more than one initial tape that produces an all-zero tape at the end of the program, but with different initial tapes producing different outputs; in that case, the interpreter may pick any such tape arbitrarily and output the output that that program would produce.

For example, the kcufniarb program :+[+] outputs an arbitrary negative number. (The initial tape must be all zeroes apart from a negative number at the tape pointer, because +[+] would be an infinite loop if the element at the tape pointer were zero or positive, but any negative number works.)

Example

The following (untested) program is intended to factorize positive semiprimes:

;>[]>>[+[+:[-<[-<+<->>]<[->+<]>>]]]>:--[-]

The core of this is a [-<[-<+<->>]<[->+<]>>], a brainfuck routine for multiplying two nonnegative numbers, except that it subtracts the result from the cell 3 to to the left of where it starts rather than adding it (thus, that cell becomes 0 only if the product equals the number that was input via ;). This contains guards to ensure that both numbers being multiplied are neither 0 nor 1; for one of the numbers being multiplied, the loops around it ensure that the core would not run if that number were 0 or 1; and for the other number being multiplied, --[-] is performed on it after the multiplication, which would be an infinite loop unless the number were at least 2. Thus, for the program to halt with an all-zero tape, the interpreter needs to find two integers that are both at least 2 and that multiply to the value given as input.

Implementing kcufniarb

kcufniarb is somewhat difficult to implement efficiently because it is unclear what algorithm should be used to search for a valid initial tape. The most promising approach seems to be to work backwards from the end of the program (at which point the tape is known to be all-zeroes), effectively "reverse-interpreting" the program (and analyzing both possibilities for where the instruction pointer could have come from at each end of a loop), but even this approach can be exceptionally slow due to the possibility of code like [[-]>] that can zero an arbitrarily large portion of the tape, containing arbitrarily large positive elements.

Computational class

It is possible to (ignoring I/O differences) write a program that is valid in both brainfuck and kcufniarb by zeroing the used portion of the tape both at the start and end of the program, in which case it will execute the same way in both languages. When allowing arbitrarily large integers in the cells, brainfuck is still Turing-complete even when restricted to only using a portion of the tape that can be easily and reliably zeroed, so kcufniarb must be at least Turing-complete too.

Despite involving a potentially infinite search, the restriction for the tape to be finitely initialized means that kcufniarb can be implemented via iterating over all finitely initialized tapes (of which there are finitely many), meaning that it is not uncomputable, and thus must be exactly Turing-complete.

See also

• Tableaux, a lower-level (but uncomputable) declarative tarpit
• Algebraic Brainfuck, the view of brainfuck programs as functions on tapes that kcufniarb uses to define the semantics of the language