Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found? • Hacker News Board

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#61

Post by kaba0 » Fri, Jul 21, 2023, 5:05 PM UTC

dragonwriter wrote: post #58

kaba0 wrote: post #48

Earlier quoted context omitted.

> 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 li…

> 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, d…

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.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#62

Post by solomatov » Fri, Jul 21, 2023, 6:11 PM UTC

famouswaffles wrote: post #59

solomatov wrote: post #56

Earlier quoted context omitted.

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.

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

Ok. I see. Sorry.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#63

Post by solomatov » Fri, Jul 21, 2023, 6:14 PM UTC

famouswaffles wrote: post #59

solomatov wrote: post #56

Earlier quoted context omitted.

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.

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

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?

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#64

Post by gwern » Fri, Jul 21, 2023, 6:47 PM UTC

shawntan wrote: post #52

gwern wrote: post #32

Earlier quoted context omitted.

> The theoretical class of problems that Transformers can solve (without Chain-of-Thought style responses) is fairly limited. Which is irrelevant because how would a Transformer emit a complete Sudoku solution in a single forward-pass/token in the first place?

I suppose you mean in order to give the answer to a Sudoku puzzle, you'd need a string of tokens anyway: [(x,y) grid coordinates], [digit]. I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do. My guess is that the straightforward output of the exact solution, even though it requires several t…

> I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do.

Yes, and maybe the occasional generation of the complete boardstate to date, because you don't want to leave the boardstate implicit and require it to be reconstructed within each forward pass - that's 'using up serial computations' that a Transformer can't afford. But if you periodically serialize the best-answer-to-date, you are more likely to be able to bite off a chewable chunk.

> My guess is that the straightforward output of the exact solution, even though it requires several tokens, wouldn't be enough to do the constraint resolution in Sudoku

A Transformer is not much different from an unrolled RNN without weight-sharing, so for any specific sudoku size, there should be some depth which does allow the worst-case amount of backtracking or other solution to the problem. (One way to show this would be to use the RASP programming language to program such a solver.) It's just it'd probably be bigger/deeper than you have available now.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#65

Post by janalsncm » Sat, Jul 22, 2023, 12:38 AM UTC

dragonwriter wrote: post #21

janalsncm wrote: post #19

Earlier quoted context omitted.

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…

> 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 potentia…

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.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#66

Post by shawntan » Sat, Jul 22, 2023, 5:05 AM UTC

gwern wrote: post #64

shawntan wrote: post #52

Earlier quoted context omitted.

I suppose you mean in order to give the answer to a Sudoku puzzle, you'd need a string of tokens anyway: [(x,y) grid coordinates], [digit]. I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do. My guess is that the straightforward output of the exact solution, even though it requires several t…

> I think if we're getting specific to this particular Sudoku example, the CoT would probably involve a trace of the entire filling-in and backtracking steps that a solver would do. Yes, and maybe the occasional generation of the complete boardstate to date, because you don't want to leave the boardstate implicit and require it to be reconstructed within each forward pass - that's 'using up serial computations' that…

Right, I see your point. Since Sudoku is fixed-size, you can always construct a Transformer with the worse-case depth. That makes sense.

I was assuming given a trained Transformer, you wouldn't know how many effective "steps of computation" it contained, and so would probably have to resort to CoT.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#67

Post by sfn42 » Sat, Jul 22, 2023, 8:30 PM UTC

joe_the_user wrote: post #18

earthboundkid wrote: post #8

An LLM is a tool. It is a very versatile tool. It can be used in many situations. It does not therefore follow that it should be used in all situations. Even if you wanted to use an AI to solve sudoku, there is no particular reason to begin with a model trained for language modeling instead of a model better suited to the task.

I would, uh, bet that you're right. But given that there has been a lot of discussion of the possibility that an LLM has "general intelligence", it seems worthwhile to figure out whether the solving of a random problem is possible.

They don't possess general intelligence, end of discussion. Thanks for attending my TED talk.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#68

Post by earthboundkid » Sun, Jul 23, 2023, 1:31 AM UTC

sfn42 wrote: post #67

joe_the_user wrote: post #18

Earlier quoted context omitted.

I would, uh, bet that you're right. But given that there has been a lot of discussion of the possibility that an LLM has "general intelligence", it seems worthwhile to figure out whether the solving of a random problem is possible.

They don't possess general intelligence, end of discussion. Thanks for attending my TED talk.

Seriously. Will someone make general intelligence by gluing together an LLM and some other AI stuff? I dunno, maybe. But currently existing LLMs don’t have GI and it’s really easy to show this by chatting with them and asking them GI questions not in the training data.