Minitree

Minitree is a programming language which operates on a binary tree rather than a tape, as well as being executed using a pre-order depth-first-search traversal of its code starting from the left as if its code was a complete or almost-complete binary tree with the first instruction being the root, the second instruction being the left branch, the fourth instruction being the left branch of the left branch, etc.

It was created in 2023 out of the creator's consistent inability to create proper Branchback documentation. The idea is that, due to bf's simplicity, creating a tree-based bf derivative should make it easier to make other tree-based languages. Version 1 was essentially an obfuscated version of Treehugger.

Only Version 3 is still here for the sake of brevity.

Instruction Traversal

Explaining Myself

To me, "pre-order depth-first traversal starting from the left" means that the code is executed in the following order:

1. Execute the current instruction
2. Ignore this step if there is no left subtree, else go to the instruction corresponding to the left child and do Step 1
3. Ignore this step if there is no right subtree, else go to the instruction corresponding to the right child and do Step 1;
4. Done!

The binary tree of the instruction is almost complete because it contains the maximum amount at each level except the last.

Explaining More Visually

It is possible that I am using the words incorrectly. Here is what I am trying to say visually:

Assuming the instructions given are 123456789ABCDEF, the way this is laid out in the tree can be represented as:

          1
     2           3
  4    5      6    7
8  9  A  B  C  D  E  F

The commands would be executed in the order:

1 2 4 8 9 5 A B 3 6 C D 7 E F

• executing the current instruction
• "multiplying the instruction number by 2" and starting the cycle again with the instruction at that number
  • until that doesn't correspond to an instruction
• "multiplying the instruction number by 2 and adding 1" and starting the cycle again with the instruction at that number
  • until that doesn't correspond to an instruction.

Generate Code

Let's say the instructions we want to execute are the letters A through J (A B C D E F G H I J, 10 instructions), and they have to be executed in ascending order.

In order to figure out where to put the numbers, one can find the number of instructions (10 in this case).

Counting from 1 and multiplying by 2 until we exceed the number of instructions and not including the exceeding number gives us the placements of the first instructions that will be executed. In this case, those placements are 1 2 4 8. These correspond to the positions of the first instructions to be executed, so when it comes to the actual written code A should be the first command, B should be the second command, C should be the fourth command, and D should be the eighth command.

Therefore, if we were to write the commands we know and indicate commands we don't know with _, our current instructions are:

A B _ C _ _ _ D _ _

The next instruction that will be executed is the one in the space after that of the last of these positions, if it is less than the number of instructions. In this case, that would be the ninth space (8 + 1 = 9), and because there is a ninth space, that is where E will go.

A B _ C _ _ _ D E _

For the next instruction, we go to the second-to-last of these positions, which is 4. Counting from that position plus 1 and multiplying by 2 until we exceed the number of instructions and not including the exceeding number gives us the placements of the next instructions that will be executed, in this case 5 10. Therefore, F will go in the fifth position and G will go in the 10th position.

A B _ C F _ _ D E G

The next instruction that will be executed is the one in the space after that of the last of these positions, if it is less than the number of instructions. In this case, that would be the 11th space (10 + 1 = 11), but because there are only ten instructions, that is impossible.

Because the second-to-last of these positions is 5, which we have already seen, we can go back to the original list of positions 1 2 4 8, where we were on the second-to-last position already. You may understand the formula already, but I will put the formula here again anyways. Because we were already on the second-to-last position, we go to the third-to-last position, 2. Counting from that position plus 1 and multiplying by 2 until we exceed the number of instructions and not including the exceeding number gives us the placements of the next instructions that will be executed, in this case 3 6. Therefore, H will go in the third position and I will go in the sixth position.

A B H C F I _ D E G

The next instruction that will be executed is the one in the space after that of the last of these positions, if it is less than the number of instructions. In this case, that would be the seventh space (6 + 1 = 7), and because there is a seventh space, that is where J will go.

A B H C F I J D E G

Because the second-to-last of these positions is 3, which we have already seen, we can go back to the original list of positions 1 2 4 8, where we were on the third-to-last position already.The fourth-to-last instruction is just 1 again, and also all of the places are filled anyways.

          A
    B           H 
  C     F     I   J
D  E  G

One problem with this example is that there are only four, so I haven't explicitly shown you what to do if you have a secondary list of positions which is more than two positions long, like 3 6 12 . In this case, you don't go back to the original list of two until you have finished with this secondary list.

Current Language

This is entirely different from the previous versions because it is not a derivative of Brainfuck at all and takes full advantage of what the tree can do, in a way which is theoretically similar to how Branchback was supposed to work the entire time.

The code essentially operates as a single huge function which returns a specific value at the end, but with the caveat that the pointer can jump around within the function.

The pointer starts at the leftmost node with no children, then traverses up the tree.

I no longer think this language has to serve a purpose. Now I just want to see what the heck this even does.

Command	First Pass	Subsequent Passes
^	indicates an empty cell; returns whatever is coming from underneath it to the parent node, and allows the pointer to pass to the code underneath it	same as before
&	indicates a single-storage cell; takes the value in the pointer and stores it	replaces the value in the pointer with the value inside it, then switches back to first-pass behavior
\	indicates the lack of a left child; the left child of the parent node and all of the subsequent nodes are assumed to be skipped	same as before
/	indicates the lack of a right child; the right child of the parent node and all of the subsequent nodes are assumed to be skipped	same as before
0-9, A-Z, a-z, ?, !	function as numerals of a custom base-64 numbering system, where the placement is equal to the value (i.e. A = 10, a = 36, ? = 62); returns itself to the unread child or the parent node	acts the same as an empty cell; whether or not this is indicated in the physical code is up to the implementation, considering other commands rely on these.
+	adds the two children underneath it, returns this to the parent node	same as before
-	subtracts the right child from the left child; returns this to the parent node	same as before
*	multiplies the left and right child; returns this to the parent node	same as before
>	if left child is greater than right child, return the value of the left child to the parent node; else, put the value of the left child in the highest non-traversed empty or storage child of the right child and keep going down the right children of that node until finding a node with no children or a non-numerical non-empty node. If there are no non-traversed empty children found, try again by changing all nodes underneath to their non-traversed forms. If there are still no empty nodes found, end the program.	changes all nodes underneath to their non-traversed forms and tries the same thing again
<	if left child is less than right child, return the value of the left child to the parent node; else, put the value of the right child in the highest non-traversed empty or storage child of the left child and keep going down the left children of that node until finding a node with no children or a non-numerical non-empty node. If there are no non-traversed empty children found, try again by changing all nodes underneath to their non-traversed forms. If there are still no empty nodes found, end the program.	changes all nodes underneath to unread and tries the same thing again
=	if left child and right child are equal, return that value to the parent node; else, copy the value of the right child into the highest non-traversed empty or storage child of the left child going leftwards and put the value of the left child in the highest non-traversed empty or storage child of the right child going rightwards and keep going down the left and right children of those nodes until finding either a non-numerical non-empty node or favoring the right child in the case of a tie. If there are no non-traversed empty children found, try again by changing all nodes underneath to their non-traversed forms. If there are still no empty nodes found, end the program.	changes all nodes underneath to unread and follows the same procedure again
.	outputs the numerical value of the child or parent it came from in base-64 as indicated by the digits earlier; returns the numerical value to whichever child node wasn't read, or to the left node if neither child node was read, or to the parent if all of the nodes around it were read	same as before
,	take in only an integer between 0-! inclusive, indicated earlier; return this value	same as before

Truth Machine

This is a tentative truth machine written in a vaguely tree-like way.

     .
   =   /
 ,    0
\ /  \  <
      2   ^
     < / \   =
  ^   1    1    &
 > / \ /  \ /  \ <
. 0              0 1

The idea is:

• The pointer goes down to the left child of the left child.
• If the input is zero, 0 = 0, so the pointer goes up to the parent node, outputs zero and ends.
• If it is not zero, it goes down the right child, storing the value in the pointer in the right child of the right child of the right child of the left child of the highest node (which is the highest empty cell in the code, in the fifth row).
• It finds the = sign and checks for equality. The left child is one, and the right child has to be found.
  • The value in the pointer is stored in the storage cell.
  • The less than sign indicates that 0 has to be less than 1.
  • This is true, so it passes 0 up.
  • The value previously in the pointer is passed back into it.
• Now the equality check runs.
• If the value is not equal to 1, the left child doesn't have any empty nodes to store the value of the right child, so the code halts.
• Say the value is equal to 1.
  • 1=1, so the pointer goes up and checks if 2<1.
  • This is false, so it stores the value of 1 and then checks if [value in pointer] > 0, while also printing the value in the pointer.
  • Because 1>0, the pointer goes up and sees if 1<1.
  • There are no more empty nodes in the left child (because 1 was stored there), so the left child is reverted to its pre-traversal state. The value 1 is stored there again (this time from the right child) and 1 is printed again.
  • This repeats indefinitely.

It could also be written like: .=/,0\/\<2^</\=^11&>/\/\/\<.001

If you can't tell, I added a bunch of functionality to the language entirely to run this.

Computational Class

I don't know the exact computational class. It can't be Turing-complete because it can't store infinite data. I don't want to just assume it's a linear bounded automaton without proof. Please explain the computational class if you know what it is.