Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial state the next state in the evolution. Only then did I realise that this is an obviously finite process (because it's a primitive recursive function, I suppose?).
So my question is: what, involving Rule 110, would one have to simulate to prove Turing-completeness of some formalism? I thought initially a function that takes a predicate and an initial state and then evaluates new states until the predicate holds might suffice, but I am not so sure how that translates into the notion of termination of Turing machines. Or maybe I'm just generally way off.