Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 2,397 papers for “Undecidable problem”

TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE

Ralph McKenzie · International Journal of Algebra and Computation · 1996

We exhibit a construction which produces for every Turing machine [Formula: see text], an algebra [Formula: see text] (finite and of finite type) such that the Turing machine halts iff the algebra has a finite basis for its equations.

Cited by 89

The Hurwitz Equivalence Problem is Undecidable

Eran Liberman, Mina Teicher · ArXiv.org · 2005

In this paper, we prove that the Hurwitz equivalence problem for 1-factorizations in $F_2 \oplus F_2$ is undecidable, and as a consequence, the Hurwitz equivalence problem for $Δ^2$-factorizations in the braid groups $B_n, n\geq 5$ is also undecidable.

Cited by 5Open access

Undecidable Boundedness Problem For Datalog Program

Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson et al. · 1992

A given Datalog program is bounded if its depth of recursion is independent of the input database. Deciding boundedness is a basic task for the analysis of database logic programs. The undecidability of Datalog boundedness was first demonstrated by Gaifman et al. We introduce new techniques for proving the undecidability of various kinds of boundedness, which allow us to considerably strengthen the results of Gaifman et al. In particular: (1) We use a new generic reduction technique to show that program boundedness is undecidable for arity 2 predicates, even with linear rules. (2) We use the mortality problem of Turing machines to show that uniform boundedness is undecidable for arity 3 predicates and for arity 1 predicates when $\ne$ is also allowed. (3) We use a single rule polymorphically to show that program (resp., predicate) boundedness is undecidable for two linear rules (resp., one rule and a projection), one initialization rule and small arity predicates.

Cited by 0

Salce's problem on cotorsion pairs is undecidable

Sean Cox · arXiv (Cornell University) · 2021

Salce \cite{MR565595} introduced the notion of a \emph{cotorsion pair} of classes of abelian groups, and asked whether every such pair is \emph{complete} (i.e., has enough injectives and projectives). We prove that it is consistent, relative to the consistency of Vopěnka's Principle (VP), that the answer is affirmative. Combined with a previous result of Eklof-Shelah \cite{MR2031314}, this shows that Salce's Problem is independent of the ZFC axioms (modulo the consistency of VP).

Cited by 0Open access

Undecidable word problem in subshift automorphism groups

P. Guillon, Emmanuel Jeandel, Jarkko Kari et al. · arXiv (Cornell University) · 2018

This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly this degree.

Cited by 0Open access

Salce's problem on cotorsion pairs is undecidable

Sean Cox · Bulletin of the London Mathematical Society · 2022

In the 1970's, Salce introduced the notion of a cotorsion pair of classes of abelian groups, and asked whether every such pair is complete (that is, has enough injectives and projectives); we refer to this as Salce's Problem (for Ab). We prove that it is consistent, relative to the consistency of Vopěnka's Principle (VP), that the answer is affirmative. Combined with a previous result of Eklof and Shelah , this shows that Salce's Problem for Ab, and in fact for R-Mod when R $R$ is hereditary, is independent of the ZFC axioms (modulo the consistency of VP).

Cited by 6

A simple undecidable problem for free groups

Tero Harju · Theoretical Computer Science · 2024

Let F n denote the free group on n generators. It is shown to be undecidable for two morphisms g , h : F n → F 2 and a generator element a of F 2 , whether or not there exists an element w ∈ F n such that g ( w ) = a and h ( w ) = 1 , where 1 is the identity element.

Cited by 1Open access

The quantum smooth label cover problem is undecidable

Eric Culf, Kieran Mastel, Connor Paddock et al. · ArXiv.org · 2025

We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.

Cited by 0Open access

The Finite Satisfiability Problem for PCTL is Undecidable

Miroslav Chodil, Antonı́n Kučera · 2024

We show that the problem of whether a given PCTL formula has a finite model is undecidable. The undecidability result holds even for formulae of the form [EQUATION] where the validity of ϕ1, ϕ2 depends only on the states reachable in at most two transitions. Consequently, the problem of whether a given PCTL formula is valid in all finite-state Markov chains is not even semi-decidable.

Cited by 4Open access

The Finite Satisfiability Problem for PCTL is Undecidable

Miroslav Chodil, Antonı́n Kučera · Journal of the ACM · 2026

We show that the problem of whether a given PCTL formula has a finite model is undecidable. The undecidability result holds even for formulae of the form \(\varphi _1 \wedge {\pmb {\mathtt {G}}}_{=1} \varphi _2\) where the validity of \(\varphi _1,\varphi _2\) depends only on the states reachable in at most two transitions. Consequently, the problem of whether a given PCTL formula is valid in all finite-state Markov chains is not even semi-decidable.

Cited by 0Open access

Halting Problem of One Binary Horn Clause is Undecidable.

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier · 1993

. This paper proposes a codification of the halting problem of any Turing machine in the form of only one right--linear binary Horn clause as follows : p(t) / p(tt) : where t (resp. tt) is any (resp. linear) term. Recursivity is well--known to be a crucial and fundamental concept in programming theory. This result proves that in Horn clause languages there is no hope to control it without additional hypotheses even for the simplest recursive schemes. Some direct consequences are presented here. For instance, there exists an explicitly constructible right--linear binary Horn clause for which no decision algorithm, given a goal, always decides in a finite number of steps whether or not the resolution using this clause is finite. The halting problem of derivations w.r.t. one binary Horn clause had been shown decidable if the goal is ground [SS88] or if the goal is linear [Dev88, Dev90, DLD90]. The undecidability in the non--linear case is an unexpected extension. The proof of the main r...

Cited by 0