31 votes
Accepted

Turing Machine restrictions that render halting decidable

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example: Juris Hartmanis: Tape-Reversal Bounded Turing Machine ...
user avatar
23 votes
Accepted

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

According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] ...
user avatar
  • 516
22 votes

A simple decision problem whose decidability is not known

It is unknown whether or not it is decidable to determine if a given shape can tile the plane, even for polyomino tiles.                     (...
user avatar
21 votes
Accepted

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

($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$...
user avatar
19 votes

Turing Machine restrictions that render halting decidable

Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded ...
user avatar
16 votes
Accepted

What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...
user avatar
15 votes

What is the simplest computational model for which the emptiness problem is undecidable?

Probably you already got these in your bag :-) Two way one counter machine over unary alphabet (Minsky61). Two way weak counter machines (the counter has no effect on the computation but the machine ...
user avatar
14 votes

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

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, ...
user avatar
14 votes

What notable automaton models have polynomially-decidable containment?

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a ...
user avatar
  • 7,643
13 votes
Accepted

Computability and continuity

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable ...
user avatar
  • 26.4k
12 votes
Accepted

Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second ...
user avatar
11 votes

What notable automaton models have polynomially-decidable containment?

A Non deterministic XOR automaton (NXA) fits your question. A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor ...
user avatar
  • 9,348
11 votes

A simple decision problem whose decidability is not known

A problem from Automata Theory. Input: A DFA $D$ over a binary input alphabet. Question: Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In ...
user avatar
9 votes
Accepted

Are there any open problems concerning decidability?

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number? This is currently not known to be either decidable or undecidable. (By ...
user avatar
9 votes

Deciding whether a context-free language is regular

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages. Regarding DCFL, I have two references (from Hopcroft+Ullman 79): A regularity test for pushdown machines, ...
user avatar
  • 1,502
9 votes

Deciding whether a unary context-sensitive language is regular

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate ...
user avatar
9 votes
Accepted

Is equivalence of unambiguous context-free languages decidable?

This is currently an open problem. As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem. On the other hand, the ...
user avatar
  • 108
9 votes
Accepted

Enumerating decidable languages

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (...
user avatar
9 votes

Post correspondence problem for finite monoids

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether ...
user avatar
  • 10.3k
9 votes

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

A something that might be too long for a comment, based on the previous answer by Emil. In the case you are interested in the complexity of such a logic, consider reading LICS'2015 paper by Joël ...
user avatar
8 votes

A simple decision problem whose decidability is not known

Iterated maps on the interval (description from here): (very related to the problem proposed by Magnus Find) Let $F$ be a piecewise-linear map on the unit interval and $x$ a point in this interval. ...
user avatar
8 votes
Accepted

Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

For Buchberger, it depends what you want it for, but generally speaking the answer is no. First, as pointed out on the Wikipedia article, the complexity upper bound given by Tarski-Seidenberg is ...
user avatar
7 votes

What notable automaton models have polynomially-decidable containment?

Let me first mention that your problem is not symmetric and that if $M_1$ is an NFA and $M_2$ a DFA, then the inclusion problem is polynomial (simply because it amounts to test whether the complement ...
user avatar
7 votes
Accepted

How can you state how abstract interpretation gets around Rice's Theorem succinctly?

To be as clear and concise as possible, I'd try saying this Abstract interpretation may only over-approximate properties of programs: the most precise abstract value of a program $P$ may be $a$, ...
user avatar
  • 13.1k
6 votes
Accepted

Solving problems by deciding a logic

I think the most spectacular example of this approach is Thomas Hales' proof of the Kepler conjecture (aka Hilbert's 18th problem). In the 1950s, Fejes Toth proved that the Kepler conjecture was ...
user avatar
6 votes
Accepted

Consistency and completeness of any arbitrary 3-valued logic?

Any logic defined semantically in a similar way is trivially consistent, as it has a model. Any finite-valued logic has a faithful translation into classical logic, hence its set of valid formulas, ...
user avatar
6 votes

Deciding whether a unary context-sensitive language is regular

This is essentially the same answer as above, but since a "more expedient" answer is sought, I'm mentioning this: (Also, this is my first post here, so forgive me if I'm posting a triviality!) ...
user avatar
6 votes
Accepted

Uniform mortality problem for Turing Machines

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966)) The uniform mortality problem undecidability follows from the following: ...
user avatar
6 votes
Accepted

Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
user avatar
5 votes
Accepted

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

It's undecidable because we can interpret natural numbers (with addition and multiplication). For example, let $Ind(f)$ be the formula: $$f(0)=1 \land \forall x \ \big(f(x)=1 \to f(x+1)=1\big)$$ Now ...
user avatar
  • 21.3k

Only top scored, non community-wiki answers of a minimum length are eligible