Questions tagged [decidability]
The decidability tag has no summary.
173 questions
0 votes
0 answers
29 views
On quadratic equations over the Gaussian ring $\mathbb Z[i]$
In 1972 C. L. Siegel proved that there is an algorithm to decide for any polynomial $P(x_1,\ldots,x_n)\in\mathbb Z[x_1,\ldots,x_n]$ with $\deg P=2$ whether $$P(x_1,\ldots,x_n)=0$$ for some $x_1,\ldots,...
- 17.5k
1 vote
0 answers
143 views
Understanding link between decidability and complexity
I've seen several instances where an undecidability/uncomputability result can be used to produce a lower bound complexity result, and I am interested in when the process can go the other way. In ...
- 21
1 vote
0 answers
111 views
Weighted sums of four primes
Sums of primes have been studied by number theorists for many years. Goldbach's conjecture is the most famous unsolved problem in this direction. Here I'd like to consider weighted sums of primes. For ...
- 17.5k
10 votes
2 answers
815 views
Is it possible to add a new axiom schema to classical propositional logic?
Let IPL mean the intuitionist propositional calculus. One can add a great diversity of axiom schemas to obtain intermediate logics between IPL and CPL, where CPL is the classical propositional ...
- 391
3 votes
0 answers
89 views
Sequence of polynomals from linear recursion: Decidable or not if all are real-rooted?
Let $P_1(x),P_2(x),P_3(x),\dotsc$ be a sequence of polynomials, determined by some initial conditions and a finite-length linear recursion with coefficients being polynomials in $x$ and the index. For ...
- 16.1k
23 votes
1 answer
661 views
Is the equational theory of $(\mathbb{N},+,\times,\mathrm{factorial}(\cdot),0,1)$ decidable?
Given two terms over the signature $(+,\times,\mathrm{factorial}(\cdot),0,1)$ with arbitrarily many variables, is there an algorithm to decide whether the two terms define the same function on $\...
- 1,047
3 votes
0 answers
93 views
Is it ever decidable if a finite set of identities implies a non-reflexive identity?
I asked this question on math stack exchange, but it didn't get any responses. So, I am asking it here. Suppose we are working in the signature of a single binary operation $*$. We are given a finite ...
- 2,183
6 votes
1 answer
284 views
Deciding positivity for polynomials summed across a regular language
Motivation: Long story short, this problem arose after a number of reductions and simplifications from a question in symbolic dynamics motivated by the paper Symbolic discrepancy and self-similar ...
- 1,383
0 votes
1 answer
272 views
Connecting Size of Solutions of Diophantine equations to Undecidability proofs
It is known there is no single algorithm to decide if a general Diophantine equation has $\mathbb Z$ solutions. It is also true that if we have size bound on the solutions, we can exhaustively search ...
- 1
6 votes
1 answer
817 views
Is decomposability of polynomials over a field an undecidable problem?
By a decomposition of a polynomial $F(x)$ over a field $K$ we mean writing $F(x)$ as $$ F(x)=G(H(x)) \quad(G(x), H(x) \in K[x]), $$ which is nontrivial if $\operatorname{deg} G(x)>1$ and $\...
- 312
1 vote
0 answers
185 views
Decide if a group is abelian
Let $G = \langle X: R\rangle$ be a finitely presented group. The following problem seems very natural to me, yet I cannot find any reference for it: Decide if $G$ is abelian or not. With a reduction ...
- 11
2 votes
0 answers
103 views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows. Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
1 vote
0 answers
172 views
What is the minimal length of an undecidable sentence in those ZFC related theories?
If we measure the length of a sentence by the number of occurrences of atomic subformulas in it. So, for example in set theory written in $\sf FOL(\in)$, the length of a sentence is the number of ...
- 13k
14 votes
1 answer
564 views
Open problems in complete theories
It is well-known that every complete recursively enumerable first-order theory is decidable. Does that mean that such theories are "trivial", or are there still interesting open problems ...
user507115
14 votes
2 answers
925 views
Examples of finitely presented subgroups of $\operatorname{GL}(n,\mathbb{Z})$ with unsolvable decision problems
$\DeclareMathOperator\GL{GL}\DeclareMathOperator\Aut{Aut}$Does there exist a finitely presented subgroup of $\GL(n,\mathbb{Z})$ for which it is known that the conjugacy problem is unsolvable (if yes, ...
- 143
10 votes
1 answer
557 views
Is the theory of $(\operatorname{Ord}, <)$ decidable?
Over a sufficiently strong second-order theory (such as Morse-Kelley set theory), it's possible to define the truth of all first-order formulae in the language of sets. This allows us to construct the ...
- 618
1 vote
1 answer
183 views
Can we effectively define a theory of all upward absolute sentences over theories of hereditarily bounded sets?
Lets' take the theory of hereditarily bounded sets[1][2]. We know that every $S_k$ where $k \in \omega$ is decidable and has as its canonical model the set ${\sf H}_k$ of all sets hereditarily of size ...
- 13k
5 votes
1 answer
276 views
Can one compute the automorphism group of a curve of genus >1?
Given a sufficiently nice perfect field $k$ and a smooth projective curve $C$ of genus $g_C>1$ over $k$, can one compute the automorphism group ${\rm Aut}(C)$? It is known that ${\rm Aut}(C)$ is ...
- 2,141
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)$ ...
- 471
8 votes
1 answer
1k 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)$ ...
- 157
10 votes
2 answers
3k 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. ...
- 9,634
53 votes
7 answers
7k 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 ...
- 120k
3 votes
0 answers
88 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 ...
- 703
3 votes
1 answer
920 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 ...
- 73
18 votes
1 answer
797 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
650 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 ...
- 73
7 votes
1 answer
337 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.
- 519
2 votes
1 answer
264 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
13 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 ...
- 3,044
5 votes
1 answer
339 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
1 vote
2 answers
163 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 ...
- 703
9 votes
2 answers
1k 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 ...
- 3,139
2 votes
1 answer
187 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$...
- 53.2k
2 votes
0 answers
95 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}...
- 53.2k
2 votes
1 answer
207 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 ...
- 8,638
3 votes
0 answers
117 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
353 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 ...
- 489
11 votes
1 answer
821 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 ...
- 14.5k
1 vote
1 answer
285 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 ...
- 703
8 votes
2 answers
313 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}\...
- 17.4k
9 votes
1 answer
446 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 ...
- 8,638
6 votes
1 answer
846 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,321
2 votes
0 answers
82 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,553
1 vote
0 answers
106 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) =...
- 161
5 votes
2 answers
1k 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 ...
- 811
6 votes
1 answer
396 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 \...
- 1,115
5 votes
1 answer
266 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 ...
- 950
1 vote
0 answers
165 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,...
- 16.1k
15 votes
2 answers
2k 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 ...
- 312
3 votes
0 answers
196 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