> Are large language models even Turing complete?

If you want to see where they have problem ask them to do something about deep hierarchical objects. For example, consider this prompt: "Draw me a complete binary tree with numbers from 1 to 128 using pseudographics"

In my experience, the deeper the structure, the more problematic it is for the current generation of LLMs.