Question is, at which level would Turing-completeness be useful?
If a single transaction was Turing-complete, then it would have unknowable verification time and could be used as a DoS vector on nodes that would attempt to verify it.
With any single transaction having a knowable worst-case verification time, there's no problem of a transaction's validity being unknowable.
But what about transaction chains? The Bitcoin (BTC) network's ScriptVM doesn't have the primitives needed to carry the computation over to the next transaction because there's no way for a locking script to enforce constraints on the outputs (a kind of locking script known as "covenant").
If the ScriptVM would be upgraded with transaction introspection opcodes (which is feasible as a soft-fork), then a transaction chain would become Turing-complete through the use of recursive covenants. There's been some work discussing why this is so: Self-Reproducing Coins as Universal Turing Machine, A. Chepurnoy, Vasily Kharin, D. Meshkov
Note that nodes wouldn't be automatically evolving the multi-TX program. Some blockchain-external agent would have to construct the next transaction that satisfies the covenant and then broadcast it to the network. The program could code-in a reward for this and incentivize anyone to construct and post the next transaction, or external agents could do it for free. The program would halt when it runs out of money for the fees/incentives, but then again, other external agents could give it more money to continue evolving.
Introspection opcodes were proposed (Jan '21) and activated (May '22) on Bitcoin Cash (BCH), a code and blockchain fork of the first Bitcoin blockchain (blocks 0 to 478558 are the same on both blockchains).
Such opcodes were also proposed (Jun '21) as Tapscript opcodes for the Elements experimental Bitcoin sidechain.