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] ...
  • 516
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, ...
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 ...
  • 108
9 votes
Accepted

Non-comparable natural numbers

When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like $$B(m)>n$$ (for natural numbers $m$, $n$) that are not decided by ZFC, assuming ...
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 (...
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: ...
6 votes

Polynomial-time reductions between undecidable languages

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a ...
  • 2,295
5 votes

Does the Linz Halting Problem proof contain 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 ...
  • 670
5 votes
Accepted

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

Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement. First, it is indeed recognized by a NCM — as is the complement of the language of ...
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 votes
Accepted

Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

The problem is in your assumption that rational relations are closed under intersection. The following counter-example is taken from Example 2.5 in Berstel's "Transductions and Context-Free Languages":...
4 votes

Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them. Your regularity theorem holds with length-preserving functions. If you want ...
  • 7,757
3 votes
Accepted

Oracle-Decidability of Algebraic Independence

The answer is no; interestingly, the problem is harder to state satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that ...
3 votes

Example of R and G when $R \subseteq L(G)$ is undecidable

If you mean "undecidable" in the computational sense, then see the answer of Suhail Sherif. Your question becomes more interesting if we take "undecidable" in the proof-theoretic sense, i.e. there is ...
  • 7,757
3 votes

Example of R and G when $R \subseteq L(G)$ is undecidable

Given an $R$ and a $G$, one can easily construct a TM which outputs whether $R \subseteq L(G)$. (Consider two TMs, one that just rejects and one that just accepts. If not the first, then the second ...
2 votes

research on systematically attacking multiple instances of undecidable problems

The obvious candidates for these kinds of things are number theoretical. The collatz problem springs to mind, see What is the "nearest" problem to the Collatz conjecture that has been ...
  • 13.3k
2 votes
Accepted

research on systematically attacking multiple instances of undecidable problems

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?". These algorithms (which may be ...
  • 4,584
2 votes
Accepted

Recommendations for References on undecidability of First Order Logic

Let me clarify one subtle point: first order logic is only undecidable for certain given languages. In particular the language $\cal{L}$ that contains only monadic predicates, that is, predicates of ...
  • 13.3k
2 votes

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e. Theorem. There is no algorithm that given ...
1 vote

Understanding the construction of an uncomputable function

The question is not research-level but since some of the comments following it may be confusing, allow me to explain precisely how functions are defined by cases. Suppose we would like to define a ...
  • 26.8k
1 vote

Show that membership in L is undecidable

Pick M to be a universal Turing machine plus two states called A and B. If you enter state A, you stay in state A forever. If you enter state B, you go through some sequence that goes through all the ...
  • 256
1 vote

Real number $p$ such that a $p$-coin makes the undecidable decidable

I was also wondering how to solve this problem. Although the comments seem to suggest that the poster of the question has already solved the problem, I will write up a solution regardless in case ...
  • 164
1 vote
Accepted

Undecidable Single Programs

One way to look at your question is the Busy Beaver Numbers. What we will do is restrict a Turing Machine so that: The blank symbol is a $0$ The tape alphabet is $\{0, 1\}$ The input to our turing ...
  • 1,102
1 vote

How to distinguish the properties applicable to Rice's theorem?

This question is probably more suitable in cs.se, but until it gets migrated, here is an answer. Rice's theorem regards non-trivial semantic properties. Formally, a semantic property is a set of ...
  • 5,316
1 vote

Recommendations for References on undecidability of First Order Logic

A Mathematical Introduction to Logic, Second Edition: Herbert B. Enderton

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