Seems like it shouldn't be too hard to make a Rule 110 cellular automaton (https://en.wikipedia.org/wiki/Rule_110), which is turing complete.