Questions tagged [decidability]
The decidability tag has no usage guidance.
146
questions
2
votes
1
answer
146
views
How can Kőnig's Lemma be expressed in Monadic Second-Order Logic of 2 Successors?
I read the following on Wikipedia's page on Monadic Second-Order Logic of Two Successors (MS2S):
Weak S2S (WS2S) requires all sets to be finite (note that finiteness
is expressible in S2S using Kőnig'...
- 123
11
votes
1
answer
2k
views
Are 100% of statements undecidable, in Gödel's numbering? [duplicate]
Gödel's incompleteness theorem shows that there are undecidable statements, i.e., formal logical claims which neither have proofs nor disproofs.
In doing so, Gödel famously enumerated all well-formed ...
- 2,509
5
votes
1
answer
280
views
Parity of number of solutions to Diophantine equations
By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?
- 13.2k
1
vote
2
answers
80
views
A variation of domino tiling problem with fusions
I know several specific variations of the domino tiling problem has been determined to be decidable or undecidable, such as the seed domino problem. I have a variation which I have not been able to ...
- 357
8
votes
2
answers
864
views
What theories are larger than the real closed field but still decidable?
It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
- 1,450
2
votes
1
answer
135
views
Computability of fillability of unit cube in $\mathbb{R}^n$ by $k$ $\varepsilon$-balls
Let $\mathbb{N}$ denote the set of positive integers. We define a relation $R \subseteq \mathbb{N}^4$ in the following way:
$(p,q,n,s)\in R$ if and only if there is $S\subseteq [0,1]^n$ with $|S| = s$...
- 42.5k
2
votes
0
answers
68
views
Is parquetability decidable?
Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}...
- 42.5k
2
votes
1
answer
101
views
Axiomatization of S2S
What is a reasonable axiomatization of S2S?
S2S is the monadic second order theory with two successors (Wikipedia link). It has finite binary strings, operations $s→s0$ and $s→s1$ on strings, and ...
- 5,507
3
votes
0
answers
85
views
Decidability of theory of modules over a ring of finite representation type
I have read from Mike Prest's model theory for modules (London lecture note series) chapter 17 that a Ring of finite representation type has a decidable theory of modules. Here decidability was ...
- 31
7
votes
1
answer
194
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
- 399
9
votes
1
answer
599
views
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...
- 11.4k
1
vote
1
answer
117
views
Possible weaker version of the Domino/Wang tiling problem
This may be a dumb question, but I was wondering whether the question of 'periodically tiling the plane from a finite set of tiles' is the same as the domino tiling problem or a weaker version. I ...
- 357
7
votes
2
answers
210
views
Congruences of binomial sums
Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...
- 16.1k
8
votes
1
answer
303
views
Decidable theories with arbitrary complexity
Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity?
Here, arbitrarily high (computational) complexity means that for every ...
- 5,507
6
votes
1
answer
441
views
How constructive is Matiyasevich's theorem?
A famous corollary of Matiyasevich's theorem is that there exists a Diophantine equation such that it is undecidable (under some recursively axiomatizable theory $T$, such as ZFC) whether that ...
- 1,213
2
votes
0
answers
58
views
Decidability of the solvability of quadratic systems
Let a finite collection of (complex) unknowns $\{x_1,\ldots,x_n\}$ be given, as well as an affine system $AX=B$ in the quadratic variables $X:=[x_i x_j : i\leq j]$, with entries in a computable ...
- 5,200
1
vote
0
answers
62
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) =...
- 141
3
votes
2
answers
369
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 ...
- 692
6
votes
1
answer
239
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 \...
- 933
5
votes
1
answer
126
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 ...
- 507
1
vote
0
answers
66
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,...
- 15.3k
13
votes
2
answers
679
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 ...
- 238
3
votes
0
answers
129
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 ...
- 31
4
votes
2
answers
266
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 ...
- 18.6k
1
vote
0
answers
69
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_{...
- 11
8
votes
0
answers
226
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 ...
- 3,477
4
votes
0
answers
147
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 ...
- 5,299
13
votes
3
answers
754
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
183
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,477
3
votes
1
answer
149
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 ...
- 1,490
7
votes
0
answers
192
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
1k
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 ...
- 19.1k
6
votes
1
answer
270
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
350
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
267
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.2k
3
votes
0
answers
108
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
603
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
101
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
547
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
272
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 $\...
- 42.5k
0
votes
0
answers
114
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.2k
4
votes
1
answer
105
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,327
10
votes
2
answers
511
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 ...
- 4,415
0
votes
1
answer
125
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,776
8
votes
0
answers
207
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}])...
- 449
3
votes
0
answers
106
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,573
10
votes
2
answers
360
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 ...
- 507
-2
votes
1
answer
119
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.3k
3
votes
1
answer
375
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 ...
- 147k
7
votes
1
answer
238
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