154
Translating Code to Mathematics
Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...
57
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:
Run M on input x;
print "Finished running input";
If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run ...
42
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 have to invent a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and ...
33
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 proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...
32
Execution Counts of Statements
There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "...
20
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 knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (...
20
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 related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you ...
19
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 $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the ...
17
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 words $x_1,\ldots,x_n \in \mathcal{A}^*$ such that $w = x_1 x_2 \ldots x_n$. Since $x_i \in \mathcal{A}^*$, there exists an integer $m_i$ such that $x_i \in \...
15
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.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-...
14
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 at the same time in different parts of the string.
Also we have the basic toolbox:
concatenation: $S\to S_1S_2$ if you can split the language in two consecutive ...
14
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 as $L_1/L_2=\{x \mid \exists y\in L_2 \text{ such that } xy\in L_1\}$.
It is easily proved that regular set are closed under quotient by an
arbitrary set. In ...
14
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 much harder to prove than upper bounds. To prove that there's a sorting algorithm that requires $O(n\log n)$ comparisons, you just need to exhibit such an ...
14
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) algorithmically decide if it has.
Consider the following class of inputs for the dead-code identifier:
simulateMx(n) {
simulate TM M on input x for n steps
if M did ...
14
I will use the following simple sorting algorithm as an example:
repeat:
if there are adjacent items in the wrong order:
pick one such pair and swap
else
break
To prove the correctness I use two steps.
First I show that the algorithm always terminates.
Then I show that the solution where it terminates is the one I want.
For the first point,...
13
One useful tool is Rice's theorem. Here is what it says:
Let $\emptyset \subsetneq P \subsetneq \mathcal{P}$ a non-trivial set of
partially computable unary functions and $\varphi$ a Gödel numbering of $\mathcal{P}$. Then the index set of $P$
$\qquad I_P = \{ i \in \mathbb{N} \mid \varphi_i \in P \}$
is not recursive.
You find it also ...
12
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 starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$.
Non-decreasing $f(n)$
When $f(n)$ is monotone non-...
12
Elementary methods
Finite automata (possibly nondeterministic, with empty transitions).
Regular expressions.
Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular.
Regular (Type 3) grammar.
Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal,...
12
You are asking for a constructive proof of the Lesser limited principle of omniscience (LLPO), which states (in one of its forms) that for a decidable proposition $P$ on natural numbers
$$(\forall n \in \mathbb{N} \,.\, P(n)) \lor \lnot \forall n \in \mathbb{N} \,.\, P(n).$$
That's exactly your problem. It is well known that LLPO is not provable ...
12
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, since one of two cases may obtain:
There is an integer $N$ for which the decimal expansion of $\pi$ contains a run of $N$ consecutive 7s, but no longer run.
...
12
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 I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the ...
12
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 $L$ with a halting behavior (halting characteristic function)
that cannot be the halting behavior of any Turing machine.
The paradox built on the self applied ...
12
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 isn't necessary to plug in all possible values and sketch how to arrive at an $O^*((2^k-1)^{n/k})$ time algorithm, where $k$ is the number of clauses. $O^*$ '...
12
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$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to ...
12
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 (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ...
12
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. Rather, most proofs are written out of a kind of obligation, as a sort of run-away argument; not presenting proofs at all is considered unacceptable, but writing ...
12
The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$
11
There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem.
Dyck language
Let $T$ an alphabet. We define the Dyck-language $D_T \subseteq (T \cup \hat{T})^*$ of $T$ by the context-free grammar $G = (\{S\}, T \cup \hat{T}, \delta, S)$ with $\delta$ given by
$\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad ...
11
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 about the proof of the Cook-Levin theorem (SAT np-completeness).
At a very high level, the cook-levin theorem proof does this:
Assume R is some problem in NP. ...
11
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 diagonalization? question on cstheory for more.
Only top voted, non community-wiki answers of a minimum length are eligible