Minebit

Minebit is a programming language invented by User:TehZ. It is designed in a way easily implementable in Minecraft using redstone and linear access memory.

Language

There are only two commands:

0 - if current bit is 0, skip next command
1 - flip current bit

It uses linear access memory, so each step, a new bit is made available. That means that it needs finite memory. It can, however, also mean that it can have unbounded program area, if the program is fed to the machine. In other words, it has two bit-tapes; the program tape and the data tape.

Implementation

It can be implemented using a few logic gates. Note:

=V- means or
=^- means and
=o- means xor
-L- means linear access memory
-N- means not
+ means cross

NOTE: This implementation is not timed. If you implement it (like I have done) you need careful timing.

.------------------.
*-L---:=V-.----:=o-*
      |    |   |
.-L-.-*----:=^-*
*---*

The linear access memory can be implemented by an array of repeaters.

Computation class

The language is not Turing complete because it has limited memory, and even if it was modified to have infinite memory, it is still equivalent to a read-only right-moving Turing machine, which is equivalent to a finite state machine.