Turing-completeness != un-optimizable! Literally the areas of type systems and compilers exist to serve this endeavor. It's gotta be a meme at this point every time someone brings up the halting problem or rice's theorem.
Right, but the type system is the constraint. Nobody's gonna take the untyped lambda calculus and run it on an accelerator. Even something like turing-completeness can be a type annotation, for example, the totality effect provided by languages like Koka.
