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?
No it can't. You can use bitcoin script to write simple logic (for example time locked or hash locked contracts) but you can't do loops and length of your code is limited. Ethereum have much more advanced smart contract capabilities (see ethereum smart contracts, solidity programming).