> Turing completeness being the clear first, which is problematic given the halting theorem and all that, so it's now rich statefullness instead

Um, pretty sure it was a solved problem from the start? You could always submit a non halting contract, it'd just burn through your gas and stop.