# Tag Info

## Hot answers tagged undecidability

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

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

### 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,347
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

### 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 ...
• 23.1k

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