Black
Black is a two-dimensional esoteric programming language created in 2006 by User:ais523. It was inspired by 1L and BackFlip, as an attempt to create a symmetrical Turing-complete language with only one instruction (two counting NOP), that uses code as data (BackFlip-style).
Commands
A Black program has only two commands: space (a NOP) and non-space (which can be represented by any character, which could be different for different commands; # is commonly used). The program runs in an unbounded area (unbounded in all four directions); any cells not initially specified are filled with spaces. The effects of non-space are as follows:
- If the instruction pointer moves into a non-space, it pushes that non-space one space in its own direction (leaving a space behind in the cell it moved from), and causes the instruction pointer to turn 180 degrees.
- If the above action would push a non-space into a cell already occupied by a non-space, program execution terminates.
- If there is a non-space behind and to the left of the instruction pointer (from the point of view of the direction the instruction pointer is moving in), and the instruction pointer is not on a non-space, the instruction pointer turns right.
- Likewise, if there is a non-space behind and to the right of the instruction pointer, and the instruction pointer is not on a non-space, the instruction pointer turns left.
- If both the two above conditions are true, the instruction pointer continues in its original direction (thus, it is possible for the instruction pointer to go between a pair of non-spaces).
The instruction pointer starts at the third row and third column of the input, going right.
Examples of commands
(In these simple examples, arrows have been added to show how the IP moves, or Xs if it moves in more than one direction; they are not non-spaces in the examples.)
Due to technical considerations, there are not enough blank rows before some of these examples; the place where the IP enters marks the third row and third column of these examples.
How a non-space affects program flow:
#
>>>>>>>>V
V
V
How to create an infinite loop:
# #
>>>>>>>>>V
#^ V
^ V#
^<<<<<
#
Here, the pair of #s on the left shows how an irreversible construct can be created.
How to cause the IP to rebound:
##
XXXXXX>>V
^# V
^ V#
^<<<
#
If this is wanted at the edge of the map, there is a simpler but less efficient method:
XXXXXXX#
(This has the advantage that it moves further away every time it is used, and so it is easy to ensure that closer moving objects never catch up to it.)
How to turn a corner reversibly:
##
>>>>>>>>V
# V#
V<<<
V
(If the IP enters from the output here, it will leave through the input.)
Example program
1
# # # #
N
# #
#
# # #
#
#
# #
# #
#
#
# #
# # # #
# # #
#
#
#
%
# #
+
##
# #
#
#
# #
+
# #
#
## # #
+
# #
#
#
#
#
#
* *
*
!
If extensions are used, this program produces the following output:
11111111111111111111111111 111111111111111111111111111 1111111111111111111111111111 11111111111111111111111111111 111111111111111111111111111111 1111111111111111111111111111111 11111111111111111111111111111111 111111111111111111111111111111111 1111111111111111111111111111111111 11111111111111111111111111111111111 111111111111111111111111111111111111 1111111111111111111111111111111111111
(the pattern continues to infinity). Even without extensions, the program does the same thing (but its progress can only be monitored with a debugger). This output cannot be produced by a bounded-storage machine or even a push-down automaton, making it more likely that Black is Turing-complete. The main activity of the program consists of moving the % down to the set of *s and back to its original location, with the IP bouncing off the 1 or the ! as it goes. To produce the increase in length, the entire set of *s is moved downwards! (This is why the program is so large). In effect, this creates an unbounded integer. Every time the % returns to its original location, the N is moved. (All nonspaces but the #s are moved during the course of the program.)
Another example
There is a truth-machine in Black here: Truth-machine#Black. It needs to be run in an interpreter that uses the output extension if one wants to see any output. The input (0/1) is calibrated by changing the position of a single '*'.
Extensions
The above example uses the following extension:
- Whenever a non-space consisting of a single digit is moved, that digit is output;
- Whenever the non-space N is moved, a newline is output.
This extension is not part of the language, and does not interfere with any program that does not use it, except possibly to produce garbage output (or, in rare cases, useful debugging traces).
Computational class
The language was suspected to be Turing-complete, but it was not proven until 2018. The Black Turing-completeness proof uses a method of translating Minsky Machine into an intermediate language (Exeter) and then that into Black.
Black implementations
ALPACA
The following is an ALPACA implementation of Black; it only works on an ALPACA implementation with an unbounded area, and requires preprocessing (all nonspaces must be changed into the # character, and a > character must be placed in the third row and third column).
class UpIP; class DownIP; class RightIP; class LeftIP;
state Space " "
to RightSp when (v is UpIP and v< NonSpace and v> Space)
or (^ is DownIP and ^< NonSpace and ^> Space)
or (< is RightIP and ^< Space and v< Space)
or (< is RightIP and ^< NonSpace and v< NonSpace),
to LeftSp when (v is UpIP and v> NonSpace and v< Space)
or (^ is DownIP and ^> NonSpace and ^< Space)
or (> is LeftIP and ^> Space and v> Space)
or (> is LeftIP and ^> NonSpace and v> NonSpace),
to UpSp when (< is RightIP and v< NonSpace and ^< Space)
or (> is LeftIP and v> NonSpace and ^> Space)
or (v is UpIP and v< Space and v> Space)
or (v is UpIP and v< NonSpace and v> NonSpace),
to DownSp when (< is RightIP and ^< NonSpace and v< Space)
or (> is LeftIP and ^> NonSpace and v> Space)
or (^ is DownIP and ^< Space and ^> Space)
or (^ is DownIP and ^< NonSpace and ^> NonSpace),
to NonSpace when > MoveLeft or ^ MoveDown or v MoveUp or < MoveRight;
state NonSpace "#"
to MoveLeft when > LeftSp,
to MoveUp when v UpSp,
to MoveRight when < RightSp,
to MoveDown when ^ DownSp;
state MoveLeft "L" is RightIP to Space;
state MoveRight "R" is LeftIP to Space;
state MoveUp "U" is DownIP to Space;
state MoveDown "D" is UpIP to Space;
state RightSp ">" is RightIP to Space;
state LeftSp "<" is LeftIP to Space;
state UpSp "^" is UpIP to Space;
state DownSp "V" is DownIP to Space.
C
An interpreter in C is also available. (The original page appears to be dead and not archived; a copy of the interpreter itself has been rehosted here.)
Javascript
A simple, visual interpreter in Javascript can be found here.
Golly
A visual interpreter in Golly was originally written by _zM here; an improved version by Wright is available here.