[thaumasiotes]

> I think a human will struggle to solve Hanoi using the recursive algorithm for even 6 disks, even given pen and paper.

Why? The whole point of the recursive algorithm is that it doesn't matter how many discs you're working with.

The ordinary children's toys that implement the puzzle are essentially always sold with more than 6 discs.

https://www.amazon.com/s?k=towers+of+hanoi

[GrayShade]

The recursive solution has a stack depth proportional to the number of disks. That's three pieces (two pegs and how many disks to move) of data for each recursive call, so for 6 disks the "stack" will contain up to around 15 values, which is generally higher than an unaided human will be able to track.

In addition, 64-256 moves is quite a lot and I suspect people will generally lose focus before completing them.

[James_K]

It's still pretty simple. I think you are really underestimating the ability of humans to do rote activities. Especially since we could give the human a pen and paper in this case and let them write stuff down on it to give parity to the AI which can write words in its output.

It seems pretty clear to me that learning how to go about following an arbitrary set of rules is a part of general intelligence. There are lots of humans who have learned this skill, and many (mostly children) who have not. If the AI has failed to learn this ability during its extensive training, and critically if it cannot be taught this ability as a human could, then it's certainly not "generally intelligent" to anywhere near the human degree.

[suddenlybananas]

You have to understand these people are fundamentally misanthropic, and think everyone but them is an idiot. That's why they're so impressed by LLMs even when they fail miserably.

[thaumasiotes]

You should try playing with one of the toys. It's not at all difficult to move 7 of them.

It's not necessary to use a stack. If you have a goal, you can work "top down", with nothing held in memory. All you need to know to begin the move is whether you're moving an odd number of discs (in which case, the first move will be onto the target peg) or an even number (in which case it will be onto the third peg).

[GrayShade]

Yes, I'm aware of the iterative solution, which is why I explicitly mentioned the recursive one.

They tried to give the algorithm description to the LLMs, but they also used the recursive solution (see page 25 of the paper).

[thaumasiotes]

What do you think a human using the recursive solution looks like?

If you ask someone how the puzzle works, they're overwhelmingly likely to tell you:

"To move disc 7, first you move discs 1-6 to the third peg, then you move disc 7[, and then you can put discs 1-6 back on top of it]."

This is an explicitly recursive statement of the solution. But the implementation is just that you count down from 7 to 1 while toggling which peg is "the third peg". You can optimize that further by dividing 7 by 2 and taking the remainder, but even if you don't do that, you're using constant space.

What would a human be doing (or thinking) differently, if they were using the recursive algorithm?