Questions tagged [decidability]
The decidability tag has no usage guidance.
155
questions
14
votes
3
answers
2k
views
Guaranteed correct digits of elementary expressions
Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...
8
votes
1
answer
998
views
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
5
votes
2
answers
651
views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
53
votes
7
answers
6k
views
Are there any undecidability results that are not known to have a diagonal argument proof?
Is there a problem which is known to be undecidable (in the algorithmic sense), but for which the only known proofs of undecidability do not use some form of the Cantor diagonal argument in any ...
3
votes
0
answers
48
views
Maximal number of aperiodic Wang tiles
I was wondering whether there is an analogue result to the minimality of Wang tiling, in the direction of maximality.
I think that the paper by Jeandel and Rao, shows that the minimal number of Wang ...
3
votes
1
answer
774
views
Language equivalence between deterministic and non-deterministic counter net
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
18
votes
1
answer
724
views
Is solvability semi-decidable?
Let $G = \langle A \mid R \rangle$ be a finitely presented group, given by a finite presentation. If $G$ is abelian, then we can verify this fact: simply verify the fact that $[a, b] = 1$ for all ...
-3
votes
1
answer
518
views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
7
votes
1
answer
239
views
Decidability of completing Penrose tilings
Is the following problem known to be un/decidable? Problem: Given a finite configuration of Penrose tiles in the plane, determine if there is an extension of the configuration tiling the whole plane.
2
votes
1
answer
161
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'...
12
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 ...
5
votes
1
answer
300
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?
1
vote
2
answers
90
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 ...
9
votes
2
answers
916
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 ...
2
votes
1
answer
140
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$...
2
votes
0
answers
70
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}...
2
votes
1
answer
119
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 ...
3
votes
0
answers
96
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 ...
7
votes
1
answer
225
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 ...
11
votes
1
answer
663
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 ...
1
vote
1
answer
180
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 ...
7
votes
2
answers
236
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}\...
8
votes
1
answer
344
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 ...
6
votes
1
answer
535
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 ...
2
votes
0
answers
63
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 ...
1
vote
0
answers
66
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) =...
4
votes
2
answers
541
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
271
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
145
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 ...
1
vote
0
answers
97
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
1k
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 ...
3
votes
0
answers
146
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
273
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
72
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
232
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
156
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
806
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
202
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
166
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 ...
7
votes
0
answers
259
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 ...
6
votes
1
answer
298
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
378
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
271
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
114
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
819
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 ...
8
votes
0
answers
110
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
555
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
274
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
117
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 ...