15
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
18
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2012 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, 2012 at 5:45
  • 1
    $\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, 2014 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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