Talk:Bitwise Trance

Turing completeness

I'm not sure this really is a Turing complete language. Sure, it works fine as an FSM, but you run into problems when you start storing data. You will probably need a pointer to keep track of your position, and this must be stored within the instructions. As you get more data, your pointers get bigger, and you find you need to shunt parts of the commands (and possibly data) forward to make room. But to do this will require another pointer, which just means you have two problems instead of one. I should also mention that to increase the length of the pointer, you will also need a pointer to the pointer, which itself needs another pointer, and it's pointers all the way down. It's possible there is some way to get it to work, but I don't know what it would be. Plokmijnuhby (talk) 12:51, 10 February 2019 (UTC)

Thinking about this myself, there seems to be something of a chicken-and-egg problem with defining addition. To be able to access large addresses, you need to be able to store a large address in memory. So that means setting alternate bits in a long run of consecutive bits. That means you have to be able to calculate the addresses of all those bits, which means you need a working way to do increments. But in order to implement an increment, you need a way to loop over the bits of the number you're incrementing, which, in the general case, requires you to implement an increment.

This doesn't prove that the language is sub-TC, though, as there's another potential solution you could use; you'd write a program where all the addresses have a given fixed size, and use it to build in memory a program with the same functionality except that the addresses are larger. Because the addresses are encoded in binary not unary, a program has enough space to encode all the addresses within itself and plenty of room to its right, thus it seems probable that you could write a working "address expander" without ever using bignum arithmetic. There would be some complications – you'd have to use self-modifying code to do the indirect addressing needed to read a particular bit of the program, and thus your expanded copy would likely capture some of the self-modifications but not others – but it doesn't seem insurmountable, as there'd likely be some way to fix it up afterwards. --ais523 15:11, 10 February 2019 (UTC)