57 votes

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: ...
user avatar
  • 29.1k
42 votes
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 ...
user avatar
36 votes

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 ...
user avatar
  • 141k
31 votes
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$ ...
user avatar
21 votes
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 ...
user avatar
19 votes
Accepted

Is it really possible to prove lower bounds?

We can absolutely prove such things. Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\...
user avatar
19 votes

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 ...
user avatar
16 votes
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 ...
user avatar
15 votes

How to prove that a language is context-free?

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated ...
user avatar
  • 27.6k
15 votes
Accepted

How to prove that problem is not in P

The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i....
user avatar
14 votes
Accepted

Is there an algorithm that provably exists although we don't know what it is?

The simplest case I know of an algorithm that exists, though it is not known which algorithm, concerns finite state automata. The quotient $L_1/L_2$ of a language $L_1$ by a language $L_2$ is defined ...
user avatar
  • 19.1k
14 votes

Is it really possible to prove lower bounds?

Yes, it's possible. The classic example is the fact that any comparison-based sorting algorithm requires $\Omega(n\log n)$ comparisons to sort a list of length $n$. However, lower bounds seem to be ...
user avatar
14 votes

Proof that dead code cannot be detected by compilers

This is a twist on jmite's answer that circumvents the potential confusion about non-termination. I'll give a program that always halts itself, may have dead code but we can not (always) ...
user avatar
  • 70.9k
14 votes

How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
user avatar
  • 5,900
13 votes

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

Self application is not a necessary ingredient of the proof In a nutshell If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine ...
user avatar
  • 19.1k
12 votes

Solving or approximating recurrence relations for sequences of numbers

Summations Often one encounters a recurrence of the form $$ T(n) = T(n-1) + f(n), $$ where $f(n)$ is monotone. In this case, we can expand $$ T(n) = T(c) + \sum_{m=c+1}^n f(m), $$ and so given a ...
user avatar
12 votes

Is there an algorithm that provably exists although we don't know what it is?

To expand on Hendrick's original comment, consider this problem Given an integer $n\ge 0$ is there a run of $n$ or more consecutive 7s in the decimal expansion of $\pi$? This problem is decidable, ...
user avatar
  • 14.6k
12 votes

How is it valid to use oracles in mathematical arguments?

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently." I accept that it sounds a bit silly to go as far as "If ...
user avatar
12 votes
Accepted

Naive argument that P ≠ NP

The error in your argument is the claim Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values. , which is simply false. I will demonstrate why it ...
user avatar
  • 6,978
12 votes
Accepted

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
user avatar
  • 141k
12 votes

Show that there are infinitely more problems than we will ever be able to compute

Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (...
user avatar
  • 4,899
12 votes

Why are mathematical proofs so hard?

As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that proofs are not written for the purpose of teaching, even in most textbooks. ...
user avatar
  • 359
12 votes
Accepted

Is every unambiguous grammar regular?

The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$
user avatar
11 votes
Accepted

Direct NP-Complete proofs

At risk of sounding like I'm avoiding the question, I claim that every reduction is a direct proof of NP-completeness, just avoiding a lot of tedious, unnecessary work. First, let me talk a little ...
user avatar
11 votes
Accepted

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Yes, there are such proofs. They are based on the Low Basis Theorem. See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or ...
user avatar
  • 21.7k
11 votes

Why are mathematical proofs so hard?

I can certainly recommend the book of G. Polya's, How to Solve It. It is a standard classic, not to be missed. There is a newer book How to Read and Do Proofs: An Introduction to Mathematical Thought ...
user avatar
  • 211
10 votes

Is there a system behind the magic of algorithm analysis?

Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze). We can convert an algorithm complexity problem ...
user avatar
10 votes
Accepted

Correctness of proof by induction

Short answer: Proof by induction is correct because we define the natural integers as the set for which proof by induction works. On your interpretations and examples Your understanding seems ...
user avatar
10 votes

Proof of an Optimal substructure in Dynammic Programming?

There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it. You should do the following: Set up ...
user avatar
  • 70.9k
10 votes

How is it valid to use oracles in mathematical arguments?

There are several applications to oracles. First, there is usage in proving lower bounds (i.e. Turing reductions): if you know that a problem $L$ cannot be solved within some complexity (or ...
user avatar
  • 16.2k

Only top scored, non community-wiki answers of a minimum length are eligible