Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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) =...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 383
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 ...
user avatar
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 ...
user avatar
  • 101
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,...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 21
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 ...
user avatar
  • 16.7k
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_{...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,201
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 65
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 ...
user avatar
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 ...
user avatar
  • 12.8k
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 ...
user avatar
  • 31
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 ...
user avatar
  • 16.4k
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), ...
user avatar
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 ...
user avatar
  • 16.4k
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 $\...
user avatar
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 ...
user avatar
  • 12.8k
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$ ...
user avatar
  • 2,287
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 ...
user avatar
  • 4,150
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 ...
user avatar
  • 1,698
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}])...
user avatar
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 $ ...
user avatar
  • 2,265
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 953
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 $...
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 ...
user avatar
  • 12.8k
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 ...
user avatar
  • 51
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 ...
user avatar
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 \...
user avatar
  • 1,265
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 ...
user avatar
  • 101
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 ...
user avatar
  • 1,265
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 ...
user avatar
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 ...
user avatar
  • 1,585
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,...
user avatar
  • 4,150
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 ...
user avatar
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{...
user avatar
  • 333