Questions tagged [decidability]
The decidability tag has no usage guidance.
163 questions
6
votes
1
answer
334
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
12
votes
1
answer
412
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 ...
7
votes
0
answers
274
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.9k
3
votes
0
answers
116
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
12
votes
1
answer
1k
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 ...
user44143
8
votes
0
answers
125
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
561
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
4
votes
2
answers
278
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 $\...
- 48.8k
0
votes
0
answers
122
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.9k
4
votes
1
answer
122
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,519
12
votes
2
answers
560
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 ...
- 6,353
0
votes
1
answer
139
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 ...
- 1,826
8
votes
0
answers
268
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
3
votes
0
answers
122
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,811
10
votes
2
answers
410
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 ...
- 619
-2
votes
1
answer
133
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 ...
- 15.8k
3
votes
1
answer
414
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 ...
- 151k
7
votes
1
answer
272
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
13
votes
1
answer
811
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 ...
- 377
7
votes
3
answers
696
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
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 ...
- 13.9k
6
votes
1
answer
286
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 ...
- 61
8
votes
1
answer
347
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 ...
- 5,565
1
vote
0
answers
77
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,503
0
votes
0
answers
104
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
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,503
1
vote
1
answer
199
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 ...
64
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
195
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,185
8
votes
1
answer
548
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,...
- 6,353
2
votes
1
answer
223
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 ...
- 7,545
4
votes
0
answers
164
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{...
- 343
1
vote
0
answers
56
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,491
5
votes
0
answers
356
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,873
2
votes
0
answers
218
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
1
vote
1
answer
299
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
...
- 31
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 ...
- 1,613
4
votes
0
answers
117
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
137
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.8k
5
votes
1
answer
432
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
6
votes
2
answers
998
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,344
5
votes
1
answer
442
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
2
votes
0
answers
91
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 \...
- 343
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?
- 1,281
11
votes
1
answer
497
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 .$$
...
user40023
8
votes
1
answer
420
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 ...
- 972
1
vote
1
answer
183
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 ...
- 111
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.9k
1
vote
0
answers
91
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,503