146
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
Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist?
[notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$]
...
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 ...
34
Converting Full History to Limited History
This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...
31
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 "...
30
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 ...
27
Generating Functions $\newcommand{\nats}{\mathbb{N}}$
Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...
22
First, let us make two maybe obvious, but important assumptions:
_.random_item can choose the last position.
_.random_item chooses every position with probability $\frac{1}{n+1}$.
In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:
For the singleton list there is only one possibility, so it is ...
22
There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:
Prove $L \subseteq \mathcal{L}(G)$.
Prove $[z^n]S_G(z) = |L_n|$.
The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.
The second step shows that $G$ has as many syntax ...
21
You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is).
Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions ...
21
Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done.
$\newcommand{\lang}[1]{\mathcal{L}(#1)}
\newcommand{\...
20
Master Theorem
The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...
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 (...
19
There are already good answers, but I would like to add a few small points.
Assume that we have a technique to solve problems, e.g. diagonalization. Assume that we want to show that the technique cannot solve a specific problem e.g. $\mathsf{P}$ vs. $\mathsf{NP}$. How can be show this?
Before going further, note that a technique like diagonalization is not a ...
19
The Special Case
Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case.
In "practice", we are given $L_2$ and are stuck with ...
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 ...
19
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 ...
18
There is a huge variety of feasible approaches. Which is best suited depends on
what you are trying to show,
how much detail you want or need.
If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can ...
18
Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works.
Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the ...
17
Guess & Prove
Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple:
Guess the solution and prove its correctness.
This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to ...
17
As it is unclear where your problem lies, I'll start at the very beginning.
Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.
More ...
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 \...
16
The language $\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$ seems to be simple. The second part is regular (and can be pumped). The first part is nonregular, but can be pumped "into" the second part by choosing $\$$ to pump.
(added) Of course, this can be generalized to $\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ for any ...
15
The Akra-Bazzi method
The Akra-Bazzi method gives asymptotics for recurrences of the form:
$$
T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$}
$$
This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out ...
15
Leveraging a known nearby problem
When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem.
Example problem
Consider a problem
$$\text{DOUBLE-SAT} = \{ \varphi \mid \varphi \text{ is a ...
14
A problem $Q$ is NP-complete if it is both NP-hard and in NP. This means that you need to disprove one of these two.
Under the assumption that P $\neq$ NP, you can give a polynomial time algorithm solving $Q$. Rarer, under the assumption that graph isomorphism is not NP-hard, you can show that $Q$ is polytime reducible to graph isomorphism.
You show that $...
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 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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
