# Questions tagged [decidability]

The decidability tag has no usage guidance.

112
questions

**12**

votes

**1**answer

271 views

### Commutator problem vs conjugacy/word problem

For a finitely presented group $G$, generated by a finite set $A$, the commutator problem is the decision problem: given a word $w$ over the alphabet $A \cup A^{-1}$, can one decide if $w$ is a ...

**4**

votes

**1**answer

170 views

### Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?

Given a Diophantine equation it is not decidable if it has integer solution.
I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties
every member in $\mathcal D_{unique}$ is a ...

**3**

votes

**0**answers

96 views

### Variation in decidability of diophantine equations with field extension

Let $O_k$ be the ring of integers in a subfield $k$ of $\overline{\mathbb{Q}}$. Let's call an equation $p(x_1, \dots, x_n) = 0$ where $p$ is a polynomial in $n$-variables $x_1, \dots, x_n$ with ...

**12**

votes

**1**answer

520 views

### Testing whether $e^x+ax^2+bx+c$ has a zero

What is the simple test with exponential polynomials to determine whether
$$f(x)=e^x+ax^2+bx+c$$ has a positive zero?
This was prompted by the question about discriminants here. We have an ineffective ...

**6**

votes

**0**answers

66 views

### The conjugacy problem for two-relator groups

Is the conjugacy problem for two-relator groups known to be undecidable?
The word problem for two-relator groups is a famous open problem (appearing e.g. as Question 9.29 in the Kourovka notebook), ...

**6**

votes

**1**answer

502 views

### Do we have an algorithm for comparing $e^e$ with rationals?

Do we have an algorithm for comparing $e^e$ with rationals, with a known time to convergence?
In a non-constructive sense, there obviously is an algorithm.
If $e^e$ is some rational $q_0$, then we ...

**5**

votes

**2**answers

248 views

### Checking for finite fibers in hash functions

Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\...

**0**

votes

**0**answers

109 views

### Genus $0$ algebraic curves integral points decidable?

It is known there is an explicit algebraic variety in $\mathbb Z[x_1,\dots,x_t]$ a bounded $t>2$ whose integral zero-set is non-empty is undecidable.
If the variety has genus $0$ is there anything ...

**4**

votes

**1**answer

86 views

### Monadic second order theory of “backwards tree” — is it decidable?

A famous result by Rabin states that the monadic second order theory of the binary tree is decidable. By the binary tree, understand the free monoid $\{0,1\}^*$ of words, with operations $S_0(w)=w0$ ...

**11**

votes

**2**answers

420 views

### Decidability of a first-order theory of hyperreals

The theory of real closed fields is decidable. The hyperreals satisfy that theory, so we can interpret statements in the theory of real closed fields as being about hyperreals.
If we add a unary ...

**0**

votes

**1**answer

104 views

### Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...

**8**

votes

**0**answers

134 views

### Membership problem in general linear group

This is surely a very well known problem, but I could not find an answer on MO or on Google, so here I am.
Given some finitely generated free subgroup $H$ of $\operatorname{GL}_n(\mathbb{Z}[t,t^{-1}])...

**3**

votes

**0**answers

88 views

### Post correspondence problem: Busy beaver variant

The Post correspondence problem (Wikipedia link) is to decide for $k$ pairs of strings $$(a_1,b_1), (a_2, b_2), ..., (a_k,b_k),$$ if there exists a finite sequence of numbers $c_j, 0\le j\le j_\max $ ...

**9**

votes

**2**answers

316 views

### Reference request: Recent progress on the conjugacy problem for torsion-free one-relator groups?

I am aware that the Spelling Theorem of B. B. Newman implies that one-relator groups with torsion are hyperbolic, and thus have a solvable conjugacy problem. My understanding is that for one-relator ...

**-2**

votes

**1**answer

107 views

### Undecidable definition of mathematical expressions?

I am arguing a bit on Facebook regarding the definition of a mathematical expression. Some argue that equations are not expressions (and there are a few possibly dubious online sources which states ...

**1**

vote

**1**answer

309 views

### Which Hilbert's 10th polynomials are known to have solutions?

The Diophantine equation
$$x^3 + y^3 + z^3 = 42$$
was recently solved by
Booker and Sutherland:
Sum of three cubes for 42 finally solved.
Is there a clean partition of the form of those
polynomial ...

**6**

votes

**1**answer

163 views

### Is $\mathbb{F}_{p}(t)^{h}$ an elementary substructure of/existentially closed in $\mathbb{F}_{p}((t))$?

It is a well-known fact that the Henselization of the function field $\mathbb{F}_{p}(t)$ in regard to the $t$-adic valuation is $\mathbb{F}_{p}(t)^{alg} \cap \mathbb{F}_{p}((t))$, so of course $\...

**12**

votes

**1**answer

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

**3**

votes

**0**answers

250 views

### Are there any references in the literature relating to work on finding a Diophantine equation representing abc

The Davis-Putnam-Robinson-Matiyasevich theorem is:
Diophantine is equivalent to listable
This result has some known applications:
(1) Prime-producing polynomials.
(2) Diophantine statement of the ...

**6**

votes

**3**answers

439 views

### How much of the Cantor-Schröder-Bernstein theorem is constructively recoverable if the injections have retractions and decidable images?

This is cross-posted from MSE at the suggestion of a comment after receiving no answers over a few weeks.
Suppose we have $f : A \to B$ and $g : B \to A$, as well as left inverses $f_r : B \to A$ of $...

**16**

votes

**3**answers

1k views

### Is Multilinear Hilbert's tenth problem version undecidable?

A multilinear polynomial $f\in\mathbb Z[x_1,\dots,x_t]$ has terms only of form $$b\prod_{i=1}^tx_i^{a_i}$$ where $a_i\in\{0,1\}$ and $b\in\mathbb Z$.
Is there no general purpose algorithm for ...

**5**

votes

**0**answers

127 views

### Example of applying real quantifier elimination algorithm for polynomials

Sorry if any of this is unclear, or doesn't make much sense, I'm still trying to figure it out, a practical example such as this would likely help me understand better than anything else. I have read ...

**8**

votes

**1**answer

266 views

### Is equality of formulas with floor rounding or integer division decidable?

As far as I know, formulae involving rationals and basic arithmetic ($+$, $-$, $\cdot$ and $/$) have decidable equality. Is this still the case if we add floor rounding (or integer division)?
Define ...

**1**

vote

**0**answers

66 views

### Decidability of linear equation about Sine and Cosine

Given integers $n,d$, and rational numbers $a_i,b_i,l_{i,j},s_{i,j}$ for $1\leq i\leq d$, $1\leq j\leq n$, we are considering the following equation
$$
\sum_{i} [a_i \sin(\sum l_{i,j}\theta_j)+b_i \...

**0**

votes

**0**answers

70 views

### Multivariate polynomial with infinite but discrete roots on one variable

I want to know if there exists a polynomial $ P(z, x_1,x_2,\ldots,x_n)$ over the rationals such that the set
$$
Z_P = \{z | \exists x_1,\ldots,x_n. P(z, x_1,x_2,\ldots,x_n) = 0 \} \subsetneq \mathbb Q
...

**2**

votes

**0**answers

131 views

### Compare my software's representation of exponential numbers and 0?

Suppose I have a real number
$$
x=\sum_{i=1}^n a_i e^{\lambda_i}
$$
where $a_i,\lambda_i$s are complex algebraic numbers.
Is there an algorithm to determine whether it is greater than 0 or less than ...

**1**

vote

**1**answer

122 views

### decidability of regularity of a language depending on representation

It is well known that many decision problems for regular languages are decidable. However, the proofs seem to rely on a witness of the regularity of said language, be it an automaton, a grammar, a ...

**53**

votes

**8**answers

5k views

### Two (probably) equal real numbers which are not proved to be equal?

Can someone give me a nice example of two computable real numbers which are believed but not proved to be equal?
I never really understood the assertion that "the reals do not have decidable equality"...

**2**

votes

**0**answers

123 views

### Can we “invert” Diophantine equations such as $x^3+y^3+z^3=k$ in to halting probabilities for some universal Turing machine?

Following Pooten [1], Davis[2], Chaitin [3], and Ord and Kieu [4]:
Is it possible that there is a polynomial $P$ of degree $d\le 4$, along with a prefix-free universal Turing machine $T$, such that ...

**8**

votes

**1**answer

437 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

122 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

133 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

50 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

227 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

172 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

206 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

88 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

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

102 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

101 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

344 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

683 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

168 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

79 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 \...

**36**

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

442 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

356 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

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

**3**

votes

**1**answer

703 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

86 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}$....