Tag Info

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
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
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,711

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 ...
• 1,021

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 ...

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,337
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: ...

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
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 ...
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.] ...

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 ...

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.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 ...
• 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