# Questions tagged [decidability]

The decidability tag has no usage guidance.

**6**

votes

**1**answer

216 views

### Do any finite predictions of Quantum Mechanics depend on the set theoretic axioms used?

I was wondering if any of the finite predictions of Quantum Mechanics depend on what set theoretic axioms are used.
We will say that Quantum Mechanics makes a finite prediction about an experiment if,...

**1**

vote

**1**answer

62 views

### Decidability of S2S with real numbers

Is the theory of natural numbers and functions $ℕ → ℝ$ decidable under:
- for natural numbers: $\mathrm{succ1}(n) = 2n+1$; $\mathrm{succ2}(n) = 2n+2$; equality
- for functions: pointwise addition and ...

**4**

votes

**0**answers

115 views

### Subgroup membership problem for Noetherian groups

I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group,
\begin{...

**1**

vote

**0**answers

43 views

### Equality of combinations of exponentials and logarithms

Suppose I have some combination of exponentials, logarithms, and arithmetic operations on rational numbers. For example, $e^{e^{r_1} + \log r_2} - r_3$. Under what conditions does an algorithm exist ...

**2**

votes

**0**answers

133 views

### minimum size of undecidable quadratic diophantine problems

According to Matiyasevich, the existence of integer solutions of systems of polynomial equations with integer coefficients is undecidable. By introducing additional variables substituting factors of ...

**2**

votes

**0**answers

144 views

### The elementary theory of finite commutative rings

I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...

**1**

vote

**1**answer

142 views

### Is Calculus of Constructions type inhabitance semi-decideable?

I'm wondering if type inhabitance for the calculus of constructions is semi-decideable. I know the following:
System F inhabitance and, correspondingly, second-order unification are semi-decideable
...

**2**

votes

**0**answers

86 views

### Is the equational theory of the variety of ternary self-distributive algebras decidable?

A ternary self-distributive algebra is an algebra $(X,t)$ that satisfies the identity $$t(u,v,t(x,y,z))=t(t(u,v,x),t(u,v,y),t(u,v,z)).$$
Is the equational theory of the variety of ternary self-...

**11**

votes

**3**answers

846 views

### Undecidable easy arithmetical statement

Is there a basic arithmetic statement which is known to be undecidable ?
By basic arithmetic statement I do mean an easy statement in the spirit of the Collatz conjecture . By the way is there some ...

**4**

votes

**0**answers

86 views

### Deciding equality in free models of a (generalized) Lawvere theory

Let $F : \mathcal{C} \rightarrow \mathcal{D}$ be functor of Lawvere theories $\mathcal{C}, \mathcal{D}$ (i.e. cartesian categories where every object is isomorphic to some power of a chosen object) ...

**6**

votes

**1**answer

79 views

### Decidability and Cluster algebras

Recall the definition of a cluster algebra,
which can be seen as a (possibly infinite) graph, where each vertex is a tuple of a quiver and Laurent expressions at some of the vertices of the quiver. ...

**5**

votes

**1**answer

275 views

### Undecidability of Diophantine equations with disjoint variables?

Consider a special case of the Hilbert's 10th problem:
$f(\vec{x})=g(\vec{y})$, where $\vec{x}$ and $\vec{y}$ are disjoint ( i.e, the LHS and RHS do not have any common variables), moreover, $f$ and $...

**6**

votes

**2**answers

386 views

### Are omega-consistent extensions of PA always consistent with each other?

The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just:
...

**5**

votes

**0**answers

131 views

### Rabin's proofs of emptiness and complementation problems for automata on infinite trees

I have originally asked this question on Math.SE, but I think it is more suitable here.
I have been reading M. Rabin's 1969 article Decidability of Second-Order Theories and Automata on Infinite ...

**2**

votes

**0**answers

74 views

### Matrix (geometric sum) orbit problem

Is the following algorithmic problem known to be decidable/undecidable?
Input: an element $\mathbf{v} \in \mathbb{Z}^n$, a matrix $\mathbf{A} \in GL_n(\mathbb{Z})$, and a subgroup $H \leqslant \...

**35**

votes

**3**answers

2k views

### Is it decidable to check if an element has finite order or not?

Suppose we have a finitely presented group $G$ with decidable word problem. Is it decidable to check whether a given element $x\in G$ has finite order or infinite?

**10**

votes

**1**answer

398 views

### Are the terms of a linear recurrence integral?

Given rational numbers $a_1,\ldots, a_k$ and $u_0, \ldots, u_k$, let $(u_n)_{n \geq k}$ be the linear recurrence defined by
$$u_n := a_1 u_{n-1} + \cdots + a_k u_{n-k}, \text{ for } n \geq k .$$
...

**8**

votes

**1**answer

318 views

### Can we algorithmically contract loops in a simply connected space?

It is well-known that the question whether a given connected simplicial complex (or simplicial set) is simply connected, is algorithmically undecidable as it can model the word problem.
Assuming ...

**2**

votes

**1**answer

105 views

### Understanding the paper: “Guarded Fixed Point Logic”

This question is specifically about the paper "Guarded Fixed Point Logic" by Gradel and Walukiewicz. Among other things they prove the decidability of the satisfiability problem for Fixpoint Loosely ...

**2**

votes

**1**answer

460 views

### Provably undecidable problems within prime numbers context

A colleague of mine was stating there are no known undecidable statements that have explicit connection with prime numbers. What does this mean? I understand that it is unknown whether Goldbach ...

**1**

vote

**0**answers

81 views

### determine the existence of positive semi-definite matrix

Given a $d\times d$ complex matrix subspace $S$, we are asking whether there is some finite integer $n$ such that there exists a non-zero positive semi-definite matrix is orthogonal to $S^{\otimes n}$....

**3**

votes

**1**answer

132 views

### Relationship between computational undecidability and axiomatic undecidability

On surface, these seem two completely different class of problems. One class represent statements which can't be proved or disproved in an axiomatic theory. For example
One can write down a ...

**5**

votes

**0**answers

254 views

### Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?

Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).

**6**

votes

**1**answer

226 views

### Deciding isomorphism between graphs which interpret in the pure set

I am interested in the following decision problem:
Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....

**13**

votes

**1**answer

420 views

### Is this theory decidable?

It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant ...

**0**

votes

**0**answers

175 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the (...

**2**

votes

**1**answer

292 views

### Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables

I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...

**6**

votes

**1**answer

395 views

### Show that the positive existential theory is undecidable

To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...

**19**

votes

**3**answers

958 views

### Is being rational decidable?

Given a real number uniquely defined by a finite system of equations and inequalities with rational coefficients involving the standard elementary functions only. Is it decidable whether this number ...

**7**

votes

**1**answer

355 views

### List of finitely presented groups with undecidable word problem

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?
By "representative" I mean "avoiding obvious redundancy", i.e. examples ...

**7**

votes

**0**answers

389 views

### Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...

**1**

vote

**1**answer

200 views

### Recurrence relations with polynomial coefficients: an undecidable problem

I read once (somewhere) that solving a recurrence relation with polynomial coefficients, in the general case, is an undecidable problem. I can't remember the exact reference and I've been trying to ...

**4**

votes

**0**answers

130 views

### Undecidability of the existential theory

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, ...

**2**

votes

**0**answers

96 views

### Positive existential theory of $(\mathbb{Z}; +, |_n)$

I am reading a paper and there is the following theorem:
Let $n$ be a fixed integer, and $n >1$.
Denote divisibility in $\mathbb{Z}[\frac{1}{n}]$ by $|_n$, thus for
all $x, y \in \...

**14**

votes

**0**answers

257 views

### Is tightness decidable?

Given a contact structure on a three-manifold, is there an algorithm to decide whether or not it tight?
For concreteness' sake, let's agree to represent the given contact three-manifold via an open ...

**0**

votes

**2**answers

214 views

### Undecidable set of problems [closed]

Is there some set of problems, for which determining if given problem is decidable or not is itself undecidable?

**-1**

votes

**1**answer

343 views

### Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...

**2**

votes

**0**answers

39 views

### Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...

**7**

votes

**1**answer

207 views

### Decidability of an Algebraic System in Real Numbers

Is there an algorithm to decide whether an algebraic system
\begin{gathered}
{f_1}({x_1}, \ldots ,{x_n}) = 0 \hfill \\
\vdots \hfill \\
{f_m}({x_1}, \ldots ,{x_n}) = 0 \hfill \\
\end{...

**2**

votes

**2**answers

174 views

### Pseudo-decision procedures for first order arithmetic

I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.2911&rep=rep1&type=pdf in which the author describes an algorithm, based on Groebner basis, ...

**16**

votes

**0**answers

559 views

### Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...

**21**

votes

**2**answers

1k 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

**0**answers

51 views

### Decidability of first order theory of subclasses of posets

Is the first order theory of finite posets known to be undecidable?
Does anyone know a survey about such results?

**3**

votes

**1**answer

275 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 ...

**11**

votes

**2**answers

1k views

### Decidability of decidability

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "...

**6**

votes

**2**answers

180 views

### Algorithm for determining when polynomial iteration is bounded?

Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates $f(p),...

**9**

votes

**2**answers

888 views

### Undecidable puzzles

There are plenty of popular NP-hard puzzles,
for example, generalized Sudoku ($n^2 \times n^2$-board), Flow (I cannot give a source for this), Minesweeper, etc.
Recently, I read a bit about aperiodic ...

**1**

vote

**0**answers

90 views

### What is the generic complexity of First Order Predicate Calculus?

I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...

**4**

votes

**1**answer

368 views

### Quantifier elimination vs decidability

Quantifier elimination is used as a technique to get decidability (e.g. $Th( \mathbb{N}, +)$ ) of theories, but typically one has to go over to some expansion. Are there examples of theories which are ...

**1**

vote

**0**answers

85 views

### unique types and decidability

Suppose $\mathcal{M}$ is an infinite structure which has the property that every type that is realised is realised uniquely. Also assume that every element of $\mathcal{M}$ is definable but there is ...