http://esoteric.voxelperfect.net/wiki/BF-PDA

This is interesting. What compression algorithm do you have in mind?

Brute force :-P

I was thinking compression, but not really anything in particular.

I'm wondering, by the way, just how fast this language's "busy beaver" function (program length -> maximum finite output) grows. I know int-e did some work on this, but I don't know the results.

Hmmm, that sounds quite interesting.. Do tell if you receive some results sometime. :)

Well, let's see here. It's obvious enough that there's a way to push numbers in some form onto the stack using logarithmic program space. Suppose we use binary notation, MSB on the bottom. Decrementing such a number requires flipping bits down to arbitrary places in the stack. The "position" within the stack must be kept, and since this can be arbitrarily high, it must also be kept on the stack. Since this number must be incremented from time to time, we need some way to do so, as well as a way to keep separate numbers as such. (Incrementing a number is essentially the same as decrementing.) These all can be achieved via a simple modification of normal binary notation:

00 = end of stack
01 = end of number
10 = 0 bit
11 = 1 bit

However, there seems to be a simple yet fatal flaw here: once we have some numbers on the stack, it's impossible to get to the bottom one to shave off a bit, then restore all the numbers on top, as this would require infinite memory in the FSM.

I believe that, with this, we can get rid of all hope of exponential growth, as it seems that an encoding whose size grows logarithmically cannot be decremented.

I know of no encodings for polynomial numbers in linear space, apart from that where said polynomial is linear.

So let's take the obvious linear encoding: the number n is represented by n 1's on the stack. Here, both incrementing and decrementing are trivial.

Now, suppose we have an unknown number of 1's on the stack. It is possible for this number to be higher than any piece of code can check for, so we'll assume it is. Anything useful we do with this number has to decrement it in a period, in order for said thing to terminate eventually. So the piece of code will essentially loop a number of times equal to the number on the stack, multiplied by some constant (and modified unimportantly). So if this program is running the . instruction some number of times every loop cycle, it is essentially multiplying two numbers. Since these numbers have to be given in linear program space, the whole busy beaver function must grow in quadratic time.

This is making a few assumptions, of course, but I consider it "good enough" to warrant a change to this language, making it more powerful.

Nice work.

Thanks. I'll post a spec for BF-PR soon.

Well, it looks like BF-PR is Turing-complete--oops.

I'll post a spec for BF-PR eventually.

I'm holding my breath.

Don't suffocate.