[heliophobicdude]

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 collapse all of the hardest problems in NP with a single prompt?

Will we ever know if NP can be reduced to P???

[ineedasername]

Or prompt(n) time, where n = the known minimum # of prompts required to solve a given class of problems.

From there we can define various classes of problems:

1) those with an absolute floor minimum # of required prompts

2) those with a known ceiling

Etc.

This should be combined with traditional Big-O notation to provide a more specific classification, e.g. a constant-time complexity task with a known ceiling of two prompts would be prompt(2)-O(1)

A problem known to, in some specific cases but not all, be solvable with some minimum number of prompts with no ceiling known might be Prompt(n(np)) where n = minimum prompts known to solve at least some problems in that class.

Classifications would be applied to specific systems but the best performing system would set the general classification for a problem. So the general classification for a problem might be prompt(1(5)) to denote a min 1 max 5 prompts required based on the best performance seen to date, a specific system might only rate a prompt(3(np)) classification.

I’m overthink this but I think I like it.

[ComplexSystems]

From what I can tell, experts currently project the problem "TURN HUMANS TO PAPERCLIPS" is in complexity class "Promptable," but that the Boolean Satisfiability problem is not in "Promptable."

[janalsncm]

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 principle which prevents LLMs from being Turing complete.

[dragonwriter]

> Are large language models even 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.

[kaba0]

> Idealized deterministic computing systems are the only thing that can be Turing complete

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.

[dragonwriter]

> My computer is for all practical purposes Turing complete

“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.)

[kaba0]

Can you give me any way that can differentiate between my practical machine with memory sized n, and a real infinite Turing machine in a finite amount of time t?

If not, than for all purposes the two are the exact same, which is my point. This is not the case with LLMs.

[janalsncm]

Sure, then a trivial example of a non-“promotable” input would be an input containing a problem whose solution requires more memory than any computer currently has. But I don’t think that’s what they were looking for.

[famouswaffles]

With memory they are. https://arxiv.org/abs/2301.04589

[solomatov]

You are mixing up LLMs with Transformers. Transformers with memory are Turing complete, but AFAIK, current state of the art LLMs aren't trained with any kind of memory.

[famouswaffles]

I'm not. The paper specifically deals with language models in particular. Memory is just dynamically inserted context

[solomatov]

So as I see it, it's possible to teach SOTA LLM with prompts to emulate a state machine part of the Turing machine. Am I right?

[solomatov]

Ok. I see. Sorry.

[solomatov]

> 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.

[bippihippi1]

attention is turing complete https://news.ycombinator.com/item?id=36332033

I'd guess it's not as efficient as a native algorithm i many cases though

[solomatov]

It's not realistically Turing complete. It assumes infinite precision.

[CydeWeys]

Right but a Turing computer assumes infinite storage space which is itself impossible. You cannot have infinite precision without infinite storage, and all real computers that we colloquially say are Turing complete have finite everything.

[solomatov]

It's possible to argue that there's no such a thing as infinite precision floats. I.e. all objects have limited "size", and real numbers is just a nice abstraction to simplify discrete world. (https://en.wikipedia.org/wiki/Finitism)

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).

[kaba0]

It lazily uses infinite tape though, so it is Turing complete for an actual, finite number of steps. You can’t have infinite precision even for a single step.

[AdieuToLogic]

> Will we ever know if NP can be reduced to P???

My opinion is that it cannot, due to the unbounded nature of NP problems[0]. Regarding sudoku specifically, the question is a bit more nuanced (as described here[1]).

As for the NP nature of sudoko in its general form, a short but very informative description can be found here[2].

HTH

0 - https://en.wikipedia.org/wiki/NP_(complexity)

1 - https://stackoverflow.com/questions/50703174/is-sudoku-np-co...

2 - http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html

[throwawaylinux]

> 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.

Promptable is old hat now. I propose an entirely new class of problems which is whether you can prompt GPT to construct a prompt for GPT that can solve a problem. I call it Deep-Promptability™ (patent pending). The "order" is defined by how many levels of prompting can you solve the problem in, so if a problem is order-3 deep-promptable then you can prompt GPT to construct a prompt for GPT that will construct a prompt that allows GPT to solve it.

[itsdrewmiller]

I honestly can't tell if any of the other replies to this comment got the joke.