Tag Info

Accepted

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

In your edit, you write: What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less ...
• 2,010
Accepted

Is the infinite language unrecognizable in a Turing machine?

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable. A language is ...
• 6,940
Accepted

Halting problem theory vs. practice

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of ...
• 3,728

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context. Remember that Turing ...
• 17.7k

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO. In other words, $\emptyset$ is decidable. You might be confused ...
• 270k

Are there any existing problems that wouldn't be solvable with a halting oracle?

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of ...
• 28.2k
Accepted

Is it decidable whether a given context free grammar generates an infinite number of strings?

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive ...
• 16.2k
Accepted

undecidable problem and its negation is undecidable

Consider the following language: $$L_2 = \{(M_1,x_1,M_2,x_2) : \text{M_1 halts on input x_1 and M_2 doesn't halt on input x_2}\}.$$ $L_2$ is undecidable and not semi-decidable, and same is ...
• 141k
Accepted

Is it decidable whether a pushdown automaton recognizes a given regular language?

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet. Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-...
• 27.6k

Is it possible that the halting problem is solvable for all input except the machine's code?

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ ...
• 80.2k
Accepted

• 18.9k