For any architecture like Vaswani’s GPT or a bigger iteration of it, eventually you run out of attention heads and layers.
If the answer is categorically no, then any sufficiently sophisticated code is not “promotable”. However, I don’t think there’s anything in principle which prevents LLMs from being Turing complete.
Idealized deterministic computing systems are the only thing that can be Turing complete, actual systems cannot be (because Turing completeness requires infinite space), LLMs are actual systems, and also are not limited-space approximation of idealized deterministic systems (they are, I suppose, deterministic if you know all the relevant parameters, including potentially some that are hardware-dependent, but they generally are a deterministic approximation of a nondeterministic system.) You can, of course, prompt an LLM to predict the output of a deterministic system and to do direct computation, but, absent an interface to external tools that actually do the computation, the results for that are notoriously unreliable.
That’s not true. My computer is for all practical purposes Turing complete - it’s tape is not the RAM, but due to side effecting, being connected to the internet, the whole universe. So while the universe itself is finite, nothing material can be mathematically infinite, Turing completeness fails “lazily”. Unless you hit the limits, it is as good as infinite.
As for the current topic, prompting problems are after a while just memoization to some limit with some strange encoding.
“For all practical purposes” is a long way of saying “not”; a large-but-finite tape is not infinite, and the key properties of Turing completeness (both universal computation and the consequent equivalence with all other Turing complete systems) do not hold with “finite but large tapes”, no matter if large is 640 kilobytes or 640 quettabytes. Particularly, differently structured “Turing complete but for finite size” systems of similar actual capacity in bytes are not guaranteed to be able to compute the same subset of all computable results. (Actually Turing machines with the same size tape would be, but “Turing complete but for size” does not imply a consistent ratio between problems of material storage space to equivalent Turing machine tape size.)
If not, than for all purposes the two are the exact same, which is my point. This is not the case with LLMs.
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.
I'd guess it's not as efficient as a native algorithm i many cases though
Turing machine is not such thing. At each moment in time, only finitely many cells of the tape are used. (The same applies to natural numbers, there are infinitely many of them, but each one of them has a finite description).