Questions tagged [decidability]
The decidability tag has no usage guidance.
155
questions
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$ ...
12
votes
2
answers
537
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
134
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
246
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
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 $ ...
10
votes
2
answers
376
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
126
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 ...
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 ...
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 $\...
13
votes
1
answer
776
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
268
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 ...
7
votes
3
answers
660
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
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 ...
8
votes
1
answer
338
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
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 \...
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
...
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
vote
1
answer
180
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 ...
57
votes
8
answers
6k
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"...
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 ...
8
votes
1
answer
538
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,...
2
votes
1
answer
212
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
153
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
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 ...
4
votes
0
answers
346
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
212
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
282
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
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-...
12
votes
3
answers
2k
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
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) ...
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. ...
5
votes
1
answer
415
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
924
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
1
answer
383
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
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 \...
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?
11
votes
1
answer
488
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
412
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
164
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 ...
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 ...
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}$....
3
votes
1
answer
153
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
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).
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....
15
votes
1
answer
568
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
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 (...
2
votes
1
answer
513
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
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: $...
21
votes
3
answers
2k
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 ...