# Questions tagged [decidability]

The decidability tag has no usage guidance.

131
questions

0
votes

0
answers

50
views

### Decidability of a polynomial-exponential equation in two variables

My question is with regards to the following (algorithmic) problem:
Problem. Given $f\in \mathbb{Z}[x,y], a,b\in \mathbb{Q}, r\in \mathbb{Z}$, do there exist positive integers $m,n$ such that $f(m,n) =...

3
votes

2
answers

253
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 ...

6
votes

1
answer

186
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 \...

5
votes

1
answer

106
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 ...

0
votes

0
answers

23
views

### Examples of Post Correspondence Problem (PCP) used to prove undecidability in graph theory

I am looking for interesting papers that use a reduction to PCP in order to prove undecidability of certain problems relating to graph theory. Specifically I'm interested in ways in which PCP is ...

1
vote

0
answers

57
views

### Game with Turing machines

Introduction
The following game is quite nice: Alice has, in secret, constructed a polynomial $P \in \mathbb{Z}[x]$.
On day $n=1,2,3,...$, she secretly writes down $P(n)$ on a piece of paper.
Each day,...

13
votes

2
answers

554
views

### Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?

There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a ...

2
votes

0
answers

106
views

### Why is the proof of decidability of arithmetic (Theorem 2.1) in Hamkins & Lewis (2000) enough?

Recently, I was reading the paper "Infinite Time Turing Machines" by Hamkins & Lewis. And one of the first theorems (Theorem 2.1) is about decidability of arithmetic.
The proof is quite ...

4
votes

2
answers

256
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 ...

1
vote

0
answers

67
views

### Non-degenerate solutions in multiplicative subgroups of $\mathbb{Q}$ of finite ranks

I am trying to study whether of a set of first order sentences is decidable, and the key is to figure out an algorithm to compute all non-degenerated solutions. The setting is as follow. Let $q = (q_{...

8
votes

0
answers

210
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 ...

4
votes

0
answers

140
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 ...

13
votes

3
answers

716
views

### Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...

5
votes

0
answers

172
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 ...

3
votes

1
answer

132
views

### Decidability theory involving real parameters

In order to formally ask if a problem is decidable, one first needs to show how to encode each instance of said problem as a finite string of bits (or symbols over some other finite alphabet). For ...

4
votes

0
answers

112
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 ...

20
votes

1
answer

996
views

### Is "almost-solvability" of Diophantine equations decidable?

Say that a Diophantine equation is almost-satisfiable iff for each $n\in\mathbb{N}$ it has a solution mod $n$. Trivially genuine satisfiability over $\mathbb{N}$ implies almost-satisfiability, but the ...

6
votes

1
answer

246
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 ...

12
votes

1
answer

323
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

266
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 ...

3
votes

0
answers

106
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 ...

12
votes

1
answer

555
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 ...

7
votes

0
answers

82
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

527
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 ...

4
votes

2
answers

264
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 $\...

0
votes

0
answers

112
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 ...

4
votes

1
answer

91
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$ ...

11
votes

2
answers

474
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

113
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

165
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

99
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 $ ...

9
votes

2
answers

336
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

112
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 ...

2
votes

1
answer

349
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

212
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

701
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

258
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

542
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

139
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

308
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

70
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

82
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

132
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

141
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 ...

53
votes

8
answers

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"...

3
votes

0
answers

187
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 ...

9
votes

1
answer

482
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

1
answer

156
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

145
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{...