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:
...
- 29.4k
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 ...
- 13.1k
37
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 ...
D.W.♦
- 149k
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$ ...
- 273k
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 ...
- 2,055
20
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 $\...
- 13.1k
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 ...
- 17.9k
18
votes
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 ...
- 28.9k
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 ...
- 273k
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 ...
- 80.8k
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) ...
- 71.5k
14
votes
How to prove greedy algorithm is correct
I will use the following simple sorting algorithm as an example:
...
- 5,910
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 ...
- 19.2k
13
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 (...
- 4,949
13
votes
Accepted
Is every unambiguous grammar regular?
The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$
- 273k
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 ...
- 80.8k
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 ...
- 7,138
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$...
D.W.♦
- 149k
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. ...
- 369
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 ...
- 21.8k
11
votes
Accepted
Show that there are infinitely more problems than we will ever be able to compute
If I understand you correctly, your question is —
why a solution can be encoded by a natural number and a problem with a real number.
(I assume that you understand the next phase of the proof ...
- 576
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 ...
- 211
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 ...
- 16.6k
10
votes
How to prove that a language is not regular?
Following the answer here, I will describe a method of proving non-regularity based on Kolmogorv complexity.
This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov ...
- 13.3k
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 ...
- 622
10
votes
Can a Minimum Possible Efficiency be proven?
There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.
...
- 19.7k
10
votes
Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup
There is no general way to find a decider TM for $L_k$
You are correct that $L_k$ is recursive because, being a subset of the
finite set $\Sigma^k$, it is also finite.
You would like to rather find ...
- 19.2k
10
votes
Accepted
Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)
I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general).
...
- 871
9
votes
Solving or approximating recurrence relations for sequences of numbers
There may be times when you come across a strange recurrence like this:
$$T(n) = \begin{cases}
c & n < 7\\
2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7
\end{...
- 4,381
9
votes
Accepted
Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f
You are not missing anything. These expressions are indeed not equivalent.
Assume $f$ in your case is an atomic proposition. Then the computation:
$f,\neg f,(f,\neg f)^\omega$ satisfies $□◊f$, but not ...
- 16.6k
Only top scored, non community-wiki answers of a minimum length are eligible