Talk:God's algorithm

From Wikipedia, the free encyclopedia

This article was nominated for deletion on 10 May 2006. The result of the discussion was keep.

Okay, the following claims need citations:

1. God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle
2. ...but which can also be applied to other combinatorial puzzles
3. ...and mathematical games.
4. The notion applies to puzzles that can assume a finite number of "configurations"... God's algorithm, then, for a given puzzle, is an algorithm that solves the puzzle and produces only optimal solutions.
5. For the notion of "God's algorithm" to be meaningful, it must further be required that the algorithm be practical...
6. For the Towers of Hanoi puzzle, a God's algorithm exists for any given number of disks.

These are all reasonable ideas, but where do they come from? Melchoir 21:36, 23 September 2006 (UTC)

I believe that the claim that "For the notion of "God's algorithm" to be meaningful, it must further be required that the algorithm be practical" is in fact incorrect. The normal usage of the term "God's algorithm" is precisely the opposite; it's the theoretically best algorithm, whether or not it is practical. For example, in this 1995 essay by Peter Suber, he says "That is, we do not know whether "God's Algorithm" is a family of methods with some learnable structure, or whether it is a chaotic tangle of disconnected pathways.", implying that he would consider a tangle of disconnected pathways to be a "God's algorithm". Indeed, the very name "God's algorithm" seems to me to have been invented to indicate that this was the best algorithm, neglecting considerations of practicality to a mere mortal. I have never, outside this page, seen a requirement that an algorithm be practical to be considered a "God's algorithm". I will wait a week to see if such a reference is posted, then edit the main page to correct this if there is no such reference posted. Andylatto 15:59, 29 January 2007 (UTC)

Fine. I added some references but left in {{unreferenced}} since not all of your concerns have been addressed. I removed {{OR}} since there appears to be no original research in the page. CRGreathouse (t | c) 01:47, 25 September 2006 (UTC)

Well, it still looks like original research to me. The Towers of Hanoi reference doesn't speak of "God's algorithms" or any other concept that is claimed to have historically arisen from the Rubik's cube. How is it relevant to this article? Melchoir 02:14, 25 September 2006 (UTC)

The reference shows a "practical algorithm that produces a solution having the least possible number of moves" for the generalized Tower of Hanoi puzzle. You're right, it doesn't use the term, but I was just trying to get the soircing started. There are no sources on the origin of the term -- for all I know the term started with the Tower of Hanoi and was later applied to Rubik's Cube. (I've read otherwise, but I have no references handy. We already agree that the article needs references, though, so there's no argument there.)

I've numbered your claims, above. (1) needs a reference. That the concept can be applied to other puzzles and games is sufficiently obvious that it needs no reference, but I'm sure one can be found if needed for (2) and (3). (4) and (5) follow directly from the definition, and as such need no source; of course you may be pointing out that no reference actually gives a sufficient definition (I haven't read the reference that was already in the article, it probably has a definition but I don't know) in which case I agree. (6) I have addressed with a reference. CRGreathouse (t | c) 06:40, 25 September 2006 (UTC)

again, I don't think it's correct that (5) follows from the definition. Every usage I've seen of the term "God's algorithm" refers to the theoretically best algorithm, whether practical to those who are not gods or not. Andylatto 15:59, 29 January 2007 (UTC)

The problem of terminology and definitions is troubling to me. It's way too easy to extend concepts to wider and wider contexts, but without any nontrivial results addressing an extension, it's not so easy to demonstrate that it's the right one or that it's useful or notable. And on Wikipedia, extending a definition beyond its verifiable meanings violates WP:NOR. I suspect that Cube enthusiasts on the Internet are reinventing the square wheel with this concept. But I'm not familiar with the established body of research on algorithms, so I could be wrong. I'll just urge everyone to be skeptical about things that seem obvious or seem to follow directly, but which might have been made up here. Melchoir 07:43, 25 September 2006 (UTC)

Googling "God's algorithm" gives plenty of early hits that show where the term comes from, such as this 1992 posting by Dik T. Winter to the cube-lovers list, this 1995 essay by Peter Suber on a variation to the game, and this 1996 posting to sci.math. All hits of an early date use the term in connection with Rubik's cube. It is also easy to find many hits that show how the term is presently commonly understood, such as this announcement of an optimal solver. The way-back machine shows the term in use like that on that page on July 25, 2003. Other examples: Kociemba's solver, Jaap's puzzle site.

The text in the referenced Joyner book seems to be the same as this text from a draft of a book called "Applied Abstract Algebra", namely: "Let G be the group of a permutation puzzle. Find the diameter of the Cayley graph of G. Sometimes this is called God's algorithm, though here that term is reserved for a harder version of the problem, stated below. This diameter problem is unsolved for must puzzles (including the Rubik's cube) and appears to be very difficult computationally (see [J1] for a discussion of similar problems). [...] Let G be the group of a permutation puzzle and let v be a vertex in the Cayley graph of G. Find an algorithm for determining a path from v to the vertex v₀ associated to the identity having length equal to the distance from v to v₀. This problem is much harder. The algorithm, if it exists, is called God's algorithm." This definition is more restricted since it only applies to permutation puzzles. The earliest use I found, the posting by Dik T. Winter mentioned, above discusses upper bounds on the lengths of optimal solutions for Rubik's cube, which corresponds to the diameter in the associated graph -- which happens to be a Cayley graph for this puzzle. The essay by Peter Suber really discusses algorithms, not just diameters. Although I don't have evidence to back this up, it is clear from the Winter posting that the term was already in use, and it is eminently reasonable to assume that the term originally was introduced for some notion of solving algorithm instead of "just" for a graph diameter. Most of the web references I gave illustrating present use, even when in the context of Rubik's cube, give a definition that does not explicitly apply specifically to the cube but is more general.

Can these web references used as references adressing Melchoir's concerns (1) and (2)?

My personal feeling is, if anyone who cares (and has access to a browser) can easily verify out that the term comes from discussions on optimal solutions to Rubik's cube, and see for themselves that the present use has a more general definition, then we need not insist on references to "reliable sources" stating this as a fact. --Lambiam^Talk 13:13, 25 September 2006 (UTC)

[edit] Unclear

While reading this it was not clear to me if that was a notion or an specific algorithm. At first I thought that it was a real algorithm called god's algorithm, by the end of the article I began to think that in a fact that an algorithm can be called a "god algorithm" if it fit the definition. May be the blurb at beginning should be adapted to make this more clear.

The first two sentences of the introductory paragraph go like this:

God's algorithm is a notion [...]. It stands for any practical algorithm that [...].

(my italics). I'd think that this clinches it that God's algorithm is a notion and not a specific algorithm.  --Lambiam^Talk