Questions tagged [decidability]
The decidability tag has no usage guidance.
46
questions with no upvoted or accepted answers
17
votes
0
answers
779
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^...
- 171
16
votes
0
answers
327
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 ...
- 18.3k
8
votes
0
answers
232
views
Hilbert 10th problem for genus 2 equations
Hilbert 10th problem, while undecidable in general, remains open for 2-variable equations: we do not know if there is an algorithm that, for polynomial $P(x,y)$ with integer coefficients, decides ...
- 5,957
8
votes
0
answers
111
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), ...
8
votes
0
answers
252
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}])...
- 469
7
votes
0
answers
261
views
Uniform word problem in finitely presented simple groups
The following question arose in the comments on this question, and it seems like a reasonable question to ask in its own right. I've added some additional details.
The word problem in any fixed ...
7
votes
0
answers
271
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 ...
- 13.7k
7
votes
0
answers
607
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 ...
user5810
5
votes
0
answers
203
views
Integer points of rational function in 2 variables
Is there an algorithm that, given polynomials $P(x)$ and $Q(y)$ with integer coefficients, decides whether there exists integers $x$ and $y$ such that $\frac{P(x)}{Q(y)}$ is an integer?
This is a ...
- 5,957
5
votes
0
answers
162
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 ...
- 51
5
votes
0
answers
282
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).
4
votes
0
answers
157
views
Undecidability for hyperbolic Wang-tilings - pentagons, heptagons, octagons, oh my!
Berger proved that the problem of determining if a finite set of Wang tiles can tile the plane is undecidable. Robinson reproved Berger's result and raised the question of considering the ...
- 5,319
4
votes
0
answers
155
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{...
- 333
4
votes
0
answers
347
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 ...
- 3,771
4
votes
0
answers
112
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) ...
4
votes
0
answers
154
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, ...
- 299
4
votes
0
answers
212
views
The theory of two finite linear orders
My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem):
Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...
- 13.9k
3
votes
0
answers
49
views
Maximal number of aperiodic Wang tiles
I was wondering whether there is an analogue result to the minimality of Wang tiling, in the direction of maximality.
I think that the paper by Jeandel and Rao, shows that the minimal number of Wang ...
- 567
3
votes
0
answers
96
views
Decidability of theory of modules over a ring of finite representation type
I have read from Mike Prest's model theory for modules (London lecture note series) chapter 17 that a Ring of finite representation type has a decidable theory of modules. Here decidability was ...
- 31
3
votes
0
answers
148
views
Why is the proof of decidability of arithmetic (Theorem 2.1) in Hamkins & Lewis (2000) enough?
Recently, I was reading the paper "Infinite Time Turing Machines" by Hamkins & Lewis. And one of the first theorems (Theorem 2.1) is about decidability of arithmetic.
The proof is quite ...
- 31
3
votes
0
answers
114
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 ...
- 31
3
votes
0
answers
116
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 $ ...
- 2,691
3
votes
0
answers
193
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 Poonen [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 ...
- 2,143
3
votes
0
answers
57
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
0
answers
174
views
What is the general feeling for Hilbert's 10th problem for Q?
We know that Hilbert's 10th problem for $\mathbb{Z}$ is undecidable. I was wondering whether there is a strong opinion in the mathematical community on the decidability of Hilbert's 10th for $\mathbb{...
- 53
2
votes
0
answers
70
views
Is parquetability decidable?
Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}...
- 45.5k
2
votes
0
answers
63
views
Decidability of the solvability of quadratic systems
Let a finite collection of (complex) unknowns $\{x_1,\ldots,x_n\}$ be given, as well as an affine system $AX=B$ in the quadratic variables $X:=[x_i x_j : i\leq j]$, with entries in a computable ...
- 5,289
2
votes
0
answers
137
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,493
2
votes
0
answers
213
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 ...
- 151
2
votes
0
answers
89
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-...
- 27.8k
2
votes
0
answers
89
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 \...
- 333
2
votes
0
answers
111
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 \...
- 299
2
votes
0
answers
46
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 ...
- 21
2
votes
0
answers
135
views
Extend Lowenheim's decidability result to fragment of second-order logic
Since relational monadic first-order logic has finite model property, its SAT problem is decidable. In H.Behmann's paper, he extended this result to fragment of SOL where all predicates, free and ...
- 63
1
vote
0
answers
66
views
Decidability of a polynomial-exponential equation in two variables
My question is with regards to the following (algorithmic) problem:
Problem. Given $f\in \mathbb{Z}[x,y], a,b\in \mathbb{Q}, r\in \mathbb{Z}$, do there exist positive integers $m,n$ such that $f(m,n) =...
- 151
1
vote
0
answers
101
views
Game with Turing machines
Introduction
The following game is quite nice: Alice has, in secret, constructed a polynomial $P \in \mathbb{Z}[x]$.
On day $n=1,2,3,...$, she secretly writes down $P(n)$ on a piece of paper.
Each day,...
- 15.6k
1
vote
0
answers
72
views
Non-degenerate solutions in multiplicative subgroups of $\mathbb{Q}$ of finite ranks
I am trying to study whether of a set of first order sentences is decidable, and the key is to figure out an algorithm to compute all non-degenerated solutions. The setting is as follow. Let $q = (q_{...
- 11
1
vote
0
answers
76
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 \...
- 1,493
1
vote
0
answers
55
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 ...
- 1,461
1
vote
0
answers
90
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}$....
- 1,493
1
vote
0
answers
114
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 ...
- 111
1
vote
0
answers
87
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 ...
0
votes
0
answers
117
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 ...
- 13.7k
0
votes
0
answers
96
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
...
- 163
0
votes
0
answers
195
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 (...
- 299
0
votes
0
answers
63
views
Is the question whether a FO formula F has a model of size k (k is a finite number) decidable?
Hi all,
can someone please tell me whether the question whether a FO formula F has a model of size k (where k is a finite number) is decidable?
Thanks in advance!
TL
