Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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$ ...
grok's user avatar
  • 2,489
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 ...
Christopher King's user avatar
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 ...
VS.'s user avatar
  • 1,816
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}])...
user8253417's user avatar
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 $ ...
Thomas's user avatar
  • 2,691
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 ...
jpmacmanus's user avatar
-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 ...
Per Alexandersson's user avatar
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 ...
Joseph O'Rourke's user avatar
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 $\...
Florian Felix's user avatar
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 ...
Lucio Tanzini's user avatar
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 ...
Safwane's user avatar
  • 963
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 $...
sarahzrf's user avatar
  • 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 ...
Turbo's user avatar
  • 13.7k
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 ...
Evan's user avatar
  • 51
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 ...
Manuel Bärenz's user avatar
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 \...
gondolf's user avatar
  • 1,487
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 ...
afiori's user avatar
  • 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 ...
gondolf's user avatar
  • 1,487
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 ...
Sebastian Mueller's user avatar
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 ...
Mark S's user avatar
  • 2,143
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,...
Christopher King's user avatar
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 ...
Dmytro Taranovsky's user avatar
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{...
suitangi's user avatar
  • 333
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 ...
pavpanchekha's user avatar
  • 1,461
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 ...
Arnold Neumaier's user avatar
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 ...
Max CYLin's user avatar
  • 151
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 ...
Talia Ringer's user avatar
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-...
Joseph Van Name's user avatar
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 ...
Ofra's user avatar
  • 1,603
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) ...
Martin Bidlingmaier's user avatar
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. ...
Per Alexandersson's user avatar
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 $...
Liam_math's user avatar
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: ...
N. Virgo's user avatar
  • 1,316
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 ...
konewka's user avatar
  • 171
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 \...
suitangi's user avatar
  • 333
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?
Al Tal's user avatar
  • 1,271
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 .$$ ...
user avatar
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 ...
Peter Franek's user avatar
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 ...
Alberto's user avatar
  • 121
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 ...
Turbo's user avatar
  • 13.7k
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}$....
gondolf's user avatar
  • 1,487
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 ...
user93785's user avatar
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).
Thinniyam Srinivasan Ramanatha's user avatar
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....
Szymon Toruńczyk's user avatar
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 ...
Adam P. Goucher's user avatar
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 (...
Mary Star's user avatar
  • 299
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}\...
Alex's user avatar
  • 21
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: $...
Mary Star's user avatar
  • 299
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 ...
Arnold Neumaier's user avatar