# Tag Info

148

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 ...

40

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 ...

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 ...

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 "...

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 ...

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


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 ...

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,...

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