Reading through the Opcodes [https://en.bitcoin.it/wiki/Script#Opcodes] the blockchain can be be used as a 4-bit computer.
Has anyone built any small 4-bit programs and tried them on a blockchain?
What do you mean by this? Bitcoin script is intentionally not Turing-complete i.e. cannot be a "computer" in the typical sense. Could you give an example of a design?