The title is funny to me. We should consider a new computation complexity class for LLMs. Let's call the ones that can be solved with a prompt, Promptable. For the problems that we cannot reliably solve with a single prompt yet, let's call them non-deterministic promptable, or NP. Question is, for most of these hard problems, is there a prompt that can solve them? Better yet, is there a prompt good enough that we col…
Are large language models even Turing complete? Or more specifically, is there something we can say about LLMs as a class with respect to this question? 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 prin…
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.