14
$\begingroup$

In representation theory, there is a well-known notion of a wild classification problem (such problems have been discussed often on this forum, for example, here). In logic, there is a notion of an undecidable problem.

Is there a theorem which says that there is something undecidable about a wild classification problem?

A reference where such issues are discussed would be very helpful.

$\endgroup$
16
$\begingroup$

Yes, there is a connection, but I think it is conjectural in its full generality. The mosst general reference could be, where it is proven, that for a subclass of wild algebras, the representation theory is undecidable:

Mike Prest: Wild representation type and undecidability, Comm. Alg. 19 (3), 1991.

It is also well-known (it is stated with references for example in Benson), that the representation theory of the algebra used to define wildness (i.e. $k\langle X,Y\rangle$) is undecidable.

$\endgroup$
  • 2
    $\begingroup$ You're welcome. Please mark as answered. $\endgroup$ – Julian Kuelshammer Aug 29 '11 at 10:43
  • $\begingroup$ Done. Sorry about the delay. $\endgroup$ – Amritanshu Prasad Aug 31 '11 at 16:00
  • $\begingroup$ Note that all articles I could find in the literature show that the infinite dimensional representation theory is undecidable for wild quivers. I have a proof for the finite dimensional representation theory and will post one day on ArXiv. It is not difficult. $\endgroup$ – Benjamin Steinberg Sep 17 '12 at 15:06
  • $\begingroup$ @Benjamin: would Prest's proof fail for the theory of finite dimensional representations? In that case it does not really address the matrix pair problem, which is really about finite dimensional representations. $\endgroup$ – Amritanshu Prasad Sep 20 '12 at 5:45
  • $\begingroup$ @AmritanshuPrasad, His proof uses the regular representation of an infinite group with undec word problem so fails. I give a proof on my blog which works by using the uniform word problem for finite semigroups. $\endgroup$ – Benjamin Steinberg Feb 20 '14 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.