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 ...
- 22.6k
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] ...
- 526
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.
(...
- 3,743
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 $|$, $+$...
- 16.9k
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 ...
- 3,033
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, ...
- 22.6k
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 ...
- 28.3k
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 ...
- 3,033
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 ...
- 5,127
10
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 ...
- 118
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 ...
- 6,967
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 ...
- 406
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 ...
- 11.7k
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 (...
- 8,616
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 ...
- 1,320
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 ...
- 36.9k
8
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 ...
- 16.9k
8
votes
Can you see that the Linz Halting Problem proof contains a fatal flaw?
This will come as no surprise to most people here, but Linz' proof does not appear to have a fatal flaw. I have prepared a machine checked formalization of the argument here. I didn't implement all ...
- 921
8
votes
Accepted
Is there a well-defined notion of an “R/poly” complexity class?
There is nothing stopping you from defining the class, though I don’t recall seeing it studied.
Actually, I can see two reasonable definitions for this class. The first one, which follows more ...
- 16.9k
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$, ...
- 13.7k
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!)
...
- 351
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:
...
- 22.6k
6
votes
Petri net termination
Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $...
- 2,552
5
votes
Accepted
Proof of decidability of type checking of calculus of (co)inductive constructions?
I found another reference that goes through a detailed proof of the decidability of typechecking for systems of dependent types up to the CIC:
Chapter 2 of Advanced Topics in Types and Programming ...
- 13.7k
5
votes
Enumerating decidable languages
While @LanceFortnow answered the question asked, since the OP mentioned deciders, I'll mention what kind of oracle is needed for that. Jockusch showed that the computable sets are $A$-uniform iff $A$ ...
- 4,475
5
votes
Accepted
Decidability of rank-k polymorphism vs. System F
The conclusion of [Kfoury & Tiuryn 1992] says (emphasis mine):
We prove that [...] for every $k\ge 3$ there is a typing of constants
that assigns types in $S(1)$ such that the type ...
- 4,796
5
votes
Dependence of decidability on the encoding of Turing machines
For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}...
- 16.9k
4
votes
Accepted
Show that minimal CFG is undecidable via mapping reduction
Here is a solution based on a reduction from Post Correspondence Problem. The general idea is similar to the ones used in reductions from PCP to the emptiness of intersection and ambiguity in context-...
- 3,354
4
votes
Accepted
Turing meta-oracle
Such an $H$ would let us solve the halting problem:
We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$).
If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)...
- 648
4
votes
About the decidability of sets enumerated in non decreasing order
Suppose there were a computable $f$ as described in the question. Then we could solve the Halting problem as follows.
Given a Turing machine $T$, consider the computable function $g$, defined by
$$g(...
- 28.3k
Only top scored, non community-wiki answers of a minimum length are eligible