Seems like the results in this blog post would be of interest.

https://www.scottaaronson.com/blog/?p=2741

Not so much in avoiding the halting problem while allowing complexity, but instead using it and actual runnable Turing machines to create ridiculously cool cases of unprovable truths.

For example a running Turing machine that only halts if it contradicts set theory.