All Questions
Tagged with decidability ra.rings-and-algebras
5 questions
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 ...
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 ...
3
votes
1
answer
360
views
Is the equational theory of commutative vN regular rings decidable?
I wanted to check whether $A(x,y):=\frac{xy}{x+y}$ is an associative operation in every commutative vN regular ring. Now $A(-1,A(1,1))=A(-1,\frac{1}{2})=1\neq 0 =A(0,1)=A(A(-1,1),1)$. On the other ...
8
votes
1
answer
329
views
Algorithmic decidability of equality in the ring of periods
Suppose two elements of the ring of periods are given by their systems of polynomial inequalities with rational coefficients. Is there a known algorithm deciding their equality? Is it known if their ...
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 ...