# Question
Title: Finding the point nearest to the x-axis over some segment
I have problem with solving the following exercise

> Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ find the first point that $s$ touches when moving upwards from the x-axis in time $O(\log^2n)$.

The preprocessing time is equivalent to sorting, so we can perform sorting by one dimension.

The query time is a little bit confusing - $\log^2$n. I would say it's $\log n$ binary searchs but it doesn't make sense.

# Answer
The $\log^2(n)$ implies that at each node in the search you probably have to do another search. This gave me an idea. Let's construct a tree from the input data: $$\text{LeafNode} = \\{ x, y \\}$$ $$\text{NonLeafNode} = \\{ \text{Min}\_x, \text{Max}\_x, \text{MinYPoint} \\}$$

Each node will partition the input space into two non-overlapping ranges. The root node will thus be the complete range of $x$ in the input data with the minimum $y$ value.

Then we define a recursive search function that takes a node and the horizontal line segment and returns either the minimum $y$ or $\text{NotFound}$ condition (for simplicity say the value of $\infty$ represents $\text{NotFound}$).

```
GlobalMinY = Infinity

search( Node, segment ) -> MinY
    if Node does not overlap segment
        return Inf
    if Node.MinY >= GlobalMinY
        return Inf
    if Node is sub-segment
            GlobalMinY = Node.MinY
        return Node.MinYPoint

    return Min( search(Node.Left), search(Node.Right) )

```

It's easy enough to construct these tree using a modified merge-sort, so construction time is within the bounds. What I'm having a hard time showing is that the search time is within the required bounds.

Search time: Other than the root node, at each node one of the Left or Right nodes will either be included completely or excluded completely. Only one of them can have a partial overlap. If this is correct the time is $2 \log(n)$ -- from root we do two searchs and each follows only a single path through the tree. I'm not even sure the GlobalMinY optimization is needed.
> 5 votes

# Answer
The problem can be solved using 2 Dimensional Range Trees with a slight augmentation.

2D Range Tree supports pre-processing of the $n$ points in $O(n\*\log{n})$ time.
The query for enumerating all points in a rectangle defined by 4 points can be done in $O(k+\log{n})$ time. Where $k$ is the number of points in the rectangle.

Let us say you have the horizontal segment $s$ between points $ (a,c) $ and $ (b, c) $.
We invoke the query operation on rectangle defined by $ (a,c) $ ,$ (b, c) $, $ (a, y\_{max})$, $ (b, y\_{max})$. Where $y\_{max}$ is the maximum among y-coordinates of given $n$ points.

In the $1^{st}$ level tree which is structured based on x-coordinates we might end up visiting the $2^{nd}$ level tree of at most $O(\log{n})$ nodes. And And each time we visit the $2^{nd}$ level tree of some node we should just return point with the smallest y co-ordinate in the y-range of rectangle. We finally return the point with minimum y-coordinate among at most $O(\log{n})$ such points. Each such traversal on $2^{nd}$ level tree takes $O(\log{n})$ time. So, the query time of this scheme is $O(\log^2{n})$
> 3 votes

---
Tags: algorithms, computational-geometry
---


title: How to implement deep copy?

text:
# Question
Title: How to implement deep copy?
Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them.

* Reflection-based (Python)
* Auto-generated shallow-copy-based (Java)
* Compiler-generated polymorphic deep copy (anybody?)

The last one seems to be the most efficient one, but I do not know if it is implemented anywhere.

# Answer
> 3 votes
You have to be very careful of what you mean when you say "deep-copying". This came up in a thread at StackOverflow in relation to C++. The first question you need to address is can an automatic "deep-copy" even be done? Consider just a few basic quesetions:

1. If the type of a data element is a referential type can you determine whether a deep copy implies copying the reference or the referred to type? That is, can you identify the ownership of these items?
2. Does the presence of a singleton, or external resource, prevent a deep copy, or does the copy refer to the same resource?
3. Given that data relations often form graphs with cycles. Could such a relationship automatically be detected? Even if yes, what would if mean to start the deep copy at an inner-node of such a structure?

This is likely why you only find references which are very language specific. Each language has its own notion of copying. This default copy is not likely to match the expected notion of a deep-copy in all situations.

I would say it is not possible to even specify what deep-copy is without explicitly enumerating the types available in a given language. This would essentially require that all research about deep-copying is specific to a particular language (even if that language is theoretical).

If you are looking for efficiency comparisons you would then also be stuck in the domain of a very particular language. You could possible define a reduced compound data type common to several languages and evaluate the efficiency of copying such structures. Such results however would not be applicable to any language with more complex data types.

# Answer
> 1 votes
Partial answer for functional languages:

In Ocaml, I believe this could be done even at runtime, because even if types are removed, we know if a word is a pointer or some data. However, it is not that good of an idea, because in the pure part of Ocaml (which is often well-understood) you don't need deep copy: the data structures are not mutable, thus deep copy will have no other effect than occupying more memory. It is all the more true for pure functional programming languages like Haskell.

About the types:

Note that despite the fact that it is useless for functional languages, the typing information there is in those would be enough to provide a compile-time-generated deep copy *generic* functions. (But *not* polymorphic, the copy function needs to be aware of types).

---
Tags: programming-languages, compilers
---


# Question
Title: Which is the minimal number of operations for intractability?
If we have an algorithm that need to run $n=2$ operations and then halt, I think we could say the problem it solves, is tractable, but if $n=10^{120}$ althought It could be theoretically solvable it seems to be intractable, and what about a problem that needs $n=10^{1000}$, or $n=10^{10^{1000}}$ operations, that's seems an intractable problem for sure.

Then we see there is a k, from which $n\ge k$ operations problems are intractable, and $n\lt k$ are tractable ones.

I doubt about that k to exist.. Where is the limit? Can a Technological advance turn some intractable problems **for a given n** into a tractable ?

I would like to read your opinion.

**EDIT**

I think this question is similar as asking if Church–Turing thesis is correct, because if the difference about solving a computable problem in a Turing Machine and in any other Turing Complete Machine, is "only a constant" about the number of operations, then I think that asking about computable is the same as asking about effective calculability.. Now I see tractable means polynomial time, and inctractable is related with no polynomial time solution. But the difference between two machines, for the same (even tractable) problem, is about Church-Turing thesis.

# Answer
Intractability is a graphical metaphor for a notion related to asymptotic complexity.

Let me remind that in abstract terms a computational problem is to find given an input $s$ a solution $r$ to an instance of the problem specified by $s$.

A problem is tractable if for every input $s$ of size $n$ a solution can be found with a number of operations bounded by a certain *slowly growing* function $P(n)$. The definition of slow growth is not important at this stage. Let us agree that a linear function is slowly growing and an exponential $e^n$ is *not* slowly growing.

If no such slowly growing upper bound exists, we have to admit that the problem is intractable. That is for any improvement in computer technology we can slightly increase the size of the input to render the effect of this improvement to zero.

Thus the precise meaning of the notion of intractability is that it stands against any technological advance.

It is important to note that there is no concrete integer number that characterizes intractability. It is the rate of growth that makes a problem intractable.

If instead you look at a specific question like solving the game of chess, you cannot say that it is intractable since as soon as it is solved once the problem will become trivial. Thus the notion of intractability does not apply to specific one-off problems whatever be the number of operations that a particular algorithm to solve them takes.

Here is a final remark to check your understanding.

> An algorithm is called efficient if it efficiently solves every instance of some computational problem. If for some instance it takes this efficient algorithm $10^{20}$ operations to complete, a trivial algorithm that simply reproduces the solution once produced by an efficient algorithm will beat the efficient algorithm to this problem. Yet this trivial algorithm will fail at any instance of the problem that was not previously seen.
> 4 votes

---
Tags: complexity-theory, church-turing-thesis
---


# Question
Title: Reduction to equipartition problem from the partition problem?
Equipartition Problem:

Instance: $2n$ positive integers $x\_1,\dots,x\_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x\_{i} = 2B$.

Query: Is there a subset $I \subseteq \[2n\]$ of size $|I| = n$ such that $\sum\_{i \in I} x\_{i} = B$?

Can the partition problem \- same as the above but without the restriction on $|I|$ - be reduced to the above problem ?

# Answer
> 4 votes
As noted in the comments, the EQUIPARTITION problem is also NP-complete. The basic idea of reducing PARTITION to it is to add elements so that they can be partitioned complementary to the original elements (thus yielding an equipartition) but in a way that ensures that new and old elements can not cancel each other out. The latter can be achieved by choosing the new elements sufficiently large.

---

Let $A = \\{a\_1, \dots, a\_n\\} \subseteq \mathbb{N}\_+$ be an instance of PARTITION. Construct an instance $f(A)$ of EQUIPARTITION by

$\qquad \displaystyle f(A) = A \cup \\{ a\_{n+i} \mid a\_{n+i} = 2B \cdot a\_i, a\_i \in A \\}$

with $2B = \sum\_{a \in A} a$. It is clear that $f$ can be computed in deterministic polynomial time. We have to show that $A$ is a YES-instance of PARTITION if and only if $f(A)$ is a YES-instance of EQUIPARTITION.

* Let $A$ be a YES-instance of PARTITION, that is there is $I \subset \[n\]$ with $\sum\_{i \in I} a\_i = B$. Then,

$\qquad \displaystyle I' = I \cup \\{n+i \mid i \in \overline{I} = \[n\] \setminus I \\}$

is a solution of $f(A)$; note that $|I'| = n$ and $\sum\_{i \in I'} a\_i = B + 2B^2 = \sum\_{i \in \overline{I'}} a\_i$. Thus, $f(A)$ is a YES-instance of EQUIPARTITION.
* Let $f(A)$ be a YES-instance of EQUIPARTITION. Let $I' = I \cup J$ a solution of $f(A)$ with $I \subseteq \[n\]$ and $J \subseteq \[2n\] \setminus \[n\]$ ($I$ contains the indices chosen from $A$, $J$ the new ones), and $\overline{I'} = \overline{I} \cup \overline{J}$ its complement, similarly partitioned. That is, $\sum\_{i \in I'} a\_i = \sum\_{i \in \overline{I'}} a\_i$

Assume towards a contradiction that $\sum\_{i \in I} a\_i \neq \sum\_{i \in \overline{I}} a\_i$; without loss of generality assume $\sum\_{i \in I} a\_i \> \sum\_{i \in \overline{I}} a\_i$. Now we have that

$\qquad \displaystyle 0 \< \sum\_{i \in \overline{J}} a\_i - \sum\_{i \in J} a\_i = \sum\_{i \in I} a\_i - \sum\_{i \in \overline{I}} a\_i \< 2B$

which contradicts the construction of $f(A)$; elements with indices in $J \cup \overline{J}$ are all (positive) multiples of $2B$ so the assumed difference is impossible. Therefore, $I$ is a solution of $A$ which is thus a YES-instance of PARTITION.

This concludes the proof, that is PARTITION $\leq\_p$ EQUIPARTITION by virtue of $f$.

---
Tags: complexity-theory, reductions, np-hard
---


title: Building ideal skip lists

text:
# Question
Title: Building ideal skip lists
I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list.

The definition of an “ideal skip list” is that in the first level we'll have all the elements, half of them in the next level, a quarter of them in the level after that, and so on.

I'm thinking about a $\mathcal{O}(n)$ run-time algorithm involving throwing a coin for each node in the original linked-list, to determine for any given node whether it should be placed in a higher or lower level, and create a duplicate node for the current node at a higher level. This algorithm should work in $\mathcal{O}(n)$; is there any better algorithm?

# Answer
> 1 votes
Following your idea, you can do this:

* Iterate through the (sorted) list.
* For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.

For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log\_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log\_{1/p} n)$ additional memory in expectation.

Note that the resulting list is not stricly "ideal" but in expectation; the interesting operations have logarithmic expected runtime due to the resulting distribution. See William Pugh's Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) and the work referenced there for details.

It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).

---
Tags: algorithms, data-structures, randomized-algorithms, lists
---


# Question
Title: Algorithm to check the 2∀-connectness property of a graph
A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of G.

I know the basic idea is to build a DFS searching tree and then check each edge is not on a circle with DFS. Any help would be appreciated.

What I expect to see is a detailed algorithm description(especially the initialization of needed variables which is obscure sometimes), complexity analysis could be omitted.

# Answer
> 5 votes
A simple algorithm is the following:

Let $G = (V,E)$ be the graph you want to check for 2-connectivity.

> For each edge $e = (x,y) \in E$, look if there is a path from $x$ to $y$ in $(V, E \setminus \\{e\\})$. If for some $e$, there is not such a path, the graph is not 2-edge connected. If there is such a path for each $e$, $G$ is 2-edge connected.

You should also note, that this algorithm is not the fastest, but very easy to understand. The path-finding part can be done using for example BFS or Dijkstra's Algorithm.

This article also shows a simple algorithm for testing 2-edge connectivity, which runs in linear time.

---
Tags: algorithms, graphs, efficiency
---


# Question
Title: Computing follow sets conservatively for a PEG grammar
Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good approximation that is conservative -- if a character can follow a node then it must appear in the follower set.

The grammar is represented as a tree of named productions whose bodies contain nodes representing

1. Character
2. Concatenation
3. Union
4. Non-terminal references

So given a grammar in ABNF style syntax:

```
A := B ('a' | 'b');
B := ('c' | 'd') (B | ());

```

where adjacent nodes are concatenated, `|` indicates union, single quoted characters match the character they represent, and upper case names are non-terminals.

If the grammar's start production is `A`, the annotated version might look like

```
A :=
  (
    (B /* [ab] */)
    (
      ('a' /* eof */)
    |
      ('b' /* eof */)
    /* eof */
    )
  /* eof */
  );

B :=
  (
    (
      ('c' /* [abcd] */)
      |
      ('d' /* [abcd] */)
    /* [abcd] */
    )
    (
      (B /* [ab] */)
      |
      ( /* [ab] */)
    /* [ab] */
    )
  );

```

I want this so that I can do some simplification on a PEG grammar. Since order is important in unions in PEG grammars, I want to partition the members of unions based on which ones could accept the same character so that I can ignore order between partition elements.

I'm using OMeta's grow-the-seed scheme for handling direct left-recursion in PEG grammars, so I need something that handles that. I expect that any scheme for handling scannerless CF grammars with order-independent unions that is conservative or correct would be conservative for my purposes.

Pointers to algorithms or source code would be much appreciated.

# Answer
Follow or lookahead sets are a standard concept in compiler theory. I would expect every textbook on the topic to contain an algorithm for them; as for online resources, try this or that one. It seems as if the choice of algorithm depended on what kind of grammar -- LL, LR, LALR, ... -- you have.
> 5 votes

# Answer
Raphael gave useful pointers but nothing that works before a grammar is reduced to a state-machine. I find doing as much work as possible via parse-tree -\> parse-tree transformations lets grammar authors debug familiar structures. Below I include some OCaml that does the job purely on a parse-tree in case others are interested:

```
let followers (Grammar (m, prods)) start_prod_name =
  let n_prods = List.length prods in

  (* Maps production names to the set of characters that might follow
   * a use of that production. *)
  let ref_followers = IdentHashtbl.create n_prods in

  (* Maps production names to the set of characters that might precede
   * the start of that production. *)
  let prod_preceders = IdentHashtbl.create n_prods in

  (* Assume that all productions are followed and preceded by the
   * empty set.  Later we iterate until convergence expanding these sets. *)
  List.iter
    (fun (Production (_, name, _)) ->
      IdentHashtbl.replace ref_followers name RangeSet.empty;
      IdentHashtbl.replace prod_preceders name RangeSet.empty)
    prods;

  (* Assume conservatively that the start production specifies at least
   * one finite-length string. *)
  IdentHashtbl.replace ref_followers start_prod_name
    (RangeSet.singleton end_of_file_code_point);

  let iter_until_convergence f =
    let rec converge f last =
      let next = f () in
      if next = last then
        last
      else
        converge f next in
    converge f (f ()) in

  (**
   * [annotated_node node followers] annotates a grammar parse-tree with
   * a conservative (overly large) set of characters that can immediately
   * follow any prefix that occurs before node is entered.
   * @oaram followers the set of characters that can follow node.
   * @return the annotated node, the preceder set of node.
   *)
  let rec annotate_node node followers = match node with
    | CharSet (m, ranges) ->
      CharSet (A.annotate m ranges, ranges), ranges

    | Concatenation (m, children) ->
      let annotated_children, preceders =
        let rec children_backwards children =
          (match children with
            | [] -> [], followers
            | child::rest ->
              let annotated_children, followers =
                children_backwards rest in
              let annotated_child, preceders =
                annotate_node child followers in
              annotated_child::annotated_children, preceders) in
        children_backwards children in
      (* The set that follows the start of a concatenation is the set that
       * precedes the first element. *)
      Concatenation (A.annotate m preceders, annotated_children), preceders

    | Reference (m, name) ->
      (* Add the call site followers with those from the map for the
       * next call to (annotate_prod name) to consider. *)
      IdentHashtbl.replace
        ref_followers name
        (RangeSet.union
           (IdentHashtbl.find ref_followers name)
           followers);
      let preceders = IdentHashtbl.find prod_preceders name in
      Reference (A.annotate m preceders, name),
      preceders

    | Repetition (m, body) ->
        (* If the last repetition of body is preceded by P and followed by F,
         * then if we treat the last repetition as optional, and consider
         * a previous instance of body, then that previous instance can be
         * followed by P or F, so we can compute its preceders by treating
         * it as followed by (P u F).
         * We iterate until convergence.
         *)
      let rec converge annotated_body followers preceders =
        let prev_instance_followers = RangeSet.union followers preceders in
        let prev_annotated_body, prev_instance_preceders =
          annotate_node body prev_instance_followers in
        if prev_annotated_body = annotated_body
        && prev_instance_preceders = preceders then
          annotated_body, preceders
        else
          converge prev_annotated_body followers prev_instance_preceders in
        (* Repetitions always match at least once. *)
      let annotated_body, preceders = annotate_node body followers in
      let annotated_body, preceders =
        converge annotated_body followers preceders in
      Repetition (A.annotate m preceders, annotated_body), preceders

    | Union (m, o, children) ->
      let annotated_children, preceders =
        List.fold_right
          (fun child (annotated_children, preceders) ->
            let annotated_child, child_preceders =
              annotate_node child followers in
            (annotated_child::annotated_children,
             RangeSet.union preceders child_preceders))
          children ([], RangeSet.empty) in
      Union (A.annotate m preceders, o, annotated_children), preceders in

  let annotate_prod (Production (m, name, body)) =
    let followers = IdentHashtbl.find ref_followers name in
    let annotated_body, preceders = annotate_node body followers in
    IdentHashtbl.replace prod_preceders name preceders;
    Production (A.annotate m preceders, name, annotated_body) in

  let annotate_grammar () =
    Grammar (
      A.annotate m (RangeSet.empty),
      List.map annotate_prod prods) in

  iter_until_convergence annotate_grammar

```
> 0 votes

---
Tags: formal-languages, reference-request, formal-grammars, parsers
---


# Question
Title: How to describe algorithms, prove and analyse them?
Before reading *The Art of Computer Programming (TAOCP)*, I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only about orders of growth. The *TAOCP* thoroughly changes my mind.

*TAOCP* uses English mixed with steps and *goto* to describe the algorithm, and uses flow charts to picture the algorithm more readily. It seems low-level, but I find that there's some advantages, especially with flow chart, which I have ignored a lot. We can label each of the arrows with an assertion about the current state of affairs at the time the computation traverses that arrow, and make an inductive proof for the algorithm. The author says:

> It is the contention of the author that we really understand why an algorithm is valid only when we reach the point that our minds have implicitly filled in all the assertions, as was done in Fig.4.

I have not experienced such stuff. Another advantage is that, we can count the number of times each step is executed. It's easy to check with Kirchhoff's first law. I have not analysed the running time exactly, so some $\pm1$ might have been omitted when I was estimating the running time.

Analysis of orders of growth is sometimes useless. For example, we cannot distinguish quicksort from heapsort because they are all $E(T(n))=\Theta(n\log n)$, where $EX$ is the expected number of random variable $X$, so we should analyse the constant, say, $E(T\_1(n))=A\_1n\lg n+B\_1n+O(\log n)$ and $E(T\_2(n))=A\_2\lg n+B\_2n+O(\log n)$, thus we can compare $T\_1$ and $T\_2$ better. And also, sometimes we should compare other quantities, such as variances. Only a rough analysis of orders of growth of running time is not enough. As *TAOCP* translates the algorithms into assembly language and calculate the running time, It's too hard for me, so I want to know some techniques to analyse the running time a bit more roughly, which is also useful, for higher-level languages such as C, C++ or pseudo codes.

And I want to know what style of description is mainly used in research works, and how to treat these problems.

# Answer
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 be said for analyses: if you need a rough upper runtime bound you proceed differently from when you want precise counts of statements.

I will give you three examples for the well-known algorithm Mergesort which hopefully illustrate this.

### High Level

The algorithm Mergesort takes a list, splits it in two (about) equally long parts, recurses on those partial lists and merges the (sorted) results so that the end-result is sorted. On singleton or empty lists, it returns the input.

This algorithm is obviously a correct sorting algorithm. Splitting the list and merging it can each be implemented in time $\Theta(n)$, which gives us a recurrence for worst case runtime $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$. By the Master theorem, this evaluates to $T(n) \in \Theta(n\log n)$.

### Medium Level

The algorithm Mergesort is given by the following pseudo-code:

```
procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

```

We prove correctness by induction. For lists of length zero or one, the algorithm is trivially correct. As induction hypothesis, assume `mergesort` performs correctly on lists of length at most $n$ for some arbitrary, but fixed natural $n\>1$. Now let $L$ be a list of length $n+1$. By induction hypothesis, `left` and `right` hold (non-decreasingly) sorted versions of the first resp. second half of $L$ after the recursive calls. Therefore, the `while` loop selects in every iteration the smallest element not yet investigated and appends it to `result`; thus `result` is a non-increasingly sorted list containing all elements from `left` and `right`. The reverse is a non-decreasingly sorted version of $L$, which is the returned -- and desired -- result.

As for runtime, let us count element comparisons and list operations (which dominate the runtime asymptotically). Lists of length less than two cause neither. For lists of length $n\>1$, we have those operations caused by preparing the inputs for the recursive calls, those from the recursive calls themselves plus the `while` loop and one `reverse`. Both recursive parameters can be computed with at most $n$ list operations each. The `while` loop is executed exactly $n$ times and every iteration causes at most one element comparison and exactly two list operations. The final `reverse` can be implemented to use $2n$ list operations -- every element is removed from the input and put into the output list. Therefore, the operation count fulfills the following recurrence:

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

By the Master theorem, we get $T \in \Theta(n \log n)$ which extends to the runtime of `mergesort`.

### Ultra-low level

Consider this (generalised) implementation of Mergesort in Isabelle/HOL:

```
types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

```

This already includes proofs of well-definedness and termination. Find an (almost) complete correctness proof here.

For the "runtime", that is number of comparisons, a recurrence similar to the one in the prior section can be set up. Instead of using the Master theorem and forgetting the constants, you can also analyse it to get an approximation that is asymptotically equal the true quantity. You can find the full analysis in \[1\]; here is a rough outline (it does not necessarily fit the Isabelle/HOL code):

As above, the recurrence for the number of comparisons is

$\qquad \begin{align}f\_0 = f\_1 &= 0 \\ f\_n &= f\_{\left\lceil\frac{n}{2}\right\rceil} + f\_{\left\lfloor\frac{n}{2}\right\rfloor} + e\_n\end{align}$

where $e\_n$ is the number of comparisons needed for merging the partial results². In order to get rid of the floors and ceils, we perform a case distinction over whether $n$ is even:

$\qquad \displaystyle \begin{cases} f\_{2m} &= 2f\_m + e\_{2m} \\ f\_{2m+1} &= f\_m + f\_{m+1} + e\_{2m+1} \end{cases}$

Using nested forward/backward differences of $f\_n$ and $e\_n$ we get that

$\qquad \displaystyle \sum\limits\_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f\_k = f\_n - nf\_1$.

The sum matches the right-hand side of Perron's formula. We define the Dirichlet generating series of $\Delta\kern-.2em\nabla f\_k$ as

$\qquad \displaystyle W(s) = \sum\limits\_{k\geq 1} \Delta\kern-.2em\nabla f\_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits\_{k \geq 1} \frac{\Delta\kern-.2em\nabla e\_k}{k^s}}\_{=:\ \boxminus(s)}$

which together with Perron's formula leads us to

$\qquad \displaystyle f\_n = nf\_1 + \frac{n}{2\pi i} \int\limits\_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$.

Evaluation of $\boxminus(s)$ depends on which case is analysed. Other than that, we can -- after some trickery -- apply the residue theorem to get

$\qquad \displaystyle f\_n \sim n \cdot \log\_2(n) + n \cdot A(\log\_2(n)) + 1$

where $A$ is a periodic function with values in $\[-1,-0.9\]$.

---

1. Mellin transforms and asymptotics: the mergesort recurrence by Flajolet and Golin (1992)
2. Best case: $e\_n = \left\lfloor\frac{n}{2}\right\rfloor$
Worst case: $e\_n = n-1$
Average case: $e\_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$
> 20 votes

# Answer
Dijkstra's "A discipline of Programming" is all about analyzing and proving algorithms and designing for provability. In the preface to that book, Dijkstra explains how a very simple constructed mini-language that is properly designed to be analyzed suffices to explain many algorithms formally:

> When starting on a book like this, one is immediately faced with the question: "Which programming language am I going to use?", and this is *not* a mere question of presentation! A most important, but also a most elusive, aspect of any tool is its influence on the habits of those who train themselves in its use. If the tool is a programming language, this influence is -- whether we like it or not -- an influence on our thinking habits. Having analyzed that influence to the best of my knowledge, I had come to the conclusion that none of the existing programming languages, nor a subset of them, would suit my purpose; on the other hand I knew myself so unready for the design of a new programming language that I had taken a vow not to do so for the next five years, and I had a most distinct feeling that that period had not yet elapsed! (Prior to that, among many other things, this monograph had to be written.) I have tried to resolve this conflict by only designing a mini-language suitable for my purposes, by making only those commitments that seemed unavoidable and sufficiently justified.

Later he explains just how small he managed to get his mini-language.

> I owe the reader an explanation why I have kept the mini-language so small that it does not even contain procedures and recursion. ... **The point is that I felt no need of them in order to get my message across, viz. how a carefully chose separation of concerns is essential for the design of in all respect, high-quality programs; the modest tools of the mini-language gave us already more than enough latitude for nontrivial, yet very satisfactory designs.**
> 3 votes

---
Tags: algorithms, proof-techniques, runtime-analysis
---


# Question
Title: Is switching quantifiers allowed in this instance?
In Logic In Computer Science (2nd Edition - Michael Huth and Mark Ryan), exercise 2.4.12.k is the following:

> For each of the formulas of predicate logic below, either find a model which does not satisfy it, or prove it is valid.

This one is difficult:

> (∀x ∃y (P(x) → Q(y))) → (∃y ∀x (P(x) → Q(y)))

Not only am I not sure how to prove this, I'm not sure whether it is valid or not. I came across this question when revising for an exam and always hit a dead end with it.

Any suggestions or insight is appreciated.

# Answer
> 6 votes
The key issue here is whether switching quantifiers is okay. Turn the top-level implication around and see what happens then.

As for this formula, think about what the left- resp. the right-hand side say.

* Left: "Every $x$ has a $y$ so that... holds."
* Right: "There is a $y$ so that ... holds for all $x$."

In particular, the left-hand side allows *different* $y$ -- one for each $x$ -- while the right-hand side requires a *single* $y$.

With this off the table, try to figure out whether

$\qquad \left(\forall x. \exists y. P(x,y)\right) \to \left(\exists y. \forall x. P(x,y)\right)$

holds for all predicates $P$. If so, your original questions is answered, and if not it should be easy to modify a counter-example to have the necessary form of an implication.

> For the simplified formula, there is a simple counter-example: every natural number has a successor, but there is no natural number that is successor to all natural numbers.

Try to utilise this before lifting the next spoiler!

> No luck? Well, that is to be expected. The "simplified" formula was a trap as it is not really a simplified formula, as you have hopefully figured out. It allows you to set $x$ and $y$ in relation which your formula does not: the (inner) implications can be read as disjunction, i.e. $\lnot P(x) \lor Q(y)$, so $P$ and $Q$ can fulfill the disjunction independently of another.

Can you prove that the formula holds now?

> If the left-hand side is fulfilled -- if it is not, the whole formula is trivially fulfilled -- all $x$ fulfill $\lnot P(x)$ or there is (at least) one $y$ that fulfills $Q(y)$ (to rescue the failing $x$). In either case (they can overlap!) the right hand side is fulfilled. In particular, if $\lnot P(x)$ is true for all $x$, $y$ can be chosen arbitrarily (on the right-hand side), else choose one of the rescuers. Be aware that the empty element domain -- if allowed -- is a special case.

# Answer
> 1 votes
consider the empty {P,Q}-structure ...

# Answer
> 1 votes
Let's try to express $(\forall x, \exists y, (P(x) \rightarrow Q(y))) \to (\exists y, \forall x, (P(x) \rightarrow Q(y)))$ in English:

> Premise: suppose that for every $x$, there is a $y$ such that $P(x)$ implies $Q(y)$.
> Conclusion: then there is a $y$ such that for every $x$, $P(x)$ implies $Q(y)$.

Suppose the premise holds, and suppose that we have found an $x\_0$ such that $P(x\_0)$ holds. Then there is a $y\_0$ such that $Q(y\_0)$ holds. There is nothing specific to $x\_0$ about $y\_0$: if there is some other $x$ that satisfies $P(x)$, then we can take that same $y\_0$, we still have $Q(y\_0)$, hence we still have that $P(x)$ implies $Q(y)$.

Or, in other words, if the premise holds and there is an $x\_0$ such that $P(x\_0)$ holds, then the conclusion holds. We have proved that the formula is always true under the additional assumption $\exists x\_0, P(x\_0)$.

So all we need to do now is look at what happens if that additional assumption does not hold. By the principle of excluded middle and the well-known principles of inversion of negation and quantifiers, the opposite assumption is $\forall x, \neg P(x)$. Since $P(x)$ never holds, the implication $P(x) \rightarrow Q(y)$ always holds. Are we finished? Almost. If we take any $y\_0$ in the model, then the formula $\forall x, (P(x) \rightarrow Q(y\_0))$ holds. So the conclusion is true in every non-empty model, hence the formula holds in every non-empty model.

If you allow an empty model, then the formula does not hold, because the premise is true ($\forall x, …$ is vacuously true) and the conclusion is false ($\exists y, …$ is vacuously false).

---
Tags: logic, logical-validity
---


# Question
Title: Categorisation of type systems (strong/weak, dynamic/static)
In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear?

In a sense the difficulty with this question is not that I can't find an answer, but rather that I can find too many, and none stand out as correct. The background is I am attempting to improve an article on the Haskell wiki about typing, which currently claims the following distinctions:

* No typing: The language has no notion of types, or from a typed perspective: There is exactly one type in the language. Assembly language has only the type 'bit pattern', Rexx and Tk have only the type 'text', core MatLab has only the type 'complex-valued matrix'.
* Weak typing: There are only few distinguished types and maybe type synonyms for several types. E.g. C uses integer numbers for booleans, integers, characters, bit sets and enumerations.
* Strong typing: Fine grained set of types like in Ada, Wirthian languages (Pascal, Modula-2), Eiffel

This is entirely contrary to my personal perception, which was more along the lines of:

* Weak typing: Objects have types, but are implicitly converted to other types when the context demands it. For example, Perl, PHP and JavaScript are all languages in which `"1"` can be used in more or less any context that `1` can.
* Strong typing: Objects have types, and there are no implicit conversions (although overloading may be used to simulate them), so using an object in the wrong context is an error. In Python, indexing an array with a string or float throws a TypeError exception; in Haskell it will fail at compile time.

I asked for opinions on this from other people more experienced in the field than I am, and one gave this characterisation:

* Weak typing: Performing invalid operations on data is not controlled or rejected, but merely produces invalid/arbitrary results.
* Strong typing: Operations on data are only permitted if the data is compatible with the operation.

As I understand it, the first and last characterisations would call C weakly-typed, the second would call it strongly-typed. The first and second would call Perl and PHP weakly-typed, the third would call them strongly-typed. All three would describe Python as strongly-typed.

I think most people would tell me "well, there is no consensus, there is no accepted meaning of the terms". If those people are wrong, I'd be happy to hear about it, but if they are right, then how *do* CS researchers describe and compare type systems? What terminology can I use that is less problematic?

As a related question, I feel the dynamic/static distinction is often given in terms of "compile time" and "run time", which I find unsatisfactory given that whether or not a language is compiled is not so much a property of that language as its implementations. I feel there should be a purely-semantic description of dynamic versus static typing; something along the lines of "a static language is one in which every subexpression can be typed". I would appreciate any thoughts, particularly references, that bring clarity to this notion.

# Answer
Historically, the term "strongly typed programming language" came into use in the 70's in reaction to the existing widely used programming languages, most of which had type holes. Some examples:

* In Fortran, there were things called "COMMON" storage areas, which could be shared across modules, but there were no checks to see if each module was declaring the contents of the COMMON storage with the same types. So, one module could declare that a particular COMMON storage block had an integer and another a floating point number, and the data would get corrupted as a result. Fortran also had "EQUIVALENCE" statements, whereby the same storage could be declared to contain two different objects of different types.
* In Algol 60, the type of procedure parameters was declared as just "procedure", without specifying the types of the parameters of the procedure. So, one could assume that a procedure parameter was an integer-accepting procedure, but pass in a real-accepting procedure as the argument. This would result in the same kind of corruption as the COMMON and EQUIVALENCE statements. (However, Algol 60 did eliminate the older problems.)
* In Pascal, "variant records" were added which were almost exactly like the old EQUIVALENCE statements.
* In C, "type casts" were added whereby any type of data could be reinterpreted as data of a different type. This was a rather deliberate type hole meant for programmers who supposedly know what they are doing.

The strongly typed languages designed in the 70's were meant to eliminate all such type holes. If you drill down into what this means, it means essentially that data representations are protected. It is not possible to view data object of one type as an object of another type which happens to have the same bit pattern as its internal representation. Theoreticians began to use the term "representation independence" to characterize this property instead of the vague idea of "strong typing".

Note that dynamically typed languages like Lisp which perform complete run-time type checking are "strongly typed" in the sense of protecting representations. At the same time, statically typed languages would lose representation independence unless they did array bounds checking. So, they are not "strongly typed" in the strict sense of the term. Due to these anomalous consequences, the term "strongly typed" fell into disuse after the 70's. When the US Department of Defence developed rigorous requirements for the design of Ada, they included the requirement that the language should be "strongly typed". (It seems to have been believed at that time that the idea of "strongly typed" was self-evident. No definition was offered.) All the language proposals submitted in response claimed to be "strongly typed". When Dijkstra analysed all the language proposals, he found that none of them were strongly typed and, in fact, it wasn't even clear what the term meant. See the report EWD663. However, I see that the term is coming back into use now, through a younger generation of researchers who don't know the checkered history of the term.

The term "statically typed" means that all type-checking is done statically and no type errors will arise at run-time. If the language is also strongly typed, that means that there are really *no type errors* during execution. If, on the other hand, there are type holes in the type system, the absence of run-time type errors means nothing. The results could be completely corrupt.

The new debate about "strong vs weak typing" seems to be about whether certain type conversions should be allowed. Allowing a string where an integer is required is "weak typing" according to these folks. There is some sense to that because attempting to convert a string to an integer may fail, if the string doesn't happen to represent an integer. However, converting an integer to a string doesn't have that problem. Would that be an instance of "weak typing" according to these folks? I have no idea. I notice that the Wikipedia discussions on "weak typing" don't cite any refereed publications. I don't believe that it is a coherent idea.

**Note added**: The basic point is that the term "strong typing" did not come into use as a technical term with a rigorous definition. It was more like some language designers felt: "our type system is strong; it catches all type errors; it doesn't have type holes" and, so, when they published their language design, they claimed that it was "strongly typed". It was a buzz word that sounded good and people started using it. The Cardelli-Wegner paper was the first one that I have seen where some analysis was provided into what it means. My post here should be thought of as an elaboration of their position.
> 18 votes

# Answer
The paper Uday Reddy found in his answer, On Understanding Types, Data Abstraction, and Polymorphism (1985), gives the following answers:

> Programming languages in which the type of every expression can be determined by static program analysis are said to be statically typed. Static typing is a useful property, but the requirement that all variables and expressions are bound to a type at compile time is sometimes too restrictive. It may be replaced by the weaker requirement that all expressions are guaranteed to be type consistent although the type itself may be statically unknown; this can be generally done by introducing some run-time type checking. Languages in which all expressions are type consistent are called strongly typed languages. If a language is strongly typed, its compiler can guarantee that the programs it accepts will execute without type errors. In general, we should strive for strong typing and adopt static typing whenever possible. Note that every statically typed language is strongly typed, but the converse is not necessarily true.
> 7 votes

# Answer
Authoritative answers can be found in Cardelli and Wegner's survey article: On Understanding Types, data abstraction and polymorphism.

Mind you that, while "strong typing" has an accepted meaning, "weak typing" doesn't. Any failure of strong typing might be considered weak and people might differ on what kind of failure is acceptable and what isn't.
> 6 votes

---
Tags: reference-request, programming-languages, type-theory
---


# Question
Title: Time complexity of a triple nested loop with squared indices
I have seen this function in past year exam paper.

```
public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

```

After give some example, I guess it is a function that with time complexity in following formula

***let make m = n^(1/2)***

***\[m+(m-1)+(m-2)+...+3+2+1\] + \[(m-1)+(m-2)+...+3+2+1\] + ...... + (3+2+1) + (2+1) + 1***

\*Edit: I have asked this math question here, the answer is **m(m+1)(m+2)/6**

Is this correct, if no, what is wrong, if yes, how would you translate to big O notation. The question that I want to ask is not **only** about this specific example; but also how would you evaluate an algorithm, let's say, I can only give some example to watch the pattern it appears. But some algorithm are not that easy to evaluate, what is your way to evaluate using this example.

**Edit: @LuchianGrigore @AleksG**

```
public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

```

This is an example that in my lecture notes, each loop is with time complexity of **n** to the power of **1/2**, for each loop there is another n^(1/2) inside, the total are n^(1/2) * n^(1/2) * n^(1/2) = n^(3/2). Is the first example the same? It is less than the second example, right?

**Edit,Add:**

How about this one? Is it **log(n)\*n^(1/2)\*log(n^2)**

```
for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)

```

# Answer
For one of the loops, you've a complexity of $O(\sqrt n)$. You're nesting the loops three times, so you'll get the complexity of $O(\sqrt n^3)$, which is $O(n^{3/2})$.

If you want to be more precise, then for your original question, the complexity will be:

1. $O(\sqrt n)$ for the first loop
2. $O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of `1` is constant.
3. $O(\sqrt n - 2)$ for the third loop, which is the same as $O(\sqrt n)$, since the time complexity of `2` is constant.

Therefore, the total complexity is still $O(\sqrt n^3) = O(n^{3/2})$.

**EDIT/ADD:**

You're pretty much correct, just make one more step to simplify the expression, remembering that $\log(n^2) = 2 \times \log(n)$. There are three loops:

1. The first on is, correctly, $O(\log n)$.
2. The second one is just like in the first problem, so you get $O(\sqrt n)$.
3. The third one is on the square of $n$, therefore you get $O(\log(n^2))$, which is the same as $O(2\log(n))$, which is the same as $O(\log(n))$.

Combining the three, it's pretty much like a multiplication, you will get: $O(\log(n) \times \sqrt n \times \log(n))$, which is $O(\log(n)^2 \times \sqrt n)$.
> 5 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Can joins be parallelized?

text:
# Question
Title: Can joins be parallelized?
Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

EDIT: to bring some clarifications from the comments into this post:

* We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each set
* If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?

# Answer
$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.
> 1 votes

---
Tags: complexity-theory, time-complexity, parallel-computing, database-theory, descriptive-complexity
---


# Question
Title: Are tamper attacks considered side-channel?
Wikipedia defines *side-channel attacks* as:

> any attack based on information gained from the physical implementation of a cryptosystem

Usually in side channel attacks the implementations leak information (e.g., timing attack: the implementation leaks the time it takes to complete a task, etc.)

**Are tampering-attacks also considered as side-channel attacks?**

On one hand, tampering-attacks are (usually) attacks on the implementation itself. On the other hand, the attack might be such that information only enters the device, and no information comes out of the device, so there is no "side-channel" that leaks the information. (example: If we heat some access-control device, until it grants us the access. Or if we perform SQL injection that causes the device to grant the access (but leaks no secret other than that))

# Answer
A tampering attack can be considered as an *active* side-channel attack, which is one that involves (physically) interacting with the device under attack. In contrast, *passive* attacks involve only measurement and observation.

Generally, however, I think tampering attacks are considered as a separate class as the countermeasures against them are quite different than for other side-channel attacks.
> 3 votes

---
Tags: terminology, cryptography
---


# Question
Title: Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$
I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)\*log(n)\*log(n).

```
public void run(int n) {
    for (int i = 1; i < n; i *= 2) {
        for (int j = 1; j < n; j *= 2) {
            for (int k = 1; k < n; k *= 2) {
                System.out.println("hi");
            }
        }
    }
}

```

I have come with this solution, but it seems not correct. Please help me out.

# Answer
> 6 votes
Your program is correct. Your could also iterate `Math.Log(n)*Math.Log(n)*Math.Log(n)` times. Not sure if that is considered cheating.

# Answer
> 4 votes
The following trivially is in the complexity class $O(\log^3 n)$:

```
public void run (int n) {
    return;
}

```

But here is a solution with average and worst case of $O(\log^3 n)$:

```
// O(log(n)), n = |orderedVals|
int findClosest (int needle, int[] orderedVals) {
    // binary search for closest value and return it
}

// O(log(n)^3), n = |orderedVals|
int weirdSum (int initialNeedle, int[] orderedVals) {
    int sum = 0;
    int needle1 = initialNeedle;
    int needle2 = findClosest(needle1, vals);
    for (int i = 0; i < needle2; ++i) {
        int needle3 = findClosest(needle2, vals);
        for (int j = 0; i < needle3; ++j) {
            sum += findClosest(needle2, vals);
        }
    }
    return sum;
}

```

---
Tags: time-complexity
---


title: How to prove 2-EXP != EXP

text:
# Question
Title: How to prove 2-EXP != EXP
I am guessing that this is correct for `3-EXP`, `4-EXP` etc...

Basically I should find a problem in `2-EXP` that is not in `EXP`. Any examples ?

# Answer
It is a direct consequence of the time hierarchy theorem:

**Time Hierarchy Theorem**: if f and g are time-constructible functions and $f(n) \log f(n) = o(g(n))$ (e.g. $f(n) = n^2, g(n) = n^3$), then $DTIME(f(n)) \subsetneq DTIME(g(n))$
> 13 votes

---
Tags: complexity-theory
---


title: Must Neural Networks always converge?

text:
# Question
Title: Must Neural Networks always converge?
## Introduction

**Step One**

I wrote a standard backpropegating neural network, and to test it, I decided to have it map XOR.

It is a 2-2-1 network (with tanh activation function)

```
X1  M1
        O1
X2  M2

B1  B2

```

For testing purposes, I manually set up the top middle neuron (M1) to be an AND gate and the lower neuron (M2) to be an OR gate (both output 1 if true and -1 if false).

Now, I also manually set up the connection M1-O1 to be -.5, M2-O1 to be 1, and B2 to be -.75

So if M1 = 1 and M2 = 1, the sum is (-0.5 +1 -0.75 = -.25) tanh(0.25) = -0.24

if M1 = -1 and M2 = 1, the sum is ((-0.5)\*(-1) +1 -0.75 = .75) tanh(0.75) = 0.63

if M1 = -1 and M2 = -1, the sum is ((-0.5)\*(-1) -1 -0.75 = -1.25) tanh(1.25) = -0.8

This is a relatively good result for a "first iteration".

**Step Two**

I then proceeded to modify these weights a bit, and then train them using error propagation algorithm (based on gradient descent). In this stage, I leave the weights between the input and middle neurons intact, and just modify the weights between the middle (and bias) and output.

For testing, I set the weights to be and .5 .4 .3 (respectively for M1, M2 and bias)

Here, however, I start having issues.

---

## My Question

I set my learning rate to .2 and let the program iterate through training data (A B A^B) for 10000 iterations or more.

*Most* of the time, the weights converge to a good result. However, at times, those weights converge to (say) 1.5, 5.7, and .9 which results in a +1 output (even) to an input of {1, 1} (when the result should be a -1).

Is it possible for a relatively simple ANN which has a solution to not converge at all or is there a bug in my implementation?

# Answer
> 13 votes
(I assume by "error propagation" you mean what I call "error *back*-propagation.")

On page 231 of Neural Networks (by Haykin), he states that back propagation always converges, although the rate can be (in his words) "excruciatingly slow."

I think what you are asking though is not whether the algorithm will always converge, but whether it will always converge *to the optimal answer.* And unfortunately, it won't. Even in simple cases like yours, it's entirely possible that there are local minima which are not global minima.

Dealing with local extrema is a hugely important topic in optimization, and you can find a plethora of advice on how to deal with it. One of the most common is what it sounds like you're doing: random restarts (i.e. just run the algorithm multiple times, each starting from a random place).

To figure out if there's a bug in your code, I would print out the error term and verify that it decreases at each iteration. If so, then you're probably just hitting a local minima.

# Answer
> 6 votes
If you have fixed the weights between the input and hidden units and are only modifying the hidden to output weights during training then there will be no local minima. With fixed input to hidden weights the optimization problem you are solving is similar to logistic regression but with a tanh instead of sigmoid function. Regardless the problem is convex and there should be only one, global minima.

Since local minima are not causing your problem I would recommend numerically approximating your derivatives and then comparing these to the values you're computing. If you're unsure how to do this the Standford ULFDL tutorial has a nice overview.

---
Tags: machine-learning, neural-networks
---


# Question
Title: A concrete example about string w and string x used in the proof of Rice's Theorem
So, in lectures about Rice's Theorem, reduction is usually used to proved the theorem. Reduction usually consists a construction of $M'$, using a TM $M$ which is in the form $\langle M,w \rangle$ to be simulated first, an input $x$ to be simulated if $M$ accepts. $M'$ accepts if x is accepted.

I really want a concrete input about $\langle M,w \rangle$ and $x$. For example:

> $L = \\{ \langle M\rangle \mid L(M) = \\{\text{ stackoverflow }\\}\\}$, that is L contains all Turing machines whose languages contain one string: "stackoverflow". $L$ is undecidable.

What kind of $\langle M,w \rangle$ to be simulated?

Suppose we have input x = "stackoverflow" or x = "this is stackoverflow" or any x with "stackoverflow" in it.

What if we first simulate a TM $M$ selected from in the possibilities of all TMs, and this TM accepts only a single character $a$ as its language. So, we simulate this $\langle M,w \rangle$ with $w = a$, and surely it will be accepted. And then input $x$ is also accepted according to the definition of $L$.

So, we conclude that $\langle M,w \rangle$ in which language is a single $a$ is reducible to $L$ that accepts all TMs which have "stackoverflow"?

**Edit:** I've just looked up a brief definition of reduction. A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Given that definition, I think the correct TM $M$ with its description $\langle M,w \rangle$ in my example should be a TM such that it accepts regular languages. This is the harder problem. If this is solvable, then my trivial $L$ with one string is solvable. But apparently, it's not according to the proof. We can effectively say we reduced from language one string problem to regular language problem and try to solve it. Previously, I thought the other way around: $\langle M,w \rangle$ is reduced to one string problem.

Is my thinking correct?

# Answer
> 3 votes
> A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Your characterisation of reduction is a bit misleading. You don't start with an "easy" problem and reduce it to a "harder" problem (how can you know it's an easy problem if it's unknown? Often you're attempting the reduction to *find out* whether your problem is "easy").

A reduction is a computable transformation from one problem to another. It proves that the source problem is **no harder** (in some sense) than the target problem.

Sometimes we do this because we already know the source problem is impossible to solve; this proves that the target problem is impossible too. Since the source problem is "no harder" than the target problem, and we already know the source is undecidable, the target problem must be undecidable (or the source would in fact be harder). More intuitively, if we can reduce the source to the target and the source is undecidable, then the target must be undecidable or we could use the reduction and the solution to the target in order to solve the source (which we already know can't be done).

Other times we find a reduction because we know the *target* problem **is** decidable. This shows that the source problem is decidable too.

So you can use a reduction argument either *to* a problem that's already known to be decidable, or *from* a problem that's already known to be undecidable, depending on what you're trying to prove.

---

So, Rice's Theorum. I don't quite understand the questions you're asking, since I haven't seen the particular statement of the proof that's giving you trouble. Instead, here's my quickie explanation of how to prove Rice's Theorum, which I'm pretty sure is similar.

Suppose we have an arbitrary language $L$, consisting of (encodings of) exactly those TMs with some non-trivial semantic property $P$.\[1\] To prove that there is no algorithm for deciding language $L$, I will reduce the Halting Problem to the decision problem for $L$.

So the Halting Problem (or the particular variant of it I will use here) is: given $\langle M, x\rangle$, an encoding of a Turing machine $M$ and an input $x$, does $M$ halt on $x$?

My reduction must transform the input to the Halting Problem $\langle M, x \rangle$ into the input for the hypothetical decider for $L$, which I will call $ML$. $L$ is a language of Turing machines, so $ML$'s input looks like $\langle M \rangle$.

So my reduction will take $\langle M, x \rangle$ and compute $\langle M' \rangle$. $M'$ is a machine that takes an input $w$ and functions as follows:

1. Simulate $M$ on $x$, ignoring the result
2. Simulate $MP$ on $w$; accept if it accepts and reject if it rejects

Here $MP$ is a machine that whose encoding is in $L$ i.e. it has the property $P$. Since we're considering a non-trivial property $P$, such an $MP$ is guaranteed to exist.

Note that $x$ is *part of* the machine $M'$ the reduction has produced, while $w$ is the *input to that machine* whenever it is run. $x$ and $w$ are completely unrelated. We are assuming we've been given a particular $x$ as part of the input to the Halting Problem, but since we haven't proposed running $M'$, there is no specific $w$ at the moment.

Now, if $M$ halts on input $x$, then $M'$ always gets to stage 2 and thus accepts/rejects exactly the same strings as $MP$. Since the property $P$ is semantic, it doesn't depend on the particular TM, only on the language it accepts, so in this case $M'$ also has property $P$. If $M$ *doesn't* halt on input $x$, then $M'$ *never* gets to an accept state regardless of input, so its language is the empty language.

So now we *don't* want to run $M'$ on anything, since it might not even halt, but we could run our hypothetical $ML$ on it to check whether it's in $L$. This will *almost* tell us whether $M$ halts on $x$; the only thing we're missing is that the empty language might happen to have property $P$, in which case $ML$ will always accept $M'$ whether or not $M$ halts on $x$. But we can easily amend $M'$: if $P$ is true of the empty language (which our reduction could check using $ML$ if $ML$ could actually exist), then we use $MN$ instead of $MP$ - some machine that *doesn't* have property $P$ (which is also guaranteed to exist by the non-triviality of $P$) - and then our $M'$ has property $P$ if-and-only-if $M$ doesn't halt on $x$.

So now we've shown that a hypothetical decider for $L$, the language of machines with property $P$, could be used to decide the Halting Problem. Since we already know the Halting Problem can't be decided, $ML$ can't exist. Since the only thing I assumed about $P$ was that it was a *semantic* and *non-trivial* property, the proof holds for *any* semantic and non-trivial property.

I cheated a little in my reduction, since I had to use $ML$ to work out whether the empty language has property $P$, which means the reduction is only computable if $ML$ exists. This breaks my earlier definition of a reduction as "a computable transformation from one problem to another", but the proof by contradiction is still perfectly valid; proving a language undecidable by reduction from an undecidable language is really just a special case of a proof by contradiction anyway.

---

\[1\] A property of a TM is *semantic* if all TMs that accept the same language share the property, i.e. the property doesn't depend on the particular implementation of the TM but only on the language it accepts. A property is *non-trivial* if there is at least one TM that has the property and at least one TM that doesn't have the property.

# Answer
> 2 votes
Your "proof sketch" contains almost no information; you need to note the special reduction partner. Usually, the halting problem is reduced to deciding the given, arbitrary non-trivial encoding set $L$. If $L$ was decidable, so would be HP but we know HP is undecidable; therefore $L$ is undecidable. So there is no concrete $\langle M,w \rangle$ that "breaks" decidability; we need to deal with *any* $\langle M,w \rangle$ (as HP does¹).

In your edit, you commit a common fallacy: $L = \\{\text{ stackoverflow }\\}$ *is* a regular language and thus decidable. However, Rice's Theorem deals not with $L$ but with

$\qquad \displaystyle L' = \\{ \langle M \rangle \mid \mathcal{L}(M) = L \\}$,

a very different beast. In particular, $L'$ is infinite. The "harder"

$\qquad \displaystyle L'' = \\{ \langle M \rangle \mid \mathcal{L}(M) \in \mathrm{REG} \\}$

is not decidable, either, so there is no paradoxon here.

---

1. That is for the general halting problem; often a version restricted to the diagonal, i.e. $\\{ \langle M, \langle M \rangle \rangle \mid M \text{ Turing machine }\\}$, is used.

# Answer
> 1 votes
Finally I found my answer in this video about reduction which gives a clear explanation for my struggle.

This video and this are about the regular expression example to demonstrate reduction.

But that doesn't mean the other answers are not helpful. They helped me to clear my misconceptions, so thanks for that.

To summarize, I didn't quite understand about the reduction written in the lecture notes or listening to my lecture, since in all the lecture notes, we construct a big TM S which takes `< M,w >` as input, and later reduce it to machine M' which accepts input x. I didn't get the part where `< M,w >` is the input, and suddenly x becomes the input and being "entered by a user".

In the lecture video, Professor Shai Simonson does not use the notation w and x. Instead, he use only x. This is well demonstrated in the regular expression example in video 4 (or 5, I am busy now but I will verify later). Instead of solving whether x is in a regular set or not, we solve whether x is ***not*** in the regular set. In other words, if x is not in regular set, it's in context free language. So we reduce from the regular language problem to a context free language problem. The same input x is used.

I guess the notion w is meant to be the string to be accepted by the original problem and x is the new problem. This is just a logical classification in our mind. In the practice, there should be one input.

---
Tags: computability
---


# Question
Title: Semi-decidable problems with linear bound
Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we’d know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?

# Answer
> 7 votes
For your sketched decision algorithm to work, it is sufficient that the run-time is *majorized* by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)

# Answer
> 3 votes
No, you cannot bound it. Assume you have a characterization of your bound, in terms of a function. That can be a polynomial, exponential, linear etc. We will denote that function by $f(n)$. Since we work on a deterministic setting, we can define an appropriate class $DTIME(f(n))$. Here note that we get a bound on the number of steps which will be a natural number whereas the bound might be not. We can get past such technicalities as @Jan Johannsen describes in his post. What is important is that **all** deterministic classes are closed under complement, thus all problems in them are decidable. Thus, so will be the semi-decidable problem under consideration, a contradiction.

---
Tags: computability, time-complexity, undecidability
---


# Question
Title: What is the type theory judgement symbol?
In type theory judgements are often presented with the following syntax:

My question is what is that symbol in the middle called? All the papers I've found seem to use an image rather than a unicode character so I can't look it up. I've also not found any type-theory reference which says what that symbol is (they explain what it means however).

So what character is that symbol and what is its proper name?

# Answer
> 4 votes
It's called a "turnstile". See the Wikipedia article.

# Answer
> 4 votes
### Detexify

Draw the character on Detexify to see what (La)TeX command generates it.

Oddly, I can't get Detexify to recognize this character. `\vdash` comes up eventually, but with a very bad score no matter how well I try to draw it.

### Shapecatcher

Draw the character on Shapecatcher to see what it is in Unicode. It's U+22A2 RIGHT TACK (⊢).

The usual name in math is turnstile. In this context, it's sometimes called the inference symbol or the deduction symbol. The $\Gamma$ on the left is a *context* or *environment*.

---
Tags: logic, terminology, type-theory
---


# Question
Title: Does a collision oracle for the pigeonhole subset sum problem produce solutions?
I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11):

> Let $\ l(n) = (1-c)n \ $ for $ \ c \> 0 \ $ ...
>
> Given $a\_1, a\_2, \cdots, a\_n \in \\{0,1\\}^{l(n)}$ and a target sum $T$, we construct an input to the collision finding algorithm as follows:
>
> 1. Let the collision finding algorithm select a (non-empty) $ s\_1 \in \\{0,1\\}^n $
> 2. compute $T' = \sum\_{i \in s\_1} a\_i$. Choose a random $j$ such that $j \in s\_1$ and define $a\_j' = a\_j - T' + T$.
> 3. Give the instance $a\_1, a\_2, \cdots , a\_j', \cdots, a\_n$ and $s\_1$ to the algorithm that finds collisions. The algorithm attempts to find $s\_2$ such that $f\_{(a\_1, a\_2, \cdots, a\_j', \cdots, a\_n)}(s\_2) = T'$.
>
> If the algorithm returns $s\_2$ that collides with $s\_1$ and $j \notin s\_2$, then **$s\_2$ is a solution to our original problem**, since swapping $a\_j$ and $a\_j'$ does not affect the sum over $s\_2$.

Where the emphasis is mine.

Where $f$ concatenates $\stackrel{\rightarrow}{a}$ with the sum of the $a\_i$'s:

$$ f( \stackrel{\rightarrow}{ a } , S) = f\_{(a\_1, a\_2, \cdots, a\_n)}(S) = \ \stackrel{\rightarrow}{a}, \sum\_{i \in S} a\_i \mod 2^{l(n)} $$

(taken from the top of page 3 from the same paper).

For the life of me, I don't understand how $s\_2$ is a solution to the original instance. Can someone elaborate on what they mean? What am I missing?

The above definition for the subset sum problem is, if I'm not mistaken, just another form of the pigeonhole subset sum problem (i.e. $\sum\_j a\_j \< 2^n -1$ ). If I read the above right, they are claiming that, given an oracle that finds collisions, they can then construct a solution to the original (pigeonhole) subset sum problem but I do not see how this is done. Any help would be appreciated.

# Answer
The way I understand it is the following.

Note that for $s\_1$, $f\_\vec{a'}(s\_1)=T$ (because the sum was $T'$ and we replaced $a\_j$ with $a'\_j$ and we know that $j\in s\_1$.

Now, they search for a collision, i.e., another $s\_2$ such that $j\notin s\_2$, but $f\_\vec{a'}(s\_2)=T$. (is there a typo there, having $T'$ instead?) Now, what is $f\_\vec{a}(s\_2)$? also $T$, right? since $j\notin s\_2$...

Does it help?
> 1 votes

---
Tags: complexity-theory, computability, np-complete, reductions
---


# Question
Title: Finding the number of distinct permutations of length N with n different symbols
I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.

For example if the string is of length ten as $w = aabbbaabba$, the total number of permutations will be

$\qquad \displaystyle \frac{|w|}{|w|\_a! \cdot |w|\_b!} = \frac{10!}{5!\cdot 5!}$

Now had the string been of distinct characters, say $w'=abcdefghij$, I would have found the permutations by this algorithm :

```
for i = 1 to |w|
  w = rotate(w)
w = rotate(w)
return w.head + rotate(w.tail)

```

Can some one throw new ideas on this - how to find the number of permutations for a string having repeated characters? Is there any other mathematical/scientific name of for what I am trying to do?

# Answer
The total number of (different) permutations of strings with $n\_i$ characters of type $i$ is given by $$\frac{(\sum\_i n\_i)!}{\prod\_i n\_i!}.$$ In other words, if the length of the string is $n=n\_1 + n\_2 +...$, you have $\frac{n!}{n\_1!n\_2!n\_3!\ldots}$ different permutations. Note that the formula fits your simple case.

Why is this formula correct?

Because $n!$ is the number of permutations. But some permutations give the same string (e.g., `aa` rotated is still `aa`). Then we need to "remove" all the permutations that give the same string. For a given string, for each letter $i$, there are $n\_i$ permutations that are identical to the string we started with. So (for each possible letter $i$) we divide by this number to get the final result.
> 6 votes

# Answer
Do you know the urn problem? You usually consider two kinds of marbles (i.e. $n=2$), which gives rise to the binomial coefficient $\binom{N}{k}$ as the number of sequences of length $N$ with $k$ marbles of one kind (and $N-k$ of the other), if you draw with replacement.

You do the same with $n$ kinds of marbles. There is a natural extension to the binomial coefficient, namely the multinomial coefficient $\binom{N}{k\_1\ \dots\ k\_n}$ as the number of sequences of length $N$ with $k\_1$ marbles of kind one, ...

---

If you want to understand why those are correct, I suggest you start with the binomial coefficient; the multinomial coefficient works similarly.

We have

$\qquad \displaystyle \binom{N}{k} = \frac{N!}{k!\cdot (N-k)!}$

by definition. $N!$ is the number of *all* permutations of $N$ marbles, that is if they are all distinguishable. Now we have $k$ black marbles (and $N-k$ white marbles), we can not distinguish. So we have to count all permutations that put the white black (and white) marbles in the exact same spots as one. We count every such permutation $k! \cdot (N-k)!$ times -- to see this, number the marbles, fix a distribution of black and white marbles and calculate the number of ways you can place the numbers -- so we have to divide by this number.

---

If your problem is to compute the multinomial coefficient, you can reduce this to computing the binomial coefficient, e.g. by

$\qquad \displaystyle \binom{n}{k} = \prod\_{i=1}^k \frac{n-(k-i)}{i}$,

with this formula:

$\qquad \displaystyle \binom{N}{k\_1\ \dots\ k\_n} = \prod\_{i=1}^m \binom{\sum\_{j=1}^i k\_j}{k\_i}$.
> 1 votes

---
Tags: algorithms, combinatorics, strings, word-combinatorics
---


# Question
Title: How to feel intuitively that a language is regular
Given a language $ L= \\{a^n b^n c^n\\}$, how can I say directly, without looking at production rules, that this language is not regular?

I could use pumping lemma but some guys are saying just looking at the grammar that this is not regular one. How is it possible?

# Answer
The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then that language is probably not regular.

Of course, you should always remember that mathematical intuition can be wrong, and the only way to be sure of your intuition is to prove it.

EDIT: I'll answer the last question in the comments here, because of lack of space.

> you guys are talking about unbounded memory which you mean is the reason why it is not regular. but a^nb^m can also have unbounded memory if i want, doesnot it? this is still giving me no peace.

The issue is not how big the words can get (you will usually encounter infinite regular languages, because every finite language is regular, and that's pretty boring) but how much the DFA needs to remember.
In the $a^mb^n$ example, there is no need to remember $m,n$. The algorihm just needs to make sure they are positive and that the word is correctly ordered. This is a finite list, and each of the items on the list requires a constant amount of memory.
Compare this to $a^nb^n$, for which a simple alogrithm is required to remember that the number of $a$'s is equal to the number of $b$'s. This will require unbounded memory. When I look at a language and see that any algorithm I can think of needs unbounded memory, my intuition that the language is not regular grows stronger. If I can't find a "smart" algorithm (one that requires a constant amount of memory) in a reasonable amount of time (how much time is reasonable is up to you) I will try proving the language is not regular.
Hope this makes it a bit clearer.
> 12 votes

# Answer
> I could use pumping lemma

Exactly. After you have used the Pumping lemma or any of the other techniques a couple (of dozens) of times, you will start *seeing* the patterns in languages that prohibit them from being regular. $a^n\dots b^n$ is a very basic one you probably have mastered already. So this is also a matter of experience, not only intuition.

A good way to test your intuition is looking at these languages:

1. $\quad \displaystyle \\{xyyz \mid x,y,z \in \\{a,b\\}^+\\}$
2. $\quad \displaystyle \\{xyyz \mid x,y,z \in \\{a,b\\}^\*\\}$
3. $\quad \displaystyle \\{xyyz \mid x,y,z \in \\{a,b,c\\}^+\\}$
4. $\quad \displaystyle \\{xyyz \mid x,y,z \in \\{a,b,c\\}^\*\\}$

Which are context-free?
> 6 votes

# Answer
You can actually decide if a language is regular using fairly straightforward calculations, rather than doing a full proof. You simply need to apply one very powerful criterion: A language is regular if and only if it has finitely many quotients.

Intuitively, a quotient is what you need to complete a word after having already read in part of the input. More formally, the left quotient of a language $L$ by a string $x$, written $x\setminus L$ is the set of strings $w$ such that $xw \in L$. For example, if $L=\\{a^nb^n\\}$, then $a\setminus L= \\{a^{n-1} b^n | n\ge 1 \\}$, while $b \setminus L=\emptyset$. We can easily see that $a^k \setminus L = \\{a^{n-k}b^n | n \ge k \\}$. There are infinitely many quotients of the form, so it follows immediately that $L$ is not regular.

If we construct a DFA $D$ to decide L, and $D$ will be in state $S$ after reading in $a$, then $a\setminus L$ is the language decided by $D$ modified to have start state $S$. This same idea can be used to directly construct the minimal DFA that decides a regular language from its definition.
> 4 votes

---
Tags: formal-languages, regular-languages, pumping-lemma, intuition
---


title: If any 3 points are collinear

text:
# Question
Title: If any 3 points are collinear
> Given a set $S$ of points $p\_1,..,p\_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear.

The problem is I started with general definition but I cannot continue to actually solving the problem.

What can we say about collinear points in general, 3 points $a,b,c$ are collinear if the distance $d(a,c) = d(a,b)+d(b,c)$ in the case when $b$ is between $a$ and $c$.

The naive approach has $O(n(n-1)(n-2))=O(n^3)$ time complexity.

How to solve this problem, what should be the next step?

# Answer
> 8 votes
One simple way is to fix a point $x$, compute the slope of the line $xy$ and store it in a hash table for every other point $y$. If there is a collision, then we have collinear points involving $x$. This takes $O(n)$ (if we assume hash table operations take $O(1)$). We then do this for every point $x$ in time $O(n^2)$.

Also if you are aware of the point-line duality (please refer to Artium's comment below), this reduces to checking the $n^2$ possible intersections of $n$ lines, but also makes use of hash tables.

Also it is open whether this can be done in sub-quadratic time as this problem is 3-SUM hard, please refer to this answer.

---
Tags: algorithms, computational-geometry
---


title: Improve Markov Chain results

text:
# Question
Title: Improve Markov Chain results
Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results.

The chain starts at State x, a uniform distribution of set S = {1,2,3,...30}. If the current state is page P, select page Q uniformly from the union of the results from each search engine. If the rank of Q \< rank of P in 2 of the 3 engines that rank both P and Q, move to Q. Else, remain at P.

This results in a number of pairwise comparisons being carried out. result2 is compared with result1 and a count is made of each time result2 ranks better than 1. The results are sorted by the results of the pairwise comparisons, with the lowest score ranked first. e.g.

```
Engine Rankings:                       Pairwise Comparison:
         eng1   eng2   eng3                    result1  result2  result3  result4  result5
result1   1      2      2              result1    0        1        0        0        1
result2   4      3      1              result2    2        0        1        2        2
result3   2      4      5              result3    3        2        0        1        2
result4   5      5      3              result4    3        1        2        0        1
result5   3      1      4              result5    2        1        1        2        0

```

The problem with this example is, if we add the total of each row in the pairwise comparison, we get {2,7,8,7,7}, leaving 3 different results with the same score. I'm wondering if there is a method to further sort these results in order to refine the results so that I'm not left with a number of results that have the same score? I've seen Keminization but I can't see how this would apply? Can someone please give me some guidance?

# Answer
> 1 votes
Let $\mathcal{S}$ be the state space of your Markov chain, and assume that we start at some state $i \in \mathcal{S}$. Let $\mathcal{Y}\_i$ be the set of states (pages) that are ranked lower than $i$ by two of the three engines. According to your description, the probability of transition to state $j$ can be defined as follows:

\begin{equation} P\_{ij} = \begin{cases} 1 - \frac{|\mathcal{Y}\_i|}{|\mathcal{S}|} & \text{if } j = i, \\ \frac{1}{|\mathcal{S}|} & \text{if } j \in \mathcal{Y}\_i, \\ 0 & \text{Otherwise} \end{cases} \end{equation}

If I have understood your question correctly, this Markov chain does not always produce credible results due to the following issues. First, your chain allows repetitive comparisons. In other words, it is likely that a state $i$ is compared against some state $j$ multiple times. This, of course, does not make trouble as long as your chain is irreducible. However, in some cases, you will not get the correct result. For example, consider the following scenario.

Imagine for some state $i \in \mathcal{S}$, no state (page) can be found that is ranked lower than $i$ by two other engines, that is $\mathcal{Y}\_i = \varnothing$. Therefore, $P\_{ii} = 1$ making $i$ an absorbing state. In this case, your chain will be trapped in state $i$ in finite time, and from then on, it will only compare state $i$ against other states repeatedly. If chain is trapped in such a state and you let it run for a long enough time, then your results would clearly be wrong. Similar problem occurs if your chain contains recurrent sub-classes.

Assuming that no such states exist, then you would have an irreducible chain. In that case, if you let the chain run for **sufficiently long time**, the counting process would result in a good approximation of *correct* rankings (according to your algorithm).

P.S. This answer is just based on my understanding of your problem and may not be 100% correct.

---
Tags: algorithms, machine-learning, markov-chains
---


# Question
Title: Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?
I've been given the following problem:

Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:

* $\text{Insert}(x)$ – add $x$ to $S$
* $\text{Extract\_min}()$ – remove the minimal element in $S$ and return it

We can implement with a heap the above methods in $O(\log n)$, however, we're looking at a bigger picture, a general case that we have no guarantee that $M$ is indeed a heap. Prove that no matter what kind of data structure $M$ is, that **at least one** of the methods that $M$ supports must take $\Omega(\log n )$.

**My solution:**

Each sorting algorithm that is based on comparisons must take at the worst case at least $\Omega(n\log n)$ – we'll prove that using a decision tree: if we look at any given algorithm that is based on comparisons, as a binary tree where each vertex is a *compare-method* between 2 elements:

* if the first is bigger than the second element – we'll go to the left child
* if the second is bigger than the first element – we'll go to the right child

At the end, we'll have $n!$ leaves that are the options for sorting the elements.

The height of the tree is $h$, then:

$$2^h \ge n! \quad\Longrightarrow\quad \log(2^h) \>= \log(n!) \quad\Longrightarrow\quad h \ge \log(n!) \quad\Longrightarrow\quad h = \Omega(n \log n)$$

Then, if we have a $\Omega(n \log n)$ worst case for $n$ elements, then we have a $\Omega(\log n)$ for a single element.

I'm not sure regarding this solution, so I'd appreciate for corrections or anything else you can come up with.

# Answer
> 13 votes
I don't think your proof is valid, because it only considers trees, and a certain type of trees at that. If there were an algorithm with a smaller lower bound for what you describe, we'd have a sorting algorithm faster than $\Omega(n \log n)$ no matter which of the two operations is $\log n$. So the problem reduces to proving that sorting cannot be faster than $\Omega(n \log n)$, which is a classical proof that you can find online.

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


title: Why is Turing completeness right?

text:
# Question
Title: Why is Turing completeness right?
I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is *one machine* which, if programmed appropriately, can perform *any possible computation*.

Of course, calculating machines of one kind or another go back to antiquity. People have built machines which for performing addition and subtraction (e.g., an abacus), multiplication and division (e.g., the slide rule), and more domain-specific machines such as calculators for the positions of the planets.

The striking thing about a computer is that it can perform *any* computation. Any computation at all. And all without having to rewire the machine. Today everybody takes this idea for granted, but if you stop and think about it, it's kind of amazing that such a device is possible.

I have two actual *questions*:

1. When did mankind figure out that such a machine was possible? Has there ever been any serious *doubt* about whether it can be done? When was this settled? (In particular, was it settled before or after the first actual implementation?)
2. How did mathematicians *prove* that a Turing-complete machine really can compute everything?

That second one is fiddly. Every formalism seems to have some things that *cannot* be computed. Currently "computable function" is *defined as* "anything a Turing-machine can compute". But how do we know there isn't some slightly more powerful machine that can compute more stuff? How do we know that Turing-machines are the correct abstraction?

# Answer
Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the *Entscheidungsproblem*.

Although Church's paper was published slightly earlier, Turing was unaware of it when he developed his ideas, and Turing's approach proved to be more useful for the design of real-world machines. This was because he showed how to design a Universal Turing Machine that could be programmed to run any computation. This universal machine, with a concrete architecture based on the work of John von Neumann is the basic idea behind the machine on which you are reading my answer.

As you noted, computable is defined as "computable on a Turing machine" and all other reasonable models of computation have proven to be equivalent in their power. The belief that all reasonable models of computation are equivalent in what decision problems they can solve is known as the Church-Turing thesis. In its original form, it is almost completely believed by the learned community. In fact it is not completely clear what it would mean to prove/disprove the Church-Turing thesis; in a lot of ways it becomes an empirical question.

However, there is still the extended Church-Turing thesis which asks the slightly more subtle question of: what can be computed *efficiently*?. Many *classical* models, such as $\lambda$-calculus, Turing Machines, tag-based systems, cellular automata, etc are equivalent under the extended thesis as well. However, the recent development of quantum computing casts doubt on the extended thesis. Although most people who work on quantum computers (including me) believe they are more efficient that classical ones, the matter is subject to scholarly debate. Note that in terms of the coarse notion of what is computable (as opposed to *efficiently* computable) quantum computing is still equivalent to Turing's model.
> 18 votes

# Answer
There's a reason it's called a Turing Machine, and it's because it was invented by Alan Turing. He did a 1936 paper on it, establishing these concepts. If you want to know more about Turing Machines, check the paper. It was seriously doubted, before he designed and built one that cracked the Enigma, that this concept could actually work. However the British were pretty desperate and he was a genius, so they trusted him and it paid off massively.

However, when you think about it some more, it's really not that amazing at all. It was known long before Turing that all of mathematics could be reduced to some set of axioms. All you would have to do is give the instruction set the ability to perform these axioms, and off you go.
> -2 votes

---
Tags: computability, turing-machines, history
---


# Question
Title: What are the minimum requirements for a language to be considered Turing Complete?
> **Possible Duplicate:**
> Are there minimum criteria for a programming language being Turing complete?

I overheard a conversation on the topic and the conclusion that one gent came to was that in order to be Turing complete, given one has infinite storage, all one needs is a conditional control structure and a jump instruction.

Is this true?

If it is true, and Turing completeness requires that the language that is Turing complete be able to simulate every instruction available in another Turing complete language, how do those two simple elements achieve that?

# Answer
The machine you describe would be turing complete with the addition of an assignment operator (you need this to take advantage of memory), and at least one comparison operator (which could be folded into the jump, like a jump-if-(not)-zero). (Note that an increment operator is necessary - either as a primitive, or appropriate representations need to be available such that one can roll ones own).

However, there are many turing-complete models of computation with completely different primitive operations, such as lambda calculus, or petri nets.
> 4 votes

# Answer
The more abstract answer which captures the requirements on both imperative-style programming (suitable for hardware register machines) and functional-style programming (suitable for dataflow and graph reduction machines) is that your language must be able to

1. represent bit strings of arbitrary lengths
2. express a partial recursive function (to simplify, a partial recursive function is a computation where the number of steps in a repetition may not be known before an arbitrary number of iterations have been run already)

Theoretical Turing machines have #1 by means of the tape, and #2 by means of the states and conditional state transitions. Pure Lambda calculus has #1 by means of lambda-terms of arbitrary lengths, and #2 by means of partial evaluation of fixed point combinators and the truth functions.

In general, if your execution platform "looks like" a Turing machine in that it has a memory for strings and instructions for state transitions, it intuitively satisfies #1 so that does not need discussion. The main question that remains is how to deal with partial recursive functions. A conditional branch and a stack pointer are a way to do it, but other ways are possible as well.
> 2 votes

# Answer
Yep, it's true. I can describe Turing machine made of endless paper, alphabet and instructions, but in Russian language only, so I can only give you this link to Wiki page about Turing machine - complete language you are talking about.
> 1 votes

---
Tags: computability, programming-languages, turing-completeness
---