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
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 ...
- 4,485
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,741
8
votes
What happens when the Linz halting problem proof is based on simulation of the input?
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 ...
- 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 ...
- 541
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 ...
- 1,347
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:
...
- 23.1k
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,485
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 ...
- 541
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 ...
- 23.1k
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 ...
- 521
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 ...
- 29.4k
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
Only top scored, non community-wiki answers of a minimum length are eligible