Talk:Krohn-Rhodes theory

From Wikipedia, the free encyclopedia

The article is incorrect. John Rhodes proved that semigroup complexity for a finite semigroup is indeed decidable. The following link to an invitation to a year 2000 seminar entitled "Techniques in my Proof that Complexity is Decidable for Finite Automata and Semigroups" given in Hungary should suffice as evidence: http://atlas-conferences.com/c/a/e/c/44.htm

I took a course from John Rhodes, and while he didn't describe the algorithm he did say that he got the idea for it while vacationing at the Horizons Casino in Stateline, NV (on the shores of Lake Tahoe). The algorithm is reportedly so complex that an ackermann function, one of the fastest growing functions known to man, describes the runtime as a function of input complexity.

The proof I think you are referring to was incorrect (as is now acknowledged by Rhodes himself). It relied upon on a published theorem of some other authors (who shall remain nameless), the proof of which turned out to have an error in it. Rhodes is still working on this problem and I understand has another idea for how decidability can be proved, but this has not yet been published or peer-reviewed. Best wishes, Cambyses 08:11, 20 March 2006 (UTC)

Thanks that's very current information. I stand corrected. -- skyscrapes

That's okay. It's good to know these relatively obscure articles are being checked by people who are actually familiar with the subjects! Best wishes, Cambyses 07:54, 24 March 2006 (UTC)