Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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)$ ...
rosan98's user avatar
  • 199
8 votes
1 answer
994 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)$ ...
Martin Clever's user avatar
5 votes
2 answers
622 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. ...
truebaran's user avatar
  • 9,140
52 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 ...
Terry Tao's user avatar
  • 108k
3 votes
0 answers
47 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 ...
Keen-ameteur's user avatar
3 votes
1 answer
773 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 ...
Lionheart's user avatar
18 votes
1 answer
723 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 ...
Carl-Fredrik Nyberg Brodda's user avatar
-3 votes
1 answer
517 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 ...
Lionheart's user avatar
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.
interstice's user avatar
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'...
hatch22's user avatar
  • 123
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 ...
Milo Moses's user avatar
  • 2,799
5 votes
1 answer
299 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?
Turbo's user avatar
  • 13.6k
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 ...
Keen-ameteur's user avatar
9 votes
2 answers
915 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 ...
Sidharth Ghoshal's user avatar
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$...
Dominic van der Zypen's user avatar
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}...
Dominic van der Zypen's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 ...
Yoneda Lemma's user avatar
7 votes
1 answer
224 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 ...
TomKern's user avatar
  • 429
11 votes
1 answer
662 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 ...
M. Winter's user avatar
  • 12.5k
1 vote
1 answer
178 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 ...
Keen-ameteur's user avatar
7 votes
2 answers
234 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}\...
Igor Pak's user avatar
  • 16.3k
8 votes
1 answer
341 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 ...
Dmytro Taranovsky's user avatar
6 votes
1 answer
534 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 ...
tparker's user avatar
  • 1,243
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 ...
Loïc Teyssier's user avatar
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) =...
thebogatron's user avatar
4 votes
2 answers
535 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 ...
Martin Skilleter's user avatar
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 \...
Sprotte's user avatar
  • 1,045
5 votes
1 answer
143 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 ...
jpmacmanus's user avatar
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,...
Per Alexandersson's user avatar
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 ...
SARTHAK GUPTA's user avatar
3 votes
0 answers
145 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 ...
Jeremy's user avatar
  • 31
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 ...
H A Helfgott's user avatar
  • 19.3k
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_{...
user978394's user avatar
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 ...
Bogdan Grechuk's user avatar
4 votes
0 answers
154 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 ...
user101010's user avatar
  • 5,319
13 votes
3 answers
804 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 ...
Bogdan Grechuk's user avatar
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 ...
Jakub Konieczny's user avatar
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
Noah Schweber's user avatar
6 votes
1 answer
296 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 ...
Niconar's user avatar
  • 75
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
Turbo's user avatar
  • 13.6k
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 ...
Fanta's user avatar
  • 31
12 votes
1 answer
810 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
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), ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
user avatar
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 $\...
Dominic van der Zypen's user avatar
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 ...
Turbo's user avatar
  • 13.6k