Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
0answers
119 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
0answers
68 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 $ ...
7
votes
2answers
252 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
1answer
104 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 ...
1
vote
1answer
291 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 ...
6
votes
1answer
132 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 $\...
10
votes
1answer
486 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
0answers
239 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 ...
6
votes
3answers
375 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
3answers
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
0answers
122 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
1answer
241 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
0answers
56 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
0answers
61 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
0answers
131 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
1answer
82 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 ...
52
votes
8answers
5k 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"...
2
votes
0answers
115 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 Pooten [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
1answer
385 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,...
1
vote
1answer
105 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
0answers
125 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
0answers
49 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 ...
2
votes
0answers
207 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
0answers
158 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
1answer
183 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
0answers
87 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-...
11
votes
3answers
1k 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
0answers
99 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
1answer
92 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
1answer
324 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
2answers
552 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
0answers
155 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
0answers
78 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 \...
35
votes
3answers
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?
10
votes
1answer
413 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
1answer
346 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
1answer
112 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 ...
3
votes
1answer
579 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
0answers
84 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
1answer
137 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
0answers
262 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
1answer
238 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....
13
votes
1answer
446 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
0answers
179 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
1answer
367 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
1answer
422 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: $...
20
votes
3answers
1k 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 ...
8
votes
1answer
458 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 ...
7
votes
0answers
445 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 ...
2
votes
1answer
273 views

Recurrence relations with polynomial coefficients: an undecidable problem

I read once (somewhere) that solving a recurrence relation with polynomial coefficients, in the general case, is an undecidable problem. I can't remember the exact reference and I've been trying to ...