Talk:Madbrain

So, the big question now is, if it is turing complete. It's even not very easy to put something on the stack and then ask the user to input two numbers and multiply them. Since

0
r
r
*
p

is always 0. To store 0 you'd have to write

r
0
r
*
p
p

But what, if the 0 was stored before?

-- Feuermonster 18:03, 25 March 2010 (UTC)

Since you take things from the bottom of the stack, you essentially have a queue available. It looks to me like compiling a BCT program into this language should be possible. --Ørjan 05:30, 26 March 2010 (UTC)

It is possible to rotate the stack by adding 0.

If the stack looks like this

a,b,c,d

You can push 0 and perform an addition ->

b,c,d,(a+0) -> b,c,d,a

If you do that a lot you can multiply c by d because the stack then looks like

b,c,d,a -> c,d,a,b -> d,a,b,c -> a,b,(c*d)

So: It is possible if you know exactly how your stack looks like and you know the exact amount of elements on the stack.

-- Feuermonster 11:39, 26 March 2010 (UTC)

I think Minsky Machine would be easier to implement than BCT. Yep, this seems like a Turing-complete language, as said. --Keymaker 13:35, 26 March 2010 (UTC)

Hm, but let's think of a loop which prints 98765....0

The thing about that is, you can not "repush"/"duplicate" an element on the stack:

9

9

1

0

+

1

0

+

-

0

+

-

p

?

2x

j

It won't work. Because print takes the element from the stack, and j too. So you have to store each element three times before entering the loop.

Which is actually the same as if you just had used 9p8p7p6p and so on.

You can't gain data or hold data. You loose it if you use it ;)

Or maybe there is a trick to workaround that, but I can't think of any :( -- Feuermonster 16:54, 26 March 2010 (UTC)

Yeah, I don't think a Minsky Machine using the language's numbers directly is feasible, because the language cannot handle unbounded numbers freely enough. There is no way to duplicate arbitrary data, and every testing operation can only give a limited amount of information while it always destroys the original numbers. You cannot keep more of a number than you can encode in the current program position.

However, BCT uses only bits, so you can keep enough temporary data in the column position. Here is one way. Assuming the very first data bit is encoded as the current running column, and the rest are on the stack, the BCT commands become (printing deleted characters as suggested on the BCT page):

0      10      11

01      0       1
pp
01
dd
2
2
+
i
  ddx

Note that in encoding the 10 and 11 commands, I needed a 1 line NOP command to complement the digit command. The current implementation ignores non-command characters, so I used a space. If that is not intended to be a NOP, then I have difficulty seeing how to get an odd-length NOP command. Especially if the current line number is too large to fit in a single digit. The easiest way I see around this would be to encode BCT bits as two numbers instead of one, then I think all paths have the same odd-even parity length and 0 then i becomes a NOP. Oh and I haven't actually tested the above. :) --Ørjan 17:04, 26 March 2010 (UTC)

I guess adding two new opcodes like "duplicates the value on top of the stack" and "duplicates the value at the bottom of the stack" wouldn't be bad ;).

But still, the problem of rotating the stack remains. You have to know the amount of elements on the stack to be able to perform an operation which takes two opcodes if

you already stored data on the stack. But I have an Idea how to solve that in general. -- Feuermonster 21:42, 26 March 2010 (UTC)

It is Turing-equivalent

And here's the proof, an compiler, written in Perl, for compiling 2-tag systems with alphabets with 8 regular symbols and 1 halt symbol and arbitrarily large production rules to Madbrain:

#!/usr/bin/perl
use warnings;
use strict;
# Translates a tag system program into a Madbrain program. The tag
# system must have m=2, and an alphabet {1,2,3,4,5,6,7,8,9}, where 9
# is the halting state.
# The first line of input gives the initial string (which can be of
# any length). The other lines of input give the productions for 1 to
# 8 respectively.


# We alternately discard and pay attention to elements of the string.
# The start of the string is represented by the bottom of the Madbrain
# stack. Tag systems expect paying attention to happen first, but this
# code puts the discard first, so we put junk onto the stack so as to
# be able to discard it. Then the actual discard is done with an
# addition of 0 to cycle the stack, followed by printing the number to
# get rid of it.
print <<'EOF';
 123456789$
 ppppppppp$
 00000000 $
 ++++++++ $
 pppppppp $
EOF

# Now, we put the initial string, and the productions for 1..10, in
# columns.
my @lines = (<>);
chomp for @lines;

scalar @lines == 9 or
    die "Input does not contain exactly 9 lines (1 initial string + 8 productions";

push @lines, ""; # last, dummy rule

my $longestline = 0;
length > $longestline and $longestline = length for @lines;
$_ .= ' ' x ($longestline - length) for @lines;

for my $n (1..$longestline) {
    s/^(.)//, print $1 for @lines;
    print "\$\n";
}

# Finally, we jump to the relevant column. This is done by returning
# to the first column, then moving right the appropriate number of
# steps while jumping back to the first line (line 0).
print <<'EOF';
012345678 $
ddddddddd $
000000000 $
gggggggggx$
EOF

Here's what the example tag system shown on Esolang looks like in Madbrain:

 123456789$
 ppppppppp$
 00000000 $
 ++++++++ $
 pppppppp $
2333      $
1333      $
121       $
 1        $
 9        $
012345678 $
ddddddddd $
000000000 $
gggggggggx$

(I think 8 regular symbols is enough for 2-tag systems to be Turing-equivalent, although I'm not 100% sure on this. Even if it isn't, the above program can trivially be generalised to tag systems with larger m by repeating the 0+p section.) --ais523 19:27, 22 February 2012 (UTC)