Skip to main content

All Questions

Filter by
Sorted by
Tagged with
13 votes
1 answer
811 views

Is there a ring for which the reducibility of a polynomial is undecidable?

Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$. Then we can decide whether a polynomial in $R[t]$ is reducible ...
Lucio Tanzini's user avatar
24 votes
2 answers
2k views

What do you do if you believe a problem is undecidable?

While the title of this question is subjective, I hope to make what I'm looking for quite concrete. The first, and main question is this: If you believe that a problem you are working on is formally ...
Pace Nielsen's user avatar
  • 18.7k
7 votes
3 answers
915 views

Decidability of matrix algebra

Take multi-sorted first-order logic with equality, complex scalars, 1xn vectors, nx1 vectors, nxn matrices, addition and multiplication for each pair of sorts they make sense for, and hermitian ...
user avatar