Questions tagged [decidability]
The decidability tag has no usage guidance.
162 questions
16
votes
2
answers
713
views
Is (Z,+,0,1,P2,P3) decidable?
Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable?
I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
- 16.6k
1
vote
0
answers
151
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 ...
- 12.9k
2
votes
0
answers
78
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
5
votes
1
answer
243
views
Undecidability of the existential theory
Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, ...
- 47.1k
10
votes
2
answers
1k
views
Decidability of periodic tilings of the plane
I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (...
- 236k
37
votes
4
answers
2k
views
Is the field of constructible numbers known to be decidable?
By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
- 4,713
6
votes
1
answer
286
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 ...
- 326
1
vote
0
answers
119
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 ...
- 11.3k
10
votes
0
answers
274
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 ...
- 6,353
14
votes
2
answers
851
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, ...
CommunityBot
- 1
64
votes
8
answers
6k
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"...
- 39.9k
10
votes
1
answer
413
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 ...
- 47.1k
1
vote
1
answer
127
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 ...
- 21.1k
5
votes
1
answer
197
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 ...
- 30.5k
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 ...
- 236k
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)$ ...
- 361
3
votes
1
answer
807
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 ...
- 43
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
15
votes
2
answers
1k
views
Decidability of decidability
The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "...
- 236k
6
votes
2
answers
1k
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. ...
- 2,009
3
votes
0
answers
59
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 ...
- 633
18
votes
1
answer
751
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 ...
- 12.9k
-3
votes
1
answer
531
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 ...
- 63
7
votes
1
answer
248
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.
- 63.9k
2
votes
1
answer
176
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'...
- 21.1k
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 ...
13
votes
4
answers
2k
views
Undecidable puzzles
There are plenty of popular NP-hard puzzles,
for example, generalized Sudoku ($n^2 \times n^2$-board), Flow (I cannot give a source for this), Minesweeper, etc.
Recently, I read a bit about aperiodic ...
- 15.8k
5
votes
1
answer
310
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?
- 47.1k
1
vote
2
answers
103
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 ...
- 6,652
9
votes
2
answers
954
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 ...
CommunityBot
- 1
2
votes
1
answer
145
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$...
- 63.9k
2
votes
0
answers
73
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}...
- 63.9k
6
votes
1
answer
640
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 ...
- 4,667
3
votes
0
answers
99
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
2
votes
1
answer
154
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 ...
- 7,525
5
votes
1
answer
442
views
Rabin's proofs of emptiness and complementation problems for automata on infinite trees
I have originally asked this question on Math.SE, but I think it is more suitable here.
I have been reading M. Rabin's 1969 article Decidability of Second-Order Theories and Automata on Infinite ...
7
votes
1
answer
261
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 ...
CommunityBot
- 1
11
votes
1
answer
710
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,356
1
vote
1
answer
213
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 ...
- 6,652
8
votes
2
answers
262
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}\...
- 17k
17
votes
3
answers
2k
views
Decidability of tiling R^2
Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane?
I know the ...
- 39.9k
9
votes
1
answer
372
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,821
7
votes
3
answers
915
views
Decidability of matrix algebra
Take multi-sorted first-order logic with equality, complex scalars, 1xn vectors, nx1 vectors, nxn matrices, addition and multiplication for each pair of sorts they make sense for, and hermitian ...
- 4,713
2
votes
0
answers
65
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,428
1
vote
0
answers
74
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) =...
- 34.3k
4
votes
2
answers
768
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 ...
- 31
6
votes
1
answer
291
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 \...
- 181
29
votes
3
answers
3k
views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
- 4,713
5
votes
1
answer
170
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 ...
- 38.6k
1
vote
0
answers
113
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.8k