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
    Commented 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
    Commented 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
    Commented Feb 20, 2014 at 13:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .