Questions tagged [decidability]
The decidability tag has no usage guidance.
154
questions
8
votes
1
answer
248
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{...
- 751
8
votes
1
answer
350
views
Decidable theories with arbitrary complexity
Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity?
Here, arbitrarily high (computational) complexity means that for every ...
- 6,112
8
votes
1
answer
324
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 ...
- 6,709
8
votes
1
answer
719
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 ...
- 333
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
112
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
253
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
3
answers
663
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 $...
- 295
7
votes
1
answer
239
views
Decidability of completing Penrose tilings
Is the following problem known to be un/decidable? Problem: Given a finite configuration of Penrose tiles in the plane, determine if there is an extension of the configuration tiling the whole plane.
- 449
7
votes
2
answers
439
views
Decidability of differential equations
Is there anything well-known about the algorithmic decidability of the satisfiability of an ODE $\dot{x}=f(x)$, $x: [0,1]\to R^n$ with an initial condition $x(0)=x_0$, given that $f(x)$ belongs to ...
- 962
7
votes
1
answer
227
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
- 429
7
votes
2
answers
238
views
Congruences of binomial sums
Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...
- 16.3k
7
votes
3
answers
902
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 ...
user5810
7
votes
1
answer
255
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 $\...
- 311
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
6
votes
2
answers
816
views
showing the subgroup membership problem is undecidable for $F_2 \times F_2$
Let $F_2$ denote the free group of rank 2. Does anybody have a fast proof that the subgroup membership problem is undecidable for $F_2 \times F_2$? I saw a really fast proof last semester that ...
- 549
6
votes
2
answers
930
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:
...
- 1,316
6
votes
1
answer
475
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: $...
- 299
6
votes
1
answer
305
views
Given some recursive function, can we effectively associate it a polynomial as in the DPRM theorem?
I'm interested in the following assertion about the Davis-Putnam-Robinson-Matijasevich theorem
Given a recursive function $f:\mathbb{N}\rightarrow\mathbb{N}$, i.e. its index, we can effectively get ...
- 75
6
votes
1
answer
555
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 ...
user44143
6
votes
1
answer
271
views
Decidability of completeness in propositional logic
Propositional logic can be presented as in Mendelson’s book, with the sole inference rule of modus ponens, and with the following three axioms:
$$B \Rightarrow (C \Rightarrow B)$$
$$(B \Rightarrow (C \...
- 1,065
6
votes
1
answer
542
views
How constructive is Matiyasevich's theorem?
A famous corollary of Matiyasevich's theorem is that there exists a Diophantine equation such that it is undecidable (under some recursively axiomatizable theory $T$, such as ZFC) whether that ...
- 1,243
6
votes
1
answer
128
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. ...
- 15.6k
6
votes
1
answer
268
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....
- 628
6
votes
2
answers
207
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),...
- 6,159
5
votes
2
answers
708
views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
- 9,150
5
votes
1
answer
301
views
Parity of number of solutions to Diophantine equations
By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?
- 13.7k
5
votes
1
answer
417
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 $...
- 61
5
votes
2
answers
574
views
(Un)Decidability of the root existence problem for functions with bounded domain
The problem whether a real function $f$ has a root or not is undecidable, given that $f$ is from a class of functions including polynomials and the sine function (http://dl.acm.org/citation.cfm?id=...
- 962
5
votes
1
answer
145
views
Given a quasi-convex subgroup $H$ of hyperbolic $G$, can we decide if two elements $x,y \in G$ lie in the same double coset of $H$?
I've come across the following question in my research, which seems elusive but is almost surely decidable.
Let $H$ be a quasi-convex subgroup of the hyperbolic group $G$. Given $x, y \in G$, we wish ...
- 537
5
votes
1
answer
386
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 ...
- 171
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
283
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
2
answers
273
views
Quantifier elimination in $S^1$
Does quantifier elimination (by cylindrical decomposition) work for systems of polynomial equations and inequalities where some or all of the variables are complex numbers of unit modulus, rather than ...
- 19.4k
4
votes
1
answer
491
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 ...
4
votes
2
answers
274
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 $\...
- 45.5k
4
votes
1
answer
1k
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 ...
- 13.7k
4
votes
2
answers
554
views
Tarski's original proof of quantifier elimination in algebraically closed fields
I am currently helping teach a course about foundations of mathematics, which has thus far focused mostly on propositional and first-order logic. As part of the course, the students are each required ...
- 731
4
votes
1
answer
113
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$ ...
- 2,489
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
1
answer
398
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 ...
- 149k
3
votes
2
answers
317
views
Decide the limit of a decreasing sequence of real number
Given a bounded decreasing sequence of rational number $a_0,a_1,\cdots$, then we know that it has limit $a$. Suppose this sequence satisfy that $|a_k-a|<1/2^k$ for any $k$.
The sequence is given ...
- 1,493