# Tag Info

### Proof that dead code cannot be detected by compilers

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this: ...
Accepted

### Why are mathematical proofs so hard?

I feel like i am memorizing the proofs rather than learn how to prove You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you ...

### How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
Accepted

### Proving Equivalence of Two Regular Expressions

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...

### Does contradiction definitively prove nonexistence

A proof is a proof, even if the system you work in is inconsistent. So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in ...

### False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
Accepted

### Prove that A** = A*, where A is a language over Σ*

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and ...