Black Turing-completeness proof
This is a proof that Black is Turing-complete. This proof utilizes two phases of translation: first translating Minsky machine to Exeter, then Exeter to Black.
Preface
This particular proof was published by Keymaker in the early 2018; Black itself was published in 2006. Black was designed (by User:ais523) to be Turing-complete, but the definite proof kept not appearing. Every once in a while I (I'll use first person from now on) kept thinking about the problem, but the solution evaded me.
Because of ais523's old example program that produces an ever-increasing series of 1s, it was known that something like the Minsky Machine register could be created. This much was clear to me. But what I could not visualize or otherwise clearly think of was the actual flow of the Minsky Machine or any other counter machine in Black. For me the questions of how to transition from state to state, how to store the state, how to set what is executed next, were what I could not solve, and perhaps for the same reason nobody else produced a proof in all these years. No matter what I tried to think, there were always too many moving parts (well, moving non-spaces), and the complexity and confusion were too great, and nothing came of it. But then, one night, I had an epiphany, which resulted into several not-quite-there ideas, which together started forming into Exeter.
Exeter
My plan was not to create an intermediate language, but the way the ideas formed, it came to being on its own, almost. While I was shaping the language, I was inventing how to translate it into Black, and how I managed to translate changed the language. It's impossible to say which was first, the language or its translation.
Presently, Exeter (for now) is defined only to the degree that the code generated in this translation uses it. Exeter is a counter machine with any number of registers and instructions. The program is a list of numbered instructions. Each instruction has information in it of what flip it activates next, and which register action it is to perform then. The way the language works is rather different from MM. Again, its unusual way of working is directly related to the Black translation it eventually enables. In Exeter, initially the first flip is set, and the control flow arrives to the main program loop via the register skip route. As control flow moves to an instruction, it arrives there using one of the two routes - the positive route or the negative route. This route determines what flip the instruction will set next (first flip if the control flow arrived the positive route, second flip if the control arrived the negative route). If the flip is "halt" instead, the execution halts at this point. After setting flips, a register action is performed. This action is either increase register, decrease it (or fail at decreasing if the register is 0), or skip. "skip" means that no register action happens and the control flow simply moves on to the next instruction by using the positive route (with skip, the positive route is always taken) - this 'next' instruction was earlier determined by setting the flip.
Here's what an instruction consists of:
numeric label / flip 1 (if arrive via positive), flip 2 (if arrive via negative) / register action
Note that the flips are the same for both the positive and the negative routes. The difference of action happens by setting further flips, depending on which route the control flow arrives at the flip.
A simple Minsky Machine program:
1 inc A 2 2 inc A 3 3 halt
The above program is translated into the following Exeter program:
1 / 2, 2 / inc A 2 / 3, 3 / skip 3 / 4, 4 / inc A 4 / halt, halt / skip
In this scheme, the MM instruction 1 becomes Exeter instructions 1 and 2, the MM instruction 2 becomes Exeter instructions 3 and 4, and the MM instruction 3 (halt) is incorporated into the Exeter instruction 4. This is how the program is executed step by step:
- Arrive to instruction 1 via positive route. Because arrival via positive route, set the first flip (2). Then go to increase A.
- Register A is increased, from 0 to 1. Go via positive route and see what flip is set. (2 in this case.)
- Arrive to instruction 2 via positive route. Set first flip (3). Skip register action.
- Register action is skipped. Go via positive route and see what flip is set. (3 in this case.)
- Arrive to instruction 3 via positive route. Because arrival via positive route, set the first flip (4). Go to increase A.
- Register A is increased, from 1 to 2. Go via positive route and see what flip is set (4).
- Arrive to instruction 4 via positive route. First flip is "halt", so instead of setting a flip (there is nothing to set, because it's "halt"), the execution ends here.
The decrease instruction of MM is translated to Exeter the following way:
a / b, b / dec X b / c, d / skip
Control flow arrives to 'a'. Whether arriving via positive route or negative route, in both cases the flip is set to 'b'. After that, the register action is performed, register X is decreased. Now, if register X was 0, the decreasing was a failure, and the control flow moves on to the negative route. If register X was larger than 0, it was successfully decreased, and the control flow moved on to the positive route. Next, the flow reaches 'b'. If it arrived via positive route, it next sets 'c'. If it arrived via negative route, it next sets 'd' instead. Whatever it does, it afterwards does "skip" as a register action (thus, manipulates no registers), and from that moves on to the positive route. It reaches either 'c' or 'd', depending on which one was set earlier.
The halt instruction of MM is incorporated into the translated Exeter instruction.
Exeter to Black
Once one sees Exeter to Black translations, Exeter's design begins to make at least partial sense. The cumbersome control flow becomes actual, definite movements of the Black's instruction pointer.
The resulting construction consists of different components. There are registers and flips and small 1x1 and 1x3/3x1 pieces guiding the control flow.
I lack the verbal dexterity to describe how these components work at the level of Black's instruction space. One day I might draw diagrams (or whatever they're called) but presently I lack the software for that. The only way for perfect understanding may be to watch the program executing in real time.
The components were designed and are placed so that two routes (positive and negative) form in midst of the components. The instruction pointer is set to a route by the register action (or "skip") and follows that route until an active flip is reached.
A register (24x26) is like this:
*
*
*
*
*
*
* *
*
* *
* *
* *
*
*
x
X x
The instruction pointer arrives to either increase or decrease the register. The register's value is defined by the three bottom-most non-spaces, which move during the execution. If the middle and right-most non-spaces are on the same level, that means the simulated register's value is 0. If the non-space in the middle is lower than the right-most non-space, that means the simulated register's value is larger than 0. The value can be - visually - determined simply by counting how many blocks their difference is. During the execution this three-item arrangement keeps moving lower and lower, but there is never anything to collide with it, and the space extends infinitely.
A flip (22x20) is like this:
*
*
*
* * * *
* *
? *
* *
*
* * *
* * *
*
*
*
*
The instruction pointer arrives either via the positive route (upper) or the negative route (lower), depending on which one it was set by the register action (or the skip). Usually, there are several flips in a row (the simplest MM program translation, "1 inc A 1", needs two flips). There are as many of them as there are instructions in the Exeter program. When moving on the route after registers, eventually one flip is always met - and only one is set at the given time. (What determines the flip's position is the single non-space "?" inside the component.) The complexity of the flip results from the several things it needs to do (in a limited space): it must detect which route the instruction pointer is arriving from. The flip may be set or not. There are four events that need to be dealt with:
- 1. Instruction pointer arrives via positive route and the flip is set -> set flip off, continue to set flip #1 (defined in the Exeter instruction).
- 2. Instruction pointer arrives via positive route and the flip is not set -> continue to the next flip via the positive route.
- 3. Instruction pointer arrives via negative route and the flip is set -> set flip off, continue to set flip #2 (defined in the Exeter instruction).
- 4. Instruction pointer arrives via negative route and the flip is not set -> continue to the next flip via the negative route.
In the two cases where the flip is set, it needs to be set off before continuing. Both routes need to do that. And because they lead to different routes, they can't approach the "?" from the same direction (otherwise the routes would become the same). So, the other case needs to move the "?" one left and then raise it and then move it back to right. The four detections, the two off-flips, and one flip-setting (code that is executed later, when setting a flip) - they all had to fit right next to each other and all these actions target the same non-space "?".
Once an active flip is encountered and set off, the instruction pointer leaves the flip below it using one of the two routes. These routes move the pointer to right until the chain of flips ends and the pointer can rise. Once it rises above the flips' level, it is sent left to a route that makes it activate the next flip (flip #1 or #2 defined in the instruction, depending on the route). After moving down to activate the flip, the pointer is sent back up from the insides of the flip component, and is guided towards paths to register action. The individual route ended at the point when the pointer was set to activate a flip, from that moment onwards different routes merge (unless the program is really simple) and the association with a particular instruction is lost. This is necessary by the design of this translation, and also explains why the translation is the way it is. The pointer moves on to the register and performs the action, then continues on a route towards the next set flip.
An example translation
This simple Minsky Machine program increases the A register two times, then executes instruction 3 until A can no longer be decreased, after which it reaches instruction 4 and halts.
1 inc A 2 2 inc A 3 3 dec A 3 4 4 halt
Here is the Exeter translation:
1 / 2, 2 / inc A 2 / 3, 3 / skip 3 / 4, 4 / inc A 4 / 5, 5 / skip 5 / 6, 6 / dec A 6 / 5, halt / skip
The above translated into Black yields this 195x101 block:
* * * *
*
* * *
* * *
*
* * * *
* *
* *
*
* *
*
* *
*
* *
*
* *
*
* *
*
* *
*
* *
*
* *
*
*
* * *
*
*
* * *
* *
* * * * * * *
* * * * * * * *
* * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * *
* * * ? * ? * ? * ? * ? *
* ? * * * * * * * * * * *
* * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
a * * * * * *
* * * * * *
A a * * * * * *
* * * * * *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
!
!
Running and deciphering memory states
One can run the translations in any valid Black interpreter (as goes without saying). I've made a simple interpreter in Javascript, which can be found here: http://yiap.nfshost.com/esoteric/black/black.html
Copy and paste the translation into the program input field and hit "reset/load". Activate "1 step" button (on Windows platform by clicking the button) and then hold the return-key to achieve rapid changing of state. (I couldn't make this automatic/timed because I'm not much of a programmer.) I really hope someone makes a good GUI interpreter for Black, the language certainly deserves it.
If you need a larger area, save the interpreter locally and modify the source. In the beginning of the source 'areaw' and 'areah' are used to set the dimensions of the grid. 'cellunit' is used to set the size of the cell in pixels.
The output generated by the program (not part of the language, simply an extension to allow text-based debugging) can be used to determine the state of the registers. The above example, once run completely (7069 steps), generates the output:
*????A????????A????????aa????????aa?????????
Remove all '*' and '?'. Set all registers to 0 (on paper, in your mind, wherever you're debugging). Then read from left to right. If capital letter, increase that register. If two non-capital letters (they always come in pairs), decrease that register if it's larger than 0. Once the string has been processed this way, you have the states of the registers. (A=0, in this case.)
The translator program
The actual translator used here, written in Python, can be found here: http://yiap.nfshost.com/esoteric/black/mmtoblack.py
Give the translator the Minsky Machine program file name as an argument. With an extra argument (any string, such as "abc") the translator will print the Exeter translation and terminate.
As the input, use only MM programs with numerical labels (sequential, beginning from 1, then 2, 3, 4, and so forth). Empty lines are allowed but keep only one space between the elements of an instruction.