Skip to main content
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 ...
Lorenzo's user avatar
  • 118
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 ...
Bjørn Kjos-Hanssen's user avatar
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 (...
Lance Fortnow's user avatar
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 ...
Dan Doel's user avatar
  • 1,021
6 votes

How to show that a problem is in $\Pi_1^1$?

The standard example of a $\Pi^1_1$ complete decision problem is the following: Is $e$ an index for a Turing machine which (halts on all inputs and) computes a well-ordering of $\mathbb{N}$? Let's ...
Noah Schweber's user avatar
6 votes

How to show that a problem is in $\Pi_1^1$?

I think that a good well-studied problem may be the "recurrent tiling problem". For more references (with many use cases) consult the paper "Recurring Dominoes: Making the Highly ...
Bartosz Bednarczyk's 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: ...
Marzio De Biasi's user avatar
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$ ...
Bjørn Kjos-Hanssen's user avatar
5 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 ...
Noah Schweber's user avatar
5 votes
Accepted

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

[EDIT: This result was already observed in Corollary 4.6 of the following paper: Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.] ...
2 votes

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

P1 Perhaps you can somewhat avoid self reference in this way. Let $S_k$ be the total number of steps performed by the halting Turing machines of size $\leq k$ in their computation. Suppose the Halting ...
Marzio De Biasi's user avatar
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 ...
Ville Salo's user avatar
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 ...
Andrej Bauer's user avatar
  • 29.2k
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 ...
lacker's user avatar
  • 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 ...
Tom Tseng's user avatar
  • 164

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