Context: A UFD (Unique Factorization Domain) is, well, an integral domain wherein elements may be factored uniquely. How to go about actually factoring these elements is unclear, but in certain instances, e.g. the integers or polynomial rings over a field, an algorithm exists. Such a domain is called a UFD with a factoring algorithm.
What are some examples of UFDs without a factoring algorithm?
I think we may have to be careful about how elements of the UFD are presented.
Consider the UFD $\mathbb R[X]$. For example, $X^2 - a$ factors as $(X+\sqrt{a})(X-\sqrt{a})$ if $a \ge 0$, while it's irreducible if $a < 0$. The trouble is that (in most formulations of the "constructible" real numbers), there is no algorithm to test whether or not $a \ge 0$. For example, given a Diophantine equation $P(x_1, \ldots, x_n) = 0$, let $a = -\sum_{j=0}^\infty b_j 2^{-j}$ where $b_j = 1$ if $P(x_1, \ldots, x_n)$ has a solution with all $x_i$ nonnegative integers $ \le j$, $0$ otherwise. Thus $a < 0$ if and only if the Diophantine equation has a solution. Since there is no algorithm to determine whether a Diophantine equation has solutions (Matiyasevich's theorem), there is no algorithm to factor polynomials of this type.