Let $A$ be a finite algebra for some finitary signature.



> 
> 
> > 
> > Is it decidable whether $\mathbb{H}\mathbb{S}\mathbb{P}(A) = \mathbb{I}\mathbb{S}\mathbb{P}(A)$?
> > 
> > 
> > 
> 
> 
> 


That is, whether the variety generated by $A$ equals the quasivariety generated by $A$?



Is HSP(A) = ISP(A) decidable?
First, note that the problem is $\Pi^0\_1$: $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ iff every quasiidentity valid in $A$ holds in $\mathrm{HSP}(A)$. The latter can be algorithmically checked, as a quasiidentity in $n$ variables that fails in an algebra from $\mathrm{HSP}(A)$ also fails in an $n$-generated such algebra, i.e., a quotient of the free $\mathrm{HSP}(A)$-algebra over $n$ generators. The latter is finite and can be explicitly computed.


For various classes of algebras, the problem is in fact decidable.


For a simple case, $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ is decidable if it is known a priori that $V=\mathrm{HSP}(A)$ is congruence-distributive. Namely, $V$ is ISP-generated by its subdirectly irreducible algebras, and by Jónsson’s lemma, these are all in $\mathrm{HS}(A)$. Moreover, a subdirectly irreducible algebra is in $\mathrm{ISP}(A)$ iff it is in $\mathrm{IS}(A)$. It is decidable whether a finite algebra is subdirectly irreducible, hence you can test whether $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ by enumerating all subdirectly irreducible algebras in $\mathrm{HS}(A)$ (up to isomorphism, there are only finitely many), and checking that each is in $\mathrm{IS}(A)$.


More generally, assume that $A$ comes from a class of algebras such that we can compute a finite upper bound $b$ on the size of subdirectly irreducible algebras in $\mathrm{HSP}(A)$, or determine that there is no bound. (Such classes of algebras are said to satisfy the recursive RS conjecture.) Then $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ iff $b$ exists and all s.i. algebras from $\mathrm{HSP}(A)$ of size at most $b$ are in $\mathrm{IS}(A)$, which is a decidable criterion.


Various results related to the RS conjecture are summarized in [1]. In particular, $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ is decidable in the following cases:


* $\mathrm{HSP}(A)$ is congruence-modular (Thm. 4.2, due to Freese and McKenzie).
* More generally, if the congruence lattices of all algebras in $\mathrm{HSP}(A)$ satisfy a nontrivial lattice equation (Thm. 5.13, due to Hobby and McKenzie).
* $\mathrm{HSP}(A)$ is abelian (Thm. 6.17, due to Kearnes, Kiss, and Valeriote).


On the other hand, the recursive RS conjecture is false in general (Thm. 6.5, McKenzie). This suggests that $\mathrm{HSP}(A)=\mathrm{ISP}(A)$ might also be undecidable in full generality, however this does not seem to directly follow from any of the result I could find.


Reference:


[1] Ross Willard, [An overview of modern universal algebra](http://www.math.uwaterloo.ca/~rdwillar/documents/Publications/torino.pdf), in: Logic Colloquium 2004 (eds. A. Andretta, K. Kearnes, and D. Zambella), Lecture Notes in Logic, vol. 29, Cambridge University Press, 2008, pp. 197–220.


