Questions tagged [decidability]

The tag has no usage guidance.

76 questions
Filter by
Sorted by
Tagged with
11k views

A simple decision problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
• 12k
3k views

Turing Machine restrictions that render halting decidable

If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$), then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
• 3,753
2k views

Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
• 3,753
859 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
• 2,942
1k views

Decidability of diophantine equations over {=, +, gcd}

It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
1k views

Checking if all products of a set of matrices eventually equal zero

I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix. This means exactly what ...
• 775
1k views

Is equivalence of unambiguous context-free languages decidable?

It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
• 464
791 views

Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).: If A ...
• 2,601
889 views

Deciding whether a unary context-sensitive language is regular

It is a well-known result that the question Does a context-free grammar generate a regular language? is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case,...
• 4,841
702 views

151 views

• 113
371 views

Deciding if a language induced by a Presburger formula is context-free

Is the following problem decidable? Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
• 1,291
202 views

Decidability of inductive invariant existence in Presburger arithmetic

Problem: Consider a finite number of control states (including an "initial" and a "bad" state), a finite number of integer variables, and for each ordered pair of states a transition relation ...
• 1,122
417 views

Decidability of existential first-order theory of reals with exponential

The first-order theory over the reals as an ordered field with polynomials is decidable with doubly exponential complexity. However, if we additionally allow the exponential function, that is $e^x$ ...
• 191
1k views

Do natural generalizations of P versus NP exist?

Accepted Answer Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!) One-sentence summary of answer  Plausibly natural generalizations of the P versus NP question ...
299 views

Is there a well-defined notion of an “R/poly” complexity class?

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
• 353
432 views

Uniform mortality problem for Turing Machines

Consider the following generalisation of the mortality problem for Turing Machines. Given a Turing Machine $M$. Is there a bound $k_M$ such that starting from any configuration $c$ machine $M$ ...
• 1,337
103 views

Algorithmically determining proof complexity for Frege systems?

I apologize if this falls wildly short of research level - I am just learning the very basics of proof complexity and lack any real logic background. Let $F$ be a Frege proof system (a finite complete ...
• 171
261 views

Solving problems by deciding a logic

I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable. I have two distinct cases in mind: The problem is ...
• 8,903
800 views

What is known about $CFL \cap coCFL$?

CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL. Are there any nice characterizations or other basic facts about CFL $\cap$ ...
256 views

Decidability of rank-k polymorphism vs. System F

There's a paper by Kfoury from 1992, "Type Reconstruction in Finite Rank Fragments of the Second-Order $\lambda$-Calculus", that proves that type inference for Curry-style rank-$k$ polymorphic lambda ...
• 325
328 views

Proof of decidability of type checking of calculus of (co)inductive constructions?

I often see it asserted that type checking is decidable for CIC, but I haven't seen it proven. Is there a good paper (or simple demonstration) of this?
• 213
2k views

Show that minimal CFG is undecidable via mapping reduction

Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE. The ...
• 395
280 views

FSM transducer sequential composition decidability

this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$....
• 11k
232 views

Post correspondence problem for finite monoids

The Post correspondence problem has the following version for finite monoids: Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$ Question: is ...
177 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
• 2,942
538 views

Proof that the theory of rationals is convex

In Example 10.12 of the book The calculus of computation by Bradley and Manna, it is said The theory of rationals is convex, as it is convex in a geometric sense. How does the geometric sense of ...
• 153
236 views

Is algebraic dependency decidable?

A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a ...
• 5,656
261 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
• 109
96 views

Which computational models support bigotous programs?

A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem. In fact, its pretty ...
1k views

Enumerating decidable languages

[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.] Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
• 153
279 views

Dependence of decidability on the encoding of Turing machines

Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of ...
624 views

About the decidability of sets enumerated in non decreasing order

It is well known that a set of numbers enumerable in nondecreasing order is decidable. However, the typical proof, by cases on the finiteness of the enumerated set, is not constructive. In general, it ...
164 views

Deciding whether a 2nfa halts on every input on every branch

A 2nfa is a nondeterministic finite automaton that can move its head left or right on the input tape, or not. Is the following language known to be decidable?  \textit{H}_{\mathsf{2nfa}} = \{ \...
• 143
261 views

Halting problem proofs that do not utilise self-reference or diagonalization

Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever? All the duplicate questions I have come across end up ...
4k views

Deciding whether a context-free language is regular [closed]

Does anyone know whether the following decision problem is decidable: Given a context-free language $L$, is $L$ regular? Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone ...
448 views

Can the halting problem be solved probabilistically? [closed]

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
• 134
242 views

Decidability of first-order theory of real closed fields with functions

By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over ...
• 11.2k
How to solve an unification problem on $\mathbb{N}$?
Usually, the unification problem for two given terms $t$ and $s$ is to find a substitution $\theta$ such that $\theta t = \theta s$, which is equal to finding the certain \$\langle x_1 , \cdots , x_n \...