# Question
Title: Search in a partial ordering defined by tuples of numbers
This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a cost. Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.

An example of such a situation could be these 5 edges:

(I did not draw the time axis on scale)

There are five edges, I, II, III, IV and V. The costs are denoted at the edges, they are either 100, 10 or 1. Edge V is drawn red to easily discriminate it from the other edges, since it crosses through them. However, aside from that it is not different.

Given such edges, a few things are important:

* An edge is only interesting if it departs after we arrive at A, for example in the image we can arrive at (a), then edge I is not an option anymore. The same goes for edges II and V if we arrive at (b), etc.
* Given an arrival and its set of interesting edges, and edge ei is dominated if there exists an edge ej with ej\< ei. This is the case iff aj ≤ ai ^ cj ≤ ci ^ (aj \< ai v cj \< ci). In layman terms, cost and arrival need to be at least as small, but one must be strictly smaller. This is a partial ordering, some edges are incomparable.
* **Given a arrival in A, I want to find all relevant, undominated (or Pareto) edges.**

We can enumerate all the edges:

* I: (0 , 1, 100)
* II: (0.5, 2, 10)
* III: (2 , 3, 100)
* IV: (2.5, 4, 10)
* V: (1.5, 5, 1)

Putting them in a partial ordering, using a directed acyclic graph (dag), we get this:

An arrow denotes the \<-relation between edges. Note that an edge in this case is a node in the dag: confusing, I know. **When I say edge, I mean a node in the dag above.**

I added an edge (-∞, -∞), which is always irrelevant, but creates a nice 'root' of the dag. This way we sort of have a tree, where leaves sometimes merge without creating cycles. I also only denote the arrival at B and cost, needed to create the dag, but technically there is also a departure are A for each of the edges.

If we were to arrive at A at -1, we can simply return all the children of (-∞, -∞) as relevant and undominated, but for another arrival we may need to traverse the tree differently (in a more complicated fashion). I was thinking of this:

```
marker := map from edge to bool # marks whether edge has been traversed
for all edges: marker(edge) := false # none have been traversed

traverse(root, arrival):
    if(marker(root)) return []  #already been at this node
    marker(root) := true;
    if(departure(root) > arrival) return [root]; # return singleton list, all children will be dominated by this edge.

    # this node is irrelevant, but possible some children are relevant.
    l = [];
    for each child of root:
        append traverse(child, arrival) to l
    return l

```

Traverse returns a list of undominated, relevant edges. However, Is this an efficient way to tackle this problem? Is there a better solution to this problem? Is this problem known under a known name?

# Answer
> 0 votes
I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

```
global: visited, front

function proceed(arrival)
    visited := array of bool for each node initialized to false
    for each x ∈ front
        proceed(arrival, x)
    return front

function proceed(arrival, node):
    if(visited[node]): return
    visited[node] := true
    if(node.departure > arrival):
       remove node from front
       for each node x:
           append x to the end of front

function calculate_outgoing:
    outgoing := array of lists for each arrival at A, each list contains feasible and relevant A->B connections for that arrival.
    front   := [(-∞, -∞)]
    for each arrival at A in increasing order:
        outgoing[arrival] := proceed(arrival)
    return outgoing

```

Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.

# Answer
> -1 votes
This is the problem of enumerating all minimal elements of a partial order. Your edge dominance relation defines the partial order.

---

## A warmup

In the simple case where you arrive at time $-1$, the partial order consists of all of the "edges", and you're just looking to enumerate all minimal elements in this partial order.

If you don't care about running time, this can be done by computing the dag that corresponds to this partial order and then pulling out all sources (all nodes in the dag with in-degree 0). Note that every partial order corresponds to a dag (the relation $x\<y$ in the partial order corresponds to an edge from $x$ to $y$ in the dag), and so you can construct the dag using your partial order. The downside is that the running time to construct a dag in a naive fashion will be $O(n^2)$, if you test all pairs of edges for dominance.

In your case, there is a much more efficient algorithm. Each edge corresponds to a pair $(a,c)$, with the arrival time and the cost. Imagine plotting these on (the upper-right quadrant of) the 2-D plane. Now we want the subset of points that don't have any point below-and-to-the-left of them.

This subset can be computed in $O(n \lg n)$ time. First sort the points by arrival time, i.e., by $a$-value. Now iterate through the points, in increasing order of arrival time. As you iterate, keep track of the smallest cost (smallest $c$-value) you've seen so far. When you see a point that has a smaller cost than any previously seen, add it to the subset: it is a minimal point (it is not dominated by any other point).

In this way, you can find all of the minimal elements of your partial order in $O(n \lg n)$ time, where $n$ denotes the number of edges in your original problem.

## The general case

We can adopt the above methods to the more general case where you arrive at time $t$. Now the partial order consists of all edges that apart after time $t$.

It's easy to construct this partial order with an initial filtering pass: simply throw away all of the edges that depart before time $t$. This can be done in a simple $O(n)$ time linear scan of all of the edges.

Next, you want to final all the minimal elements in this partial order. This can be done in $O(n \lg n)$ time, using the method described above. So, this solves your problem of finding all of the Pareto-minimal (undominated) edges, efficiently.

## References

You might like to read the following articles about lattices and partial orders and their role in computer science:

---
Tags: graphs, graph-traversal, partial-order
---


# Question
Title: Longest Path A*, Admissible Heuristics, and Optimalness
Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path.

I have some number of classes, each with a list of unique nodes, with each node having its own value. Im attempting to determine the best possible combination of a node from each class to determine the combination or path that has the greatest weight. To do this, I am viewing these classes as a tree, with each Level having the nodes contained within a single class.

Then I search through this tree using A Star, or more specifically, im searching through my tree based on a search stack. Once a node is explored, its children are inserted in a sorted order based on their weight (plus their ancestors weight) plus the possible future weight (my heuristic). Then the top of the stack, with the highest value is selected to search next.

To do this I have an overestimating heuristic, that is it never underestimates the the optimal solution.

If I am looking for the highest weight and not the lowest weight, is this heuristic admissible, and thus my algorithm optimal?

PS: A FormalIsh defination of the current algorithm.

Let S = {S1, S2, ... , Sn}

and each Si has a set of items and a NULL, which represents an item not chosen from this set.

Si = {I1, I2, ... , Im, NULL}

Also each item only ever exists in one set, IE Si U Sj = Si \+ Sj

Each Item, Ii has an associated value, Vi.

The problem is to select a maximum of M offers, one from each set, when summed yield the highest value. I call this selection a Path, Pi. A path can be complete, meaning it has a selection from all S, or it can be partial where only x offers are contained within it. Also M

In addition, there exists a function IsCompatable(path) that returns true if a path is compatible. Whether a path is compatible or is completely arbitrary. The Max valued path must be compatible. This is why I can not trivially select the M largest Items from each set.

In addition each set contains a NULL item, so that an item need not be selected from that set.

The Trivial Algorithm would to make a search tree and generate all possible combinations of items in S, with each path to the trees leaves said to be a path.

let G(P) be the current value (the summed value of each item) of the partial path. Let H(P) be an estimation (heuristic) of the value of the future path. H(P) = The Y values from Y items from Y Si in S. Each item is the item with the maximum value in the Si where i \> len(P). Y = M - the current length of the partial path P.

To Find the path with the greatest value, I keep a sorted Queue of partial paths, sorted on their values + their possible future values, ie G(Pi) + H(Pi). I Initialize this Queue by adding paths contained in S1.

```
While the Queue is not empty or a path has not been found:
    p = Pop the path from the top of Q
    if p is Complete:
        A full path has been found
        return p
    find the possible children of p by adding an item to p from the next set.
    for child in Children:
        if IsCompatable(child):
            add child back to Q in sorted order on G(child) + H(child)

```

There it is, now is my Heuristic admissible?

# Answer
> 3 votes
It seems to me (and correct me if I'm wrong) that a regular A\* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're searching for the shortest path we want a heuristic that will never lead us down a path that will be longer than what we estimate it to be, in your case you never want to be led down a path that will be less than what you estimate it to be (which you say you have).

A heuristic is a function that gives $h(n) = 0$ at the goal.

An admissible heuristic is one that never overestimates the distance to the goal. In your cause you want the longest path rather than the shortest, so an admissible heuristic never underestimates the distance to the goal.

So if you have a heuristic that gives you at least the correct distance from the current node to the goal node or a larger value and you order your queue by largest $f(n)$ then you have a correct implementation of A\*.

On the other hand if your heuristic both may underestimate or overestimate you're aren't guaranteed to find an optimal path.

We can prove the optimality of this easily (this is an adapted proof from Russell and Norvig's Artificial Intelligence A Modern Approach).

Let $G$ be an optimal goal state, with path cost $f^\*$. Let $G\_2$ be a suboptimal goal state with path cost $g(G\_2) \< f^\*$. Now assume that A\* has selected $G\_2$ from the queue. Because $G\_2$ is a goal state it would terminate the search with a suboptimal solution.

Consider a node $n$ that is a leaf node on an optimal path to $G$. Because $h$ is admissible (never underestimates), we must have

$f^\* \leq f(n)$

And if $n$ was not chosen over $G\_2$ then

$f(n) \leq f(G\_2)$

Combining these we get

$f^\* \leq f(G\_2)$

Because $G\_2$ is a goal state $h(G\_2) = 0$ thus $f(G\_2) = g(G\_2)$. So we have a contradiction that $f^\*$ is an optimal longest path and that $G\_2$ is suboptimal. Thus A\* will never expand a suboptimal solution and is an optimal algorithm.

---
Tags: algorithms, search-algorithms, heuristics
---


# Question
Title: Find an MST in a graph with edge weights from {1,2}
I've been asked the following question:

> Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \\{1,2\\}$, suggest an **efficient** algorithm that finds an MST of the graph.

After a few clarifications, the algorithm should run in time $O(|V|+|E|)$. I believe we can do this because of the fact that there are two types of weight of edges.

I tried the following idea, which did not work (I had a contradicting example):

> Run BFS on the graph, and output the BFS tree.

I thought that shortest paths in this case would also mean easiest trees, but this is not the case.

I also tried to make each edge $e$ such that $w(e)=2$ into two edges of weight $1$ but my friend also gave a contradicting example.

Can you help please? This is not a homework question, this is a previous exam question as I am studying for my algorithms exam which is soon.

# Answer
> 4 votes
Since you have only 2 possible edge weights you can perform a linear time sort on the edges, then perform Kruskal's algorithm. The complexity of Kruskal's algorithm comes from its need to sort the edges in terms of weight, which previously had to be done in $O(ElogE)$ time, now however, you can sort the edges in linear time and then perform Kruskal's to complete the search. Creating the vertex set is $O(|V|)$ time, sort in $O(|E|)$ ,build MST in $O(|E|)$ total time is $O(|E|+ |V|)$

# Answer
> 6 votes
Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices that have a connection of weight 1 (because they have priority to those of weight 2). I would say that a single list can handle this.

I also think that there might be another approach. Start building spanning trees for the components when we only use edges of weight 1, just ignoring edges of weight 2. Then the components are "big vertices" that can be connected by a tree using the remaining edges of weight 2. Keeping components here is easy: all vertices reached in a new component are labelled with the same number. That number identifies the "big vertex".

---
Tags: algorithms, spanning-trees
---


# Question
Title: Detecting coplanarity by given pairwise distances
Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that we're not given the coordinates of the points in V. We may not even be given all pairwise distances, so the graph need not be complete, and it may even be sparse.

Suppose we're given $k$ and told that there are $k$ planes such that all the vertices belong to at least one of those plane. We want to find $k$ such planes, with an added restriction:

In order to determine whether 4 points are coplanar given only their pairwise distances, the most straightforward method is to use the Cayley-Menger determinant. For our problem, this would require the graph to be fairly dense, since we'd need to know most of the pairwise distances to apply Cayley-Menger. The restriction is to find $k$ planes *without* using the Cayley-Menger determinant.

If this is impossible, can we obtain a proof that states this is impossible? In other words, can we prove that for any such graph $G$ and given $k$, if we have enough information to find $k$ planes for $G$ by *some* means, then we have enough information to *use Cayley-Menger* to find $k$ planes?

# Answer
> 3 votes
I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K\_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

**Random Greedy**

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the *expected* running time is, but I would wild-guess it at $O(n \\, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

**Prioritized Greedy**

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.

# Answer
> 3 votes
RANSAC would be one candidate method to find planes that cover a large fraction of the points.

Suppose that a large fraction of the points go through some plane $P$, say, $n/10$ of them. Here's how we can find it:

So let's pick 4 points at random from the $n$; call those points $q,r,s,t$. Suppose we know the distances between all such pairs (they form a 4-clique, $K\_4$). Then we can use the Cayley-Menger determinant to see if they are co-planar. Suppose they are co-planar. Then we might try testing each other point $x$ and seeing whether we can tell whether it is co-planar with the plane formed by $q,r,s,t$. We might only be able to test this when the additional point $u$ forms a 4-clique together with some other points known to be on the plane. At the end, if we've found a significant number of points that are on the plane formed by $q,r,s,t$, we keep this plane. Keep doing this for, say, 1000 random choices of $q,r,s,t$.

How well will this work? Well, suppose we model the graph as a random graph where each possible edge appears with probability $p$ (so we expect $pn(n-1)/2$ edges on average). Then the probability that a randomly chosen set of 4 points form a 4-clique in the graph is $p^6$. Therefore, if we sample at least $10^4/p^6$ choices of $q,r,s,t$, we expect to find at least one where they reveal the plane $P$. Also, the probability that an additional point $u$ forms a 4-clique with at least three of $p,q,r$ is $p^3$, so when we do find four points $q,r,s,t$ on the plane $P$, we expect to find at least $p^3 n/10$ of the points on the plane $P$. (Actually, we'll probably find a lot more than that. Once we have those $p^3 n/10$ points, now the probability that an additional point $v$ forms a 4-clique with at least three of them is $1-(1-p^3)^{p^3 n/10} \approx 1-\exp\\{-p^6 n/10\\}$, which is significantly larger than $p^3$.) In other words, once we find points $q,r,s,t$ on the plane $P$, it is likely that we will keep this plane.

So as long as you sample enough 4-combinations of points, and as long as your graph is dense enough, this procedure is likely to detect all planes that cover a large fraction of points.

# Answer
> 3 votes
Unfortunately, the answer is that this is an NP-Complete problem. Using only 4 planes of points, you can encode satisfiability problems into whether or not there is a point set that generates a sparse set of distances.

That means you can create problems where determining if a fifth plane is necessary or not requires solving 3-SAT problems. You can combine two such problems, where exactly one requires the fifth plane, to keep the number of planes constant and force the algorithm to solve 3-SAT problems even if it knows $k$ ahead of time.

So the problem has no worst case polynomial time solution, unless P = NP.

# Answer
> -1 votes
am attempting an answer even though the question may be somewhat unclearly stated. half of it says the points are given, the other half says that pairwise distances are given. am going to assume that point coordinates are given for this answer. there is a close connection between computing determinant and matrix rank. there is a generalization as follows. create the matrix of 3d vectors, they can be either column or row vectors. compute the rank. if it is 2, the points are coplanar. the pairwise distances can be computed from the coordinates and is not necessary to calculate/ determine matrix rank.

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


# Question
Title: What is the signal going from the computer to the screen?
Im sorry if it is a weird question, but I cant seem to find an answer for this. What does the signal going to the screen look like in more abstract sense? Does it code the values of each pixel in a huge matrix, is it a computational stream that instructs the screen what to present?

In other words, can I grab this signal by a "listening" device for example and deconstruct it with algorithms? Not just grab the signal and present it on another screen. For example, if it is a matrix of pixel values, then I can run face recognition algorithms for example, to see if the signal sent to the computer is a picture of face or not.

It might also depend on the type of screen? Say that it is a LCD screen.

edit: To elaborate, if I wanted to take the signal sent to the screen and scan it for text (NSA style), could I? If so, what should I know of the signal that Im collecting to actually do this? Disclaimer: Im not interested in spying on anyone.

# Answer
> 3 votes
The memory you are asking about really exists and is called *framebuffer*. However, it's not easy to directly access this memory on modern computers, because it's *intentionally* hidden from user processes.

For more info - click here.

---
Tags: computer-architecture, signal-processing
---


# Question
Title: Recovering a point embedding from a graph with edges weighted by point distance
Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.

Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d\_{0,1} = d\_{0,2} = d\_{0,3} = d\_{1,2} = d\_{1,3} = d\_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.

In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p\_0$ to be at $(0,0,0)$, then pick a neighboring point $p\_1$ and place it at $(d\_{0,1},0,0)$, then a common neighbor $p\_2$ gets triangulated onto the XY plane, then a final common neighbor $p\_3$ gets triangulated into the half-space $z \> 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.

On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.

Which raises the questions:

* How expensive is it to find a solution?
* How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
* What sorts of conditions make the problem trivial?
* If I don't promise the edge weights actually correspond to point distances in 3d, how expensive is it to determine if an embedding is possible at all?

# Answer
**The problem is NP-Complete**. The positions of the points is a good certificate, so it's in NP, and you can encode circuits into the "is there a satisfying set of points?" problem.

**Reduction from Circuit Evaluation to Distance Embedding**

We're going to reduce circuit evaluation into a distance embedding problem by creating a coordinate system, putting logical bits in it, wiring bits to be equal, and creating widgets for NOT and AND gates.

1. **Coordinates**. We need some kind of coordinate system that we can position points with. Do this by creating a "base" tetrahedron of points. Add four points all declared to be a distance of $1$ from each other. This forces the shape of those four points into a tetrahedron. We can position other points relative to our tetrahedron coordinate system by specifying their distance to each of the four corners of the base. The tetrahedron can be translated and rotated and reflected, but the same thing will happen to all the other points as well.
2. **Bits**. To make a bit, we position a triangle of points relative to the base tetrahedron. The triangle's normal must point upward along the Z axis, so that the triangle is parallel to the XY plane (in tetrahedron coordinates). Also its edges must have length $1$. With that done, we add a "value" point $v$, specified to be a distance of $1$ from the other three. We *don't* connect $v$ to the base coordinate system. This gives it two possible positions: centered $\frac{1}{\sqrt{3}}$ above or below the triangle, as the final corner of a tetrahedron. The bit is ON if the point is above the triangle, and OFF if it's below.
3. **Wires**. We can force two bits to be equal by saying the distance between their value points is equal to the distance between the centers of their triangles. There is one exception: when the top or bottom corner of one of the bits exactly lines up with the center plane of the other. In that case we first use a wire to move one of the bits vertically.
4. **NOT**. We can get the negation of a bit by adding a second value point $w$ to the same triangle, but requiring that $w$ be a distance of $\frac{2}{\sqrt{3}}$ from $v$. This forces $w$ to take the position opposite of $v$, with respect to the triangle, giving us a bit with the opposite value.
5. **IMPLIES**. The equidistant issue we had to work around with the wires is actually quite useful. When the bits line up in that way, which we can force with a vertical wire, the higher one implies the lower one. If the higher one is true, only the top of the lower one is the right distance away. If the higher one is false, both the top and bottom are the right distance away.
6. **AND**. To make a bit $C$ be equal to $A$ AND $B$, we need two implications and a widget to force equality when $A$ and $B$ agree. The implications are just $C \implies A$ and $C \implies B$. To make the widget we move $A$ and $B$ vertically so they're on the same level and a distance $\frac{2}{\sqrt 3}$ apart, then we move $C$ to be equidistant between them. We then add a points $S\_A$ and $S\_B$ a distance $\frac{\sqrt 2 - 1}{2 \sqrt 3}$ from $A$ and $B$'s value points respectively, and force the distance between $S\_A$ and $S\_B$ to be $\frac{\sqrt 2 + 1}{\sqrt 3}$. We also add a point $S\_C$ a distance $\frac{\sqrt 2 + 1}{2 \sqrt 3}$ from both $S\_A$ and $S\_B$. This creates a chain between $A$ and $B$'s value points, with $S\_C$ at the chain's center. When $A \neq B$, the chain is stretched to the limit and $S\_C$ is in the center of $C$'s triangle. When $A = B$ the chains links are forced to go in exact opposite directions, *pushing* it to the limit and placing $S\_C$ on $C$'s value point equal to $A$. To force $C$'s value point, we insert a point $S\_D$ a distance $\frac{1}{2 \sqrt 3}$ from both $S\_C$ and $C$'s value point. This doesn't constrain $C$'s value point when $A \neq B$, but forces $A=B=C$ when $A=B$.

With those elements, you can encode any circuit into a distance embedding. The inputs become bits, gates get decomposed into NOTs and ANDs introducing new bits as necessary, and that's it. Force the position of the output to be true, and you get your satisfiability problem.
> 5 votes

# Answer
One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape.

Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d\_{v,w}$, then the spring is chosen so it ideally wants to be of length $d\_{v,w}$ (it can be longer or shorter, but this costs energy). We now want to solve for a set of positions that minimize the total energy. Suppose each vertex $v$ is placed at point $x\_v \in \mathbb{R}^3$. Then the total energy of this arrangement will be

$$E(x) = \sum\_{(v,w) \in E} (\text{distance}(x\_v,x\_w) - d\_{v,w})^2.$$

Here the $d\_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x\_v$'s (they are the coordinates of the points).

We can solve for an arrangement $x$ that minimizes this total energy. This arrangement then provides a reasonable candidate for the positions of the points. This is an optimization problem, and there are standard techniques for solving this kind of optimization problem. See, e.g., the article Network Solutions by Erica Klarreich.

I don't think there any guarantee this will provide the correct desired solution. It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for. However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.

---

Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances. Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.

---

Finally, there's a lot of work on embedding graphs into $\ell\_2$ space, while minimizing the distortion of the embedding. That's very related; you are basically asking for a zero-distortion embedding into $\ell\_2$. Thus, the techniques developed in that context might be useful for your problem, too. Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem. However, it's possible that their techniques might be effective in your situation as well. It's worth a try.
> 5 votes

# Answer
Partial answer on *uniqueness*: 3-connectedness is *not* sufficient.

Minimal counter example: cube graph ($Q\_3$ of the Hypercube Graph family)

To see how fixing the length of all edges in $Q\_3$ does not give positions to vertices in 3-d space that is unique up to translation/rotation/mirroring, look at how **you can flatten a cardboard box (with 2 opposing faces removed)**.

Take the corners of cardboard box to be the vertices of interest. Each corner of a cardboard box have fixed distance from other corners which it shares a box's face with.

While the resulting graph has even more edges than $Q\_3$, it still allows the cardboard box to be flatten down --- a transformation which can not be produced by translation/rotation/mirroring.
> 4 votes

# Answer
this is known as the following problem and occurs eg with reconstructing coordinates from sensor networks that can measure distance to nearby nodes, & this paper can serve as a mini-survey along with leading algorithm(s). a leading method is known as Singular Value Projection, another Singular Value Threshholding. the algorithms are generally based on matrix algebra & rank reduction. the paper implements both algorithms and gives some empirical analysis.

Euclidean Distance Reconstruction from Partial Distance Information Xu, Chen
> 3 votes

---
Tags: complexity-theory, graphs, computational-geometry, euclidean-distance
---


title: Calculate winding number

text:
# Question
Title: Calculate winding number
How can one calculate the winding number of a polygon given as a list of vertices in some (counter-clockwise or clockwise) order?

The complexity of the algorithm must be linear time.

# Answer
> 4 votes
The winding number $w$ of a polygon has to be calculated around a certain point $P$. Since your question is ambiguous, I'll suppose you've already determined $P$.

Given a list of n vertices $v\_0, v\_1, ... v\_{n-1},v\_0$ (notice $v\_n = v\_0$) given in counter-clockwise order, a simple linear way to calculate the winding number is $$ w = \frac {1}{2\pi}\sum\_{i=0}^{n-1} \theta\_{v\_i,v\_{i+1}}$$ where $\theta\_{v\_i,v\_{i+1}}$ is the angle between $\vec{v\_iP}$ and $\vec{v\_{i+1}P}$, which you can obtain using dot product and arcosines.

Your second solution consists of casting a ray $R$ from $P$. The winding number of your polygon can then be calculated as the number of edges $E\_+$ that cross $R$ going counter clockwise, minus the number of edges $E\_-$ that cross $R$ going clockwise.

I.e.: $w = E\_+ - E\_-$

If you want further insight (and proof) on how to determine $E\_+$ and $E\_-$, I highly suggest you research the "point in polygon" problem and the "crossing number" often associated with that problem.

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


# Question
Title: Call‑by‑name will succeeds where call‑by‑value may fails: some example cases?
I've landed to SML pages, comparing call‑by‑name and call‑by‑value, asserting the former always succeed while the latter may fails. As this seems counter intuitive to me, I feel at least an example case would be useful.

Call-by-value, call-by-name and call-by-need

> Theorem (Church Rosser 1)
>
> For a purely functional language, if call-by-value evaluation and call-by-name evaluation both yield a well-defined result then they yield the same result.
>
> Theorem (Church Rosser 2)
>
> If a well-defined result exists for an expression then **the call-by-name evaluation strategy will find it where, in some cases, call-by-value evaluation will not**.

What make it counter‑intuitive to me, is that call‑by‑name may re‑evaluate expressions multiple times, which I don't understand how it can make it succeed when call‑by‑value and its one‑time evaluation, would fails. If, as the context is FP and its referential transparency, both expression are supposed to evaluated to the same, how evaluating multiple time may make something succeed or alternatively potentially fails if the same expression is evaluated only once? Unless there are side‑effect somewhere?… is this related to side effects and non‑pure FP?

As a reminder, here is what would look like call‑by‑value and call‑by‑name with SML (if there is an error here, feel free to tell), added call‑by‑need to help not confuse one with the others:

```
(* This, is supposed to sometime fails… *)

fun call_by_value a =
   a + a  (* `a` is evaluated only once *)

(* …when this is supposed to succeed *)

fun call_by_name a =
   a () + a ()  (* `a` is evaluated for each of its reference *)

(* None of the above should be confused with call‑by‑need: *)

fun call_by_need a =
   let val a' = a ()  (* memoization *)
   in fn () => a' + a'  (* to be evaluated when needed *)
   end

val _ = print (Int.toString (call_by_value 2) ^ "\n")
val _ = print (Int.toString (call_by_name (fn () => 2)) ^ "\n")
val r = call_by_need (fn () => 2) ()  (* memoization *)
val _ = print (Int.toString r ^ "\n")

```

# Answer
Call-by-value evaluates the arguments to a function *exactly once*. Call-by-name evaluates the arguments to a function, *zero*, *once*, or *more* times. Call-by-need evaluates the arguments to a function zero or once, but not more than once.

The trick you are looking for here is a case where call-by-value needs to evaluate an argument once while call-by-name does not need to evaluate its argument at all. The particular thing that Church and Rosser were worried about was that the argument might be an infinite loop.

So if I have the following

```
fun call_by_name (cond a b) =
  if cond
    a
  else
    b

```

and

```
fun loop_forever () =
   loop_forever()

```

Then

```
call_by_name(true, 1, loop_forever())

```

will return 1 while

```
call_by_value(true, 1, loop_forever())

```

will loop forever.

Actually, call-by-name is super cool because it allows you to implement control-flow constructs like `if-then-else` and `while-do`. Suppose, for example that your language doesn't have `if-then-else` built in. You can implement boolean values `True` and `false` and `if-then-else` in call-by-name as follows:

```
fun True  (t f) = t
fun False (t f) = f
fun if_else (cond t f) = cond(t f)

```

Now

```
if_else(True, 1, loop_forever())

```

returns 1 and

```
if_else(False, loop_forever(), 0)

```

returns 0.
> 5 votes

# Answer
This is a bit simpler (in OCaml notation):

```
(fun x => 42) (let rec f x = f x in f ())

```

It loops in call-by-value and returns 42 in call-by-name and call-by-need.
> 3 votes

---
Tags: programming-languages, lambda-calculus, functional-programming, semantics, evaluation-strategies
---


# Question
Title: Combinatory interpretation of lambda calculus
According to Peter Selinger, *The Lambda Calculus is Algebraic* (PDF). Early in this article he says:

> The combinatory interpretation of the lambda calculus is known to be imperfect, because it does not satisfy the $ξ$-rule: under the interpretation, $M = N$ does not imply $\lambda x.M = \lambda x.N$ (Barendregt, 1984).

Questions:

* What kind of equivalence is meant here?
* Given this definition of equivalence, what is a counter-example of the implication?

# Answer
The equivalence is just equivalence in the equational $\lambda$-theory under discussion. In this case, it's the theory outlined in Table 1. Note that this theory does not include $\eta$: doing so would make the theory extensional, and the point is eventually that $\xi$ respects $\lambda$'s intensionality, while it would make CL partially extensional. I am not sure why the other answer mentions $\eta$.

Note that in $\lambda$:

$$(M =\_\beta N) \Longrightarrow (\lambda x.M =\_\beta \lambda x.N) \tag{1}$$

This should be intuitively obvious: if $M$ is $\beta$-convertible to $N$ when it stands by itself, then it is also $\beta$-convertible to $N$ when it is a subterm of $\lambda x.M$.

The $\xi$-rule, defined as \begin{align} M &\\;= N \\ \hline (\lambda x.M) &\\;= (\lambda x.N) \tag{$\xi\_\lambda$} \end{align} makes this inference directly possible when it is part of a $\lambda$-theory. Its CL analogue would be: \begin{align} M &\\;= N \\ \hline (\lambda^\* x.M) &\\;= (\lambda^\* x.N) \tag{$\xi\_{CL}$} \end{align}

Now, the point is that in CL, the following **does not hold**:

$$(M =\_w N) \Longrightarrow (\lambda^\* x.M =\_w \lambda^\*x.N) \tag{2}$$

In other words, if two terms are weakly equal, then this is not *necessarily* true for their pseudo-abstracted versions.

Consequently, if we add $\xi\_{CL}$ to a CL theory, then we start equating terms which have different normal forms.

---

*Note.* Here, $M =\_w N$ denotes weak equality. It means that $M$ can be converted into $N$ (and vice versa) by a series of $\mathsf{S}$ and $\mathsf{K}$ contractions (possibly also $\mathsf{I}$, if it is part of the theory). As you probably know, $=\_w$ is the CL analogue of $=\_\beta$.

$\lambda^\*$ is the pseudo-abstractor as defined on page 5 of your document. It has the following property:

$$(\lambda^\*x.M)N \rhd\_w \[N/x\]M \tag{3}$$

This property makes it easy to find a CL analogue for any $\lambda$-term: just change $\lambda$ to $\lambda^\*$ and apply the translations according to the definition of $\lambda^\*$.

---

To be clear, the 'counter-example' in this answer is not a counter-example to (2). Because if we have:

$$M = x \tag{4}$$ $$N = (\lambda^\*z.z)x \tag{5}$$

Then $N$ really denotes (applying the translations of page 5, and the fact that $\mathsf{I}$ is defined as $\mathsf{SKK}$ at the end of page 4):

$$N = (\lambda^\*z.z)x = \mathsf{I}x = \mathsf{SKK}x \tag{6}$$

Since $\mathsf{SKK}x \rhd\_w \mathsf{K}x(\mathsf{K}x) \rhd\_w x$, we indeed have that $M =\_w N$. However, if it is a counter-example, we should then have that $(\lambda^\* y. M) \not=\_w (\lambda^\* y. N)$. But if we translate, we actually get:

$$(\lambda^\* y. M) = (\lambda^\* y. x) = \mathsf{K}x \tag{7}$$ $$(\lambda^\* y. N) = (\lambda^\* y. \mathsf{SKK}x) = \mathsf{K}(\mathsf{SKK}x)\tag{8}$$

And is easy to verify that (7) and (8) are still weakly equal, for:

$$\mathsf{K}(\mathsf{SKK}x) \rhd\_w \mathsf{K}(\mathsf{K}x(\mathsf{K}x)) \rhd\_w \mathsf{K}x \tag{9}$$

Now, a proper counter-example to (2) would be:

$$M = \mathsf{K}xy$$ $$N = x$$

Since $\mathsf{K}xy \rhd\_w x$, we definitely have that $M =\_w N$. However, if you translate carefully for the abstracted versions, then you will see that both are distinct normal forms - and these cannot be convertible according to the Church-Rosser theorem.

First we check $M'$:

\begin{align} M' &= \lambda^\* x.\mathsf{K}xy \\ &= \mathsf{S}(\lambda^\* x.\mathsf{K}x)(\lambda^\* x.y)\\ &= \mathsf{S}(\lambda^\* x.\mathsf{K}x)(\mathsf{K}y) \\ &= \mathsf{S}(\mathsf{S}(\lambda^\* x.\mathsf{K})(\lambda^\* x.x))(\mathsf{K}y) \\ &= \mathsf{S}(\mathsf{S}(\lambda^\* x.\mathsf{K})(\mathsf{I}))(\mathsf{K}y) \\ &= \mathsf{S}(\mathsf{S}(\lambda^\* x.\mathsf{K})(\mathsf{SKK}))(\mathsf{K}y) \\ &= \mathsf{S}(\mathsf{S}(\mathsf{KK})(\mathsf{SKK}))(\mathsf{K}y) \end{align} Here you can verify that $M'$ is a normal form. Here you can check that $(\lambda^\* x.Kxy)P \rhd\_w P$, as you should expect if $\lambda^\*$ is supposed to behave like an abstractor for CL. (Click the blue links to perform weak contractions.)

Now we check $N'$: \begin{align} N' &= \lambda^\*x.x \\ &= \mathsf{I} \\ &= \mathsf{SKK} \end{align}

Which is obviously a normal form different from $M'$, so $M' \not=\_w N'$ by the Church-Rosser theorem. Note also that $N'P \rhd\_w P$, i.e. $M'$ and $N'$ 'produce the same output' for arbitrary inputs $P$.

We have now proven that (2) does not hold in CL, and that a CL theory incorporating $\xi$ would therefore equate terms that are not weakly equal. **But why do we care?**

Well, first of all, it makes the combinatory interpretation of $\lambda$ imperfect: apparently not all metatheoretic properties carry over.

In addition, and perhaps more importantly, while there exist extensional theories of $\lambda$ and CL, they are originally and commonly kept intensional. Intensionality is a nice property because $\lambda$ and CL model computation as process, and from this perspective two *different* programs (specifically, terms that have a different normal form) that always produce the same results (given equal inputs) are not to be equated. $\xi$ respects this principle in $\lambda$, and if we want to make $\lambda$ extensional, we could just add e.g. $\eta$. But the introduction of $\xi$ in CL would no longer make it completely intensional (in fact, only partially so). And this is the reason for $\xi$'s 'notoriety', as the article puts it.
> 7 votes

# Answer
**EDIT** This answer is incorrect, as the other answerer correctly pointed out. I used the translation into combinatory logic from Asperti & Longo, which is subtly different from the one in Selinger.

In fact, this illustrates a crucial point: "the combinatory interpretation" of lambda calculus is not a single thing! Different authors do it slightly differently.

I'm leaving my answer here for posterity, but the other answer is better.

---

Equivalence in this context is defined by Tables 1 and 2 in Selinger's paper. However, a slightly different axiomatisation may make things a little more clear.

What it really means is that two terms are convertible in the $\lambda$ theory. We can define "convertibility" by the following two axioms:

* $\beta$. $(\lambda x. M) N = \[N/x\]M$, if $x$ free for $N$ in $M$
* $\eta$. $\lambda y. M y = M$, if $y$ not free in $M$

plus, of course, the usual axioms and inference rules needed to make $=$ a congruence. From this, it should be obvious that any counter-example is going to rely on the free variable condition on the $\eta$ rule being broken.

I think this is probably the simplest:

$$M = x$$ $$N = (\lambda z. z) x$$

You can verify for yourself that $\lambda y. M = \lambda y. N$, but their respective combinatorial interpretations are not equal under the rules in Table 2.
> 3 votes

---
Tags: terminology, lambda-calculus, combinatory-logic
---


# Question
Title: Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$
I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo $n$.

I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $\left.\mathbb{Z}\middle/n\mathbb{Z}\right.$ and square it. If $r$ was a square, $r^2$ can have up to $4$ different square roots and the basic idea of the algorithm is that the oracle has some chance not to choose $\pm r$, but one of the other two roots. It will turn out that we then can determine a factor of $n$ using Euclidean's algorithm.

I formalized this to

**Input**: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.

**Output**: $p$ or $q$

1. Take a random number $r$ between $1$ and $n-1$
2. If $r\mid n$ then return $r$ (we were lucky)
3. $s:= r^2\pmod{n}$
4. $t:=\sqrt{s}\pmod{n}$ (using the oracle)
5. If $t\equiv \pm r\pmod{n}$ then goto step 1.
6. Return $\gcd(t-r,n)$

One can show that $t \not\equiv \pm r\pmod{n}$ implies that $\gcd(t-r,n)\neq 1,n$ and therefore get that the return value of the algorithm is a non-trivial factor of $n$.

Inspired by my main question "How do I prove that the running time is polynomial in the bit-size of the input?" I have some follow up questions:

1. Do I have to show that a lot of numbers between $1$ and $n-1$ are squares? There must be a well-known theorem or easy fact that shows this (well... not well-known to me ;-).
2. Are there any more details I have consider?
3. Has every square of a square exactly $4$ square roots modulo $n$?

# Answer
1. Where in the analysis of the algorithm does the number of squares ("quadratic residues") come in? As to their number, you know that $a^2 \pmod{n}$ is always a square, and every number has up to $4$ square roots. That should help you show that there are a lot of squares.
2. Try to prove that your algorithm works, and see if anything is missing.
3. Suppose $n = pq$ ($p,q$ different primes) and $(x,n)=1$. Then if $x$ is a square, then $x$ has two square roots modulo $p$ and two square roots modulo $q$, and so four square roots in total by the Chinese remainder theorem. We know that a number $x$ such that $(x,p)=1$ has at most two square roots since the polynomial $t^2-x$ can have at most two roots modulo $p$. If it has one square root $y$ then $-y$ is another one.
> 4 votes

# Answer
"2." Another detail to consider is that finding square roots modulo a large composite (your step 4) is proved to be as hard a factoring, and produces in any case a factorization of the large composite. See, for example, here for an application of their equivalent difficulty, and here for an explanation of how to factor the large composite if one **can** find square roots modulo the large composite.

So it would seem you have found the algorithm correctly! And since all the steps, like computing (t-r,n), and aside from the magical oracle, are proven polynomial it seems you have constructed a proof as well!
> 0 votes

---
Tags: randomized-algorithms, integers, factoring
---


# Question
Title: Can PRNGs be used to magically compress stuff?
This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange.

Here's a 14 year-old's scheme for an amazing compression algorithm:

Take a PRNG and seed it with seed `s` to get a long sequence of pseudo-random bytes. To transmit that sequence to another party, you need only communicate a description of the PRNG, the appropriate seed and the length of the message. For a long enough sequence, that description would be much shorter then the sequence itself.

Now suppose I could invert the process. Given enough time and computational resources, I could do a brute-force search and find a seed (and PRNG, or in other words: a program) that produces my desired sequence (Let's say an amusing photo of cats being mischievous).

PRNGs repeat after a large enough number of bits have been generated, but compared to "typical" cycles my message is quite short so this dosn't seem like much of a problem.

Voila, an effective (if rube-Goldbergian) way to compress data.

So, assuming:

* The sequence I wish to compress is finite and known in advance.
* I'm not short on cash or time (Just as long as a finite amount of both is required)

I'd like to know:

* Is there a fundamental flaw in the reasoning behind the scheme?
* What's the standard way to analyse these sorts of thought experiments?

*Summary*

It's often the case that good answers make clear not only the answer, but what it is that I was really asking. Thanks for everyone's patience and detailed answers.

Here's my nth attempt at a summary of the answers:

* The PRNG/seed angle doesn't contribute anything, it's no more than a program that produces the desired sequence as output.
* The pigeonhole principle: There are many more messages of length \> k than there are (message generating) programs of length \<= k. So some sequences simply cannot be the output of a program shorter than the message.
* It's worth mentioning that the interpreter of the program (message) is necessarily fixed in advance. And it's design determines the (small) subset of messages which can be generated when a message of length k is received.

At this point the original PRNG idea is already dead, but there's at least one last question to settle:

* Q: Could I get lucky and find that my long (but finite) message just happens to be the output of a program of length \< k bits?

Strictly speaking, it's not a matter of chance since the meaning of every possible message (program) must be known in advance. Either it *is* the meaning of some message of \< k bits *or it isn't*.

If I choose a random message of \>= k bits randomly (why would I?), I would in any case have a vanishing probability of being able to send it using less than k bits, and an almost certainty of not being able to send it at all using less than k bits.

OTOH, if I choose a specific message of \>= k bits from those which are the output of a program of less than k bits (assuming there is such a message), then in effect I'm taking advantage of bits already transmitted to the receiver (the design of the interpreter), which counts as part of the message transferred.

Finally:

Ultimately, both tell us the same thing as the (simpler) pigeonhole principle tells us about how much we can compress: perhaps not at all, perhaps some, but certainly not as much as we fancy (unless we cheat).

# Answer
You've got a brilliant new compression scheme, eh? Alrighty, then...

♫ Let's all play, the entropy game ♫

Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ambiguous what you have compressed).

So, your scheme is to determine some family of PRNG/seeds such that if you want to compress, say, $01000111001$, then you just write some number $k$, which identifies some precomputed (and shared) seed/PRNG combo that generates those bits after $n$ queries. Alright. How many different bit-strings of length $n$ are there? $2^n$ (you have n choices between two items; $0$ and $1$). That means you will have to compute $2^n$ of these combos. No problem. However, you need to write out $k$ in binary for me to read it. How big can $k$ get? Well, it can be as big as $2^n$. How many bits do I need to write out $2^n$? $\log{2^n} = n$.

Oops! Your compression scheme needs messages as long as what you're compressing!

"Haha!", you say, "but that's in the worst case! One of my messages will be mapped to $0$, which needs only $1$ bit to represent! Victory!"

Yes, but your messages have to be unambiguous! How can I tell apart $1$ followed by $0$ from $10$? Since some of your keys are length $n$, all of them must be, or else I can't tell where you've started and stopped.

"Haha!", you say, "but I can just put the length of the string in binary first! That only needs to count to $n$, which can be represented by $\log{n}$ bits! So my $0$ now comes prefixed with only $\log{n}$ bits, I still win!"

Yes, but now those really big numbers are prefixed with $\log{n}$ bits. Your compression scheme has made some of your messages even longer! And *half* of all of your numbers start with $1$, so *half* of your messages are that much longer!

You then proceed to throw out more ideas like a terminating character, gzipping the number, and compressing the length itself, but all of those run into cases where the resultant message is just longer. In fact, for every bit you save on some message, another message will get longer in response. In general, you're just going to be shifting around the "cost" of your messages. Making some shorter will just make others longer. You really can't fit $2^n$ different messages in less space than writing out $2^n$ binary strings of length $n$.

"Haha!", you say, "but I can choose some messages as 'stupid' and make them illegal! Then I don't need to count all the way to $2^n$, because I don't support that many messages!"

You're right, but you haven't really won. You've just shrunk the set of messages you support. If you only supported $a=0000000011010$ and $b=111111110101000$ as the messages you send, then you can definitely just have the code $a\rightarrow 0$, $b\rightarrow 1$, which matches exactly what I've said. Here, $n=1$. The actual length of the messages isn't important, it's how many there are.

"Haha!", you say, "but I can simply determine that those stupid messages are rare! I'll make the rare ones big, and the common ones small! Then I win on average!"

Yep! Congratulations, you've just discovered entropy! If you have $n$ messages, where the $i$th message has probability $p\_i$ of being sent, then you can get your expected message length down to the entropy $H = \sum\_{i=1}^np\_i\log(1/p\_i)$ of this set of messages. That's a kind of weird expression, but all you really need to know is that's it's biggest when all messages are equally likely, and smaller when some are more common than others. In the extreme, if you know basically every message is going to be $a=000111010101$. Then you can use this super efficient code: $a\rightarrow0$, $x\rightarrow1x$ otherwise. Then your expected message length is basically $1$, which is awesome, and that's going to be really close to the entropy $H$. However, $H$ is a lower bound, and you really can't beat it, no matter how hard you try.

Anything that claims to beat entropy is probably not giving enough information to unambiguously retrieve the compressed message, or is just wrong. Entropy is such a powerful concept that we can lower-bound (and sometimes even *upper*-bound) the running time of some algorithms with it, because if they run really fast (or really slow), then they must be doing something that violates entropy.
> 45 votes

# Answer
There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that *whatever your compression algorithm is*, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many applications of Kolmogorov complexity.

In real life, we often know something about the sequence we are compressing, say it's voice or a picture. In the case of lossless compression, Shannon's source coding theorem shows that the optimal compression rate is equal to the entropy of the source. For lossy encoding there are other theorems in information theory (rate-distortion theory). So even in this case there's a limit to how much you can compress data.
> 22 votes

# Answer
Imagine that your seed $s$ has length $k$. Your PRNG is a deterministic function of the seed, so it outputs at most $2^k$ different sequences of length $n$. There are $2^n$ of these, so your scheme isn't going to work unless it falls back on just sending the whole $n$-bit string when there is no corresponding $s$.

(As another answer noted, this will happen for any compression function you choose at all.)
> 7 votes

# Answer
Beside other already answared points, I just want to add this link: https://www.schneier.com:443/blog/archives/2009/09/the\_doghouse\_cr.html

> Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

So only iterating (no comparing...) to find a valid 187bit constellation of your desired data would take under (not attainable) ideal conditions more energy than the sun emits over a year.
> 4 votes

# Answer
A very quick proof that an universal compressor cannot exist. Let´s suppose you do make one, and you compress an input. Now, iteratively compress the output of your program. If you can always reduce the size, it will get smaller and smaller on every step, until you are down to 1 bit.

You could argue that, perhaps, the output of your algorithm has such a structure that it cannot be compressed more, but then you could just apply a deterministic shuffle\* before recompressing.

*Footnote:* Some deterministic shuffling actually helps in some compression schemes: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim
> 1 votes

# Answer
The use of a PRNG for "compression" is basically useful in one situation: when it is necessary to use a "random" bunch of data and compactly record what data was used. Most pseudo-random generators can only generate a tiny fraction of possible sequences, but if one only needs a small-to-moderate number of "random" sequences, the fraction of possible sequences that a PRNG can generate will often be more than adequate.

If the sequence of data that one wishes to store happens coincidentally to match what a certain PRNG would generate given the right seed, storing the seed may be a compact alternative to storing the data. Unless the source of data is such that such matches are likely to occur, however, they would be so infrequent that searching for them would not be worthwhile.
> 1 votes

# Answer
Something to consider to add to the cacophony of answers that assert why there are some strings that cannot be compressed owing to the, by definition, injective nature of decompression, and the limited universe of compressed strings from which to select to represent messages is this: most strings cannot be compressed because there are very many more high entropy, disordered strings than there are lower entropy and structured ones, therefore giving rise to the condition that we see in practice that: compression is most of the time useful, since the messages we most often wish to compress are those most often possessive of some aliquot of order and structure, and by this dint, are part of the very much smaller universe of lower entropy objects. This means it is possible that, by choosing a suitable output length, we can compress everything in the smaller, structured universe. The term structured, entropy and ordered here are deliberately imprecise, to reflect the subjective definitions of the semantics and usefulness of messages we may wish to compress.

And in direct answer to the questioner's request : \*yes, you could of course just get lucky and find the output of your PRNG is the exact message you wish to compress, it's just that you so often won't find this is the case because the very property that characterises a PRNG, namely, its ability to product an (almost) unending variety of different strings, make it concomitantly unlikley to produce yours.

Of course you could mitigate this unlikelihood by using a PRNG to walk over a "domain graph" of word to word transitions, and you increase greatly the likelihood of your message's apparition, and also find you must now add the domain graph to the compressed message length.
> 1 votes

---
Tags: information-theory, randomness, data-compression, pseudo-random-generators, entropy
---


# Question
Title: Lexicographical position of a string in its type class
I have the following problem:

Given a string $x\in\\{1,...,M\\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists of all permutations of $x$. We call this set the type class of $x$.

My question:

> How to compute the position of $x$ in the lexicographical ordering of $S$?

I found the paper "Enumerative source coding" written by Thomas M. Cover, where this position function $i\_{S}$ is shown for binary alphabets (in the following the alphabet is $\\{0,1\\}$):

$i\_S(x\_1x\_2\cdots x\_n)=\sum\limits\_{k=1}^{n}x\_k\cdot$ $n-k\choose n(w,k)$

with $\\;\\;n(w,k)=w-\sum\limits\_{j=1}^{k-1}x\_j\\;\\;\\;$

and $\\;\\;w$ is the number of occurrences of $1$ in $x\\;\\;$ ($w=\sum\limits\_{k=1}^{n}x\_k$).

Unfortunately, i do not know how to extend this formula to alphabets of size $M$. Any help?

# Answer
This is yet another example of enumerative encoding. Suppose that $x$ has $\alpha\_i$ symbols of type $i$. The size of $S$ is then the multinomial coefficient $\binom{n}{\alpha\_1,\ldots,\alpha\_M}$. Pascal's identity reads $$ \binom{n}{\alpha\_1,\ldots,\alpha\_M} = \sum\_{i\colon \alpha\_i \neq 0} \binom{n-1}{\alpha\_1,\ldots,\alpha\_i-1,\ldots,\alpha\_M}. $$ In the lexicographic ordering of $S$, the strings starting with $1$ (if any) constitute the first $\binom{n-1}{\alpha\_1-1,\ldots,\alpha\_M}$ positions, the strings starting with $2$ (if any) constitute the following $\binom{n-1}{\alpha\_1,\alpha\_2-1,\ldots,\alpha\_M}$ positions, and so on. So $x\_1$ already gives you an interval of length $\binom{n-1}{\alpha\_1,\ldots,\alpha\_{x\_1}-1,\ldots,\alpha\_m}$ to which $x$ belongs in the lexicographical ordering of $S$. To find its location within the interval, recurse: examine $x\_2$, then $x\_3$, and so on.

Here is the resulting algorithm, returning a $0$-based position:

1. Set $P \gets 0$.
2. For $i=1,\ldots,n$:
    1. Set $P \gets P + \sum\_{j \< x\_i, \alpha\_j \neq 0} \binom{n-i}{\alpha\_1,\ldots,\alpha\_j-1,\ldots,\alpha\_M}$.
    2. Set $\alpha\_{x\_i} \gets \alpha\_{x\_i} - 1$.
3. Return $P$.
> 3 votes

---
Tags: coding-theory, encoding-scheme, word-combinatorics
---


# Question
Title: Does FACTORING have optimal substructure or analog to it?
Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily solvable instance is encountered, at which point the ancestry of subproblems can be successively reconstructed from the sequence of solved instances to arrive finally at the solution of the original problem.

In terms of original research toward this question I considered the following two possibilities. It is not thought that either of these are to be very workable, and are here to attempt to illustrate the intended meaning of the question, which then asks whether it is likely there are approaches that could be workable that display optimal substructure or analogous structure:

1. The hypothetical, magical FACTOR\_SUCCESSOR function, which when given an integer factorization for X, returns the integer factorization for X+1 in polynomial time in log(X). \[This can be used to construct a factoring algorithm to factor N using the binary (or any other) base representation of N.\] This hypothetical function seems difficult to construct since, for example, see here.
2. An approximation approach. This would make use of the idea that if large (\>500 decimal) N is hard to factor (say a semiprime), then perhaps if N-m is k-smooth, with factors in a multiset F, and then perhaps good approximations to base representation vectors of p and q could be obtained by forming p' and q' from disjoint covering subsets of F. The choice of k determines how expressive F is in being able construct varied factors of about equal size to p and q. It is unclear both if p' and q' would be good approximations to p and q even if they were of similar size and m were small, and even if they were good approximations, the algorithm appears more of a one-shot, and not amenable to iterative betterment of that guess. This is accounting for the idea of 'randomly modifying' parts of the guess p' and q' to then give an m' \< m, with the same k-smooth property, and beginning the search for selections of disjoint covering subsets of F nearby to p' and q'. It is unclear whether m' could be easily found, also if the algorithm would get stuck in a local optima, removed from p and q. Which makes it seem quite unworkable.

Edit: it is incorrect to say optimal substructure is a meaningless term since it has both a generally accepted meaning (in computer science referring to problems by which larger instances are amenable to solution using the solution of smaller instances) and also a derivable meaning in that if one considers the possible meanings of "optimal" and "substructure" put together one arrives at a conclusion that such a concatenation is likely to refer to the state of having a substructure which is in some way optimal. In the context of the solution of problems, the intended meaning naturally follows. Maybe Raphael simply doesn't like the question or the answer or both, because they're so meaningful!

# Answer
> 2 votes
No. There's no known optimal substructure like that. Such a substructure would naturally lead to algorithms for factoring large composite numbers, which is a notoriously hard problem. For numbers that are products of two primes, there is no known optimal substructure; these are the kinds of numbers that are used in the RSA cryptosystem, and factoring them has been studied in great depth in the literature. However, the best factoring algorithms known don't use optimal substructure; instead, they use other number-theoretic ideas.

Another way to put it: recursion does not seem like a useful approach to factoring products of two primes efficiently. The natural way to recurse is to find a divisor $d$ of $n$, then recurse on $d$ and $n/d$; but that's a chicken-and-egg problem, because finding a divisor of $n$ is exactly the problem that's hard. For instance, when $n$ is a product of two primes, factoring *is* the problem of finding a (non-trivial) divisor of $n$. So, the problem is that, to figure out what to recurse on, you first need to solve the problem itself. My thanks to @Raphael for this helpful way of thinking about things.

---
Tags: optimization, dynamic-programming, factoring
---


# Question
Title: Meaning of type inference rule for abstraction in lambda-calculus
Below is a snippet about simply typed lambda-calculus from CS152: Programming Languages Lecture 9 | Simply Typed Lambda Calculus, on printed‑page 15, indexed 23.

$$ \frac {\Gamma, x: \tau\_1 \vdash e: \tau\_2}{\Gamma \vdash \lambda x. e: \tau\_1 \rightarrow \tau\_2} $$

I read it as: if from a context $\Gamma$ containing $x$ of type $\tau\_1$, follows that an expression $e$ is of type $\tau\_2$, then from context $\Gamma$, follows that $\lambda x. e$ is of type $\tau\_1 \rightarrow \tau\_2$.

How does that differs from this:

$$ \frac {\Gamma \vdash x: \tau\_1 \land \Gamma \vdash e: \tau\_2}{\Gamma \vdash \lambda x. e : \tau\_1 \rightarrow \tau\_2} $$

I understand $x$ is expected to typically appears in $e$ (but need not to), however still not see why the second expression (looking more intuitive to me) is not used instead, and so I suspect I may be not really understanding the notation in the first expression.

Is this the same or is this different? If it is not the same, what's the precise meaning of the former and what's the (different) meaning (if it has one) of the latter? Is the former just a way to underline $x$ may be contained in $e$ (i.e., more matter of style than formal meaning)?

# Answer
The problem is that whatever the context $\Gamma$ may imply about the variable $x$ is irrelevant. This rule is intended to type a $\lambda$-abstraction, and the variable $x$ may be changed to another variable by $\alpha$-conversion, without changing the semantics of the $\lambda$-abstraction, and thus without changing its type.

By writing $\Gamma, x: \tau\_1$, we are considering a context $\Gamma$ where the variable $x$ has type $\tau\_1$, ignoring what the type of $x$ may have been in context $\Gamma$ alone. If $x$ could be assigned a type in the context $\Gamma$ alone, it would refer to some homonymous variable that is irrelevant to the abstraction, since its scope is shadowed in the abstraction by the local variable $x$. Indeed, an $\alpha$-conversion would make $x$ disappear from $e$ altogether.

In other words: $\Gamma \vdash x: \tau\_1$ may or may not be true, but it is simply irrelevant to typing the abstraction.

Then, it is possible that $\Gamma \vdash e: \tau\_2$. But that is only possible if the type of $x$ is irrelevant, for example when $x$ does not actually occurs in $e$, as for the abstarction $\lambda x.42$, Then $e=42$ which is indeed typable. But in general, you cannot type $e$ without having a type for $x$ (for the variable $x$ of the abstraction).

In other words, you expect the type of $e$ to be in general related to the type of $x$, and it is their relation that the rule is intended to express.

What the rule says is that, if by adding to the context $\Gamma$ that the *new* variable $x$ has type $\tau\_1$, you can infer then that $e$ has type $\tau\_2$ in this new environment, then the abstraction $\lambda x. e$ has type $\tau\_1 \rightarrow \tau\_2$ in the original environment $\Gamma$.

It says that the type of $e$ is dependent on the type $x$ may have.

Then, wherever the abstraction is applied to another expression $e'$, the type of the application is whathever the type of $e$ should be when the type of $x$ is that of $e'$. But that is another typing rule.
> 5 votes

---
Tags: lambda-calculus, semantics, typing, type-inference, type-checking
---


# Question
Title: Does programming language detection need more input than natural language detection?
I wonder which one of the two needs a larger input to achieve a decent accuracy:
programming language detection or natural language detection?

---

More details:

Definition of Language detection:

> In natural language processing, language identification or language guessing is the problem of determining which natural language given content is in. Computational approaches to this problem view it as a special case of text categorization, solved with various statistical methods.

The question I was asking can be written bit more formally as: let $x$ be a substring from some text $X$ written in natural language, and $y$ a substring from some source code $Y$ written a programming language. Assume a $X$ and $Y$ are each written in one language only (natural language or programming language).

Let $f(X)$ be the size of $x$ so that on average (i.e. trying on a bunch of different X) I correctly predict the language with accuracy $p$. Does $f(X) \< f(Y)$ or $f(X) \> f(Y)$ ?

# Answer
> 7 votes
Answering knowingly this question would require experiments. I am sure there is some data for natural languages, where it is a common problem. I recall from memory that one study gave ridiculously small figures for natural language, which is not too surprising. If you take 5 consecutive word in a sentence (the figure I recall, without being sure), there is a good chance that one of them belongs to a single language, and even more that the fragment can syntactically belong to only one language (parsing fragments without context is possible with existing technology). To me the problem is not so much the size of the input as the size of the recognition program and its data. There is a compromise there. Actually my guess is that keeping all the relevant data is far too costly, and that the actual techniques are statistical ones, such as checking n-grams of letters. (see Wikipedia), which are extremely effective.

Regarding programming languages, the problem is a bit different. The size of the vocabulary is ridiculously small, and identifiers do not give any indication (or very little with the allowed mophology: a language could forbid to use dask inside identifiers, for example). Furthermore, what fixed vocabulary there is (keywords) is often the same in many programming languages. However, programming languages have a very strict syntax, which will certainly distinguish them rather quickly. It is not so much how long a fragment as the kind of fragment. A long succession of assignments might look the same in many programming languages. Buit I would not venture any figure, and I am not even sure statistics would make sense.

Then there is the issue of parenthood. A fragment of Pascal may look very much like a fragment of Algol 60 or Simula 67. Is American English to be distinguished from British or Autralian English?

To conclude, without any hard knowledge on facts:

The problem should be stated with a word regarding the space cost (and possibly time-cost) of the identification program.

Identification for natural language is essentially morphology or lexically based, and will use statistical techniques if space costs are to be acceptable. They can recognize fairly short sequences (a few words as I recall) with good accuracy.

Identification for programming languages is essentially syntax based, and probably needs larger fragments in number of tokens, in order to have enough syntax substance, despite the intentional similarities between programming languages. But it can probably be 100% accurate, without excessive size of the identification program. I would however be more confident if I had actual data to back my guesswork. I do not know of any work on this topic.

Considering only fragments is not an issue. It is obviously not an issue when only lexical information is used. It is not an issue either when syntactic information dominates, as the technology to parse fragments is working well.

---

**Afterthoughts, after the question was completed.**

One minor remark concerns the concept of substring size: is it measured in characters, in bytes, in lexical elements? Size of character encoding is variable. Characters take diacritical marks. Lexical elements have different average size in natural and programming languages.

A more important remark concerns the mode of measurement. Natural language will use statistical methods to avoid the problem of natural language huge specification. Hence the answer is accordingly accurate with some probability that may depend on substring length (different techniques produce different types of mis-detection).

In the case of programming languages, the specifications are small enough that they can probably be used exactly. Hence the answer could possibly be always 100% exact at acceptable cost. The problem would not be with the detection procedure inaccuracies as in natural language, but in the question itself. If a string does not discriminate two languages because it can belong to both, no amount of technology will help you solve the problem. In such a case, the detection software should not guess, which would be meaningless, but it should just list, with a 100% accuracy, all the programming languages the substring can belong to.

In other words, the case of natural language and the case of programming languages are very different technically. I am not sure it makes sense to compare them.

# Answer
> 2 votes
I understand the problem as follows:

> Given a text $t$ and models $M\_1, \dots, M\_k$ for languages, detect which of the $M\_i$ generated $t$ or, alternatively, that *none* did.

I move that the problem is *so* different for natural $M\_i$ and programming $M\_i$ that a comparison makes little sense.

The main reason is: programming languages have specifications that enable us to *solve the word problem effectively*, and often even efficiently¹. In that case, the solution is simple:

* Run parsers for all $M\_i$.
* If exactly one $M\_i$ answers "yes", output $i$.
* If none answer "yes", output "none".
* If multiple answer "yes", output "underspecified" (and maybe the list of accepting $i$).

In the case of natural languages, this is clearly not possible since we have no formal, effectively parseable representation and hence have to use a whole different set of techniques.

Now, regarding the length of the sample necessary to distinguish two languages. Even for programming languages, there is no universal answer: if you only have Lisp, Java and Malbolge in your list of models, things will be easy. If you have Pascal and Delphi or C and C++, there are (probably) arbitrarily long texts that can not be uniquely classified.

I imagine that the situation is similar for natural languages. English, Mandarin and Icelandic are probably easy to distinguish -- a single word may usually suffice -- but Norwegian and Swedish (or Danish, no idea which is closer in writing) can give you a hard time.

In other words, the question can not be answered in its generality.

---

1. Usually.

# Answer
> -2 votes
the idea that human languages are similar to programming languages is encouraged by the use of the term "language" in theoretical computer science but there which *(also)* has a very specific technical/mathematical meaning. this blurring was encouraged by ideology associated with one of the rare crosscutting pioneers in CS/linguistics, Chomsky. a computer science "language" refers to a set of strings, possibly infinite. however, there is no ambiguity involved in these mathematical sets. human language has ambiguity. human language recognition is an imperfect/ imprecise/ inaccurate exercise even for humans and it is an open question in AI whether there is an algorithm for it.

a similar analogy can be made to Turing machines. real PCs are alternatively sometimes considered equivalent, or inequivalent. sometimes the analogy breaks down. another case study here is ambiguity in CFLs. programming languages, all basically/roughly CFLs, are carefully built to avoid ambiguity. all human languages have ambiguity that even humans imperfectly parse. so in short, the question mixes up apples and oranges. but this is not uncommon in even some professional/ scientific writing on the subject of AI-related topics.

---
Tags: machine-learning, natural-language-processing, classification
---


title: Find an unambiguous grammar

text:
# Question
Title: Find an unambiguous grammar
S → aS | aSbS | (empty) where the alphabet is {a,b}

in other words, the set of strings where any prefix has at least as many 'a's as 'b's.

# Answer
A grammar that can do this unambiguously is:

$S \to aS \mid A S \mid \epsilon$
$A \to a AAb \mid \epsilon$

Every b is associated with an a in front of it, and anything between these is also associated in the same way so there is always balance.
> 1 votes

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: What are the axioms, inference rules, and (formal) semantics of lambda calculus?
Wikipedia says that lambda calculus is a formal system. It defines lambda calculus by giving its alphabet, and inductively describing what is inside its formal language.

1. Since lambda calculus is a formal system, what are its

* axioms and
    * inference rules?
2. Does lambda calculus have semantics? If yes, how does an interpretation of lambda calculus look like as a mapping from what subset to another?

# Answer
First of all, note that the notion of a formal system is an informal notion and there is no general (or generally accepted), formal definition of what a formal system is. In my opinion, the Wikipedia article on formal systems does not do a good job at explaining this and creates the illusion that formal systems are more or less the same as (the syntactic part) of logical systems, axiomatic systems, or proof systems, etc. Personally, I would rather go with the intuition given by the link at the bottom of the article, that leads to the following quote from John Haugeland's *Artificial Intelligence: The Very Idea* (1985), pp. 48-64.

> A formal system is like a game in which tokens are manipulated according to rules in order to see what configurations can be obtained. (Examples: chess, checkers, go, tic-tac-toe. Nonexamples: marbles, billiards, baseball). All formal games have three essential features:
>
> * They are token manipulation games;
> * they are digital; and
> * they are finitely playable.

where

> A digital system is a set of positive and reliable techniques (methods, devices) for producing and reidentifying tokens, or configurations of tokens, from some prespecified set of types.

From this perspective, it is much easier to see lambda calculus as a formal system:

* the tokens are lambda expressions
* the reduction rules provide the techniques as required per the "digital system"

If you want to reconcile this with the Wikipedia definition of the topic, you could consider the reduction rules to be the inference rules and the set of axioms to be empty.

Another way to look at it, is by considering the equational theory of the $\lambda$-calculus, which would look something like

* Axiom: reflexivity $$\frac{}{s=s}$$
* Rules: symmetry and transitivity $$\qquad \frac{s=t}{t=s} \qquad \frac{s=t \quad t=u}{s=u}$$
* Rules: application and abstraction $$ \frac{s=s^\prime\quad t=t^\prime}{st = s^\prime t^\prime} \quad \frac{s=t}{\lambda x.s = \lambda x.t} $$
* Axiom: $\beta$-conversion $$\frac{}{(\lambda x.s)t=s\[t/x\]}$$

It is easy to show that $t =\_\beta s$ (i.e. $t$ $\beta$-reduces to $s$) if and only if $t=s$ can be proved using the axioms and rules above. Using this system, it also makes sense, for example, to ask the usual "logical" question of consistency: Are there terms $s$ and $t$ for which we can **not** prove $s=t$.

Regarding the question of semantics, you can use the reduction rules in order to give $\lambda$-calculus operational semantics and there are also denotational semantics see Dana Scott's *Data Types as Lattices* For the latter, it might be easier to go via combinator algebras, see Engelers *Algebras and Combinators*. On a side note, this article on architectures for interpreters gives a good idea of what denotational and (small-step and big-step) operational semantics mean in this context.

In general, these questions are, however, quite hard and it might be better to first consider the simply typed $\lambda$-calculus as a starting point. Here, it is (somewhat) easy to see that it actually is a logic via the Curry-Howard correspondence. You will also find a nice answer to the question of semantics in this simple case. From the simply typed $\lambda$-calculus you can go on to consider more complicated systems in the lambda cube or things like homotopy type theory.

Also, maybe the discussion Is lambda calculus a logic? in the Lambda the Ultimate forum might also provide further insights.

Finally, this might be slightly off-topic, but if you really want to go deep down into the rabbit hole of $\lambda$-calculus, logic, and semantics, Girard's *Proofs and Types* and *The Blind Spot* might be worth a look.
> 9 votes

# Answer
This may depends on the context, as there is not a single logic based on lambda calculus. Ex. two of the most famous are Higher Order Logic and Calculus of Constructions.

An axiom is a starting point taken for granted. An inference rule is a rule by which, from an (or multiple) axiom/theorem/lemma, you can produce a new theorem or lemma, which is a proven axiom (otherwise an axiom may be supposed valid, while not proven to be so… an axiom is a starting point).

From that follows the axioms of lambda‑calculus are the syntactic rules (there also are “syntactic proofs”) and interpretations of formulas (note interpretations may vary, depending on the context) and inference rules are the rewriting and transformation rules, ex. application, abstraction, substitution, beta‑reduction and some others. Also note inference rules, are just special kind of axioms.

According to Introduction to Lambda Calculus \[pdf\] (Henk Barendregt, Erik Barendsen), the axiom of substitution, is the only required axiom (an inference rule is often taken for an axiom in the logician world).

For the semantics, it depends on the interpretation: denotational semantic and operational semantic, are both valid options, while two different enough options.

I'm posting this so that you at least get an answer, but please, note you can expect a better answer than mine, as I'm not a lambda‑calculus guru.

### Update #1

Worth reading too:

A nominal axiomatisation of the lambda-calculus \[pdf\] (Murdoch J. Gabbay, Aad Mathijssen)

> Abstract
>
> The lambda-calculus is fundamental in computer science. It resists an algebraic treatment because of capture-avoidance side-conditions.
>
> Nominal algebra is a logic of equality designed for specifications involving binding. **We axiomatise the lambda-calculus using nominal algebra, demonstrate how proofs with these axioms reflect the informal arguments on syntax, and we prove the axioms sound and complete**. We consider both non-extensional and extensional versions (alpha-beta and alpha-beta-eta equivalence) \[…\]

### Update #2

Worth to be noted in this context, to avoid confusion: the lambda calculus on it's own, is not a valid deductive system, and this is demonstrated by the existence of a function named the fixed‑point combinator \[1\], which introduce a paradox of one of the most common type: self‑referential paradox. However, some part of it, or at least of some kind of lambda‑calculus, may be sound. Ex. the type system of at least SML (I don't know for other concrete system of lambda‑calculus) is sound. In this example context, providing types are assigned an interpretation (which is straight‑forward with the Curry‑Howard isomorphism where a type is a logical proposition), the type system (if I understand correctly), is a sound deductive system. As an example, HOL systems (the proof checkers and proof assistants family, not the logic of the same name they are based on), rely on SML's type system to formally ensure the validity of the inferences sequence they check.

\[1\] As a reminder, the fixed‑point combinator is the function of this canonical form (there are other way to express it though):

```
val rec fix = fn f => (fn x => (f (fix f)) x)

```

Or more succinctly:

```
fun fix f x = f (fix f) x

```
> 3 votes

---
Tags: lambda-calculus, semantics
---


# Question
Title: What difference does it make when universal classical gates in quantum computation are reversible but not unitary?
As I've come across Grovers algorithm I dont understand why when computing ***F(X)***, which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can't it just be done using classical logic gates(and, or, etc) when the function doesn't have any thing to do with changing the superposition of the bits.

# Answer
Reversible gates are unitary, see for example https://en.wikipedia.org/wiki/Quantum\_gate. The eigenvalues are $\pm 1$. The quantum computation model requires all gates to be unitary, so you can't just use classical gates.
> 3 votes

---
Tags: quantum-computing, reversible-computing
---


# Question
Title: What does apostrophe-like symbol in the superscript mean?
It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written.

That apostrophe-type symbol in the sequence notation - what is that?

# Answer
That's a prime.

> In mathematics, statistics, and science, the prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – $x'$ generally means something related to or derived from $x$.
> 14 votes

# Answer
Draw the character on Detexify or Shapecatcher. Detexify tells you what (La)TeX commands generates a character that looks like what you drew. Shapecatcher tells you what Unicode characters looks like what you drew.

Mathematical notations tend to be easier to find via Detexify. In my first attempt, I got the correct answer `\prime` as the second choice, with the other choices obviously not right. Although Unicode does have a U+2032 PRIME character, it didn't come up among the many very similar characters that look like a diagonal line.

Once you have the name, you can look it up. Prime has a standard meaning in some fields (in particular calculus, where it means a derivative), but in general it's a way to generate more symbols: $a$ is the name for something and $a'$ is the name for something else; usually there is a relationship between $a'$ and $a$ but it's up to the surrounding text to explain what that relationship is.

Here, $(a'\_1, \ldots, a'\_n)$ is the sequence produced as output by the algorithm. It is related to $(a\_1, \ldots, a\_n)$ in that the two contain the same elements but in a different order (i.e. it's a permutation).
> 5 votes

# Answer
The idea here is that the sequence $a'\_1,\ldots,a'\_n$ is a rearrangement of $a\_1,\ldots,a\_n$ in non-decreasing order. For example, if the original sequence were $3,1,2,5,4,3$, then the new primed sequence would be $1,2,3,3,4,5$.

The prime ($^\prime$) doesn't have a fixed meaning, and in this particular case, the author could just as well have used a completely new letter for the new sequence, say $b\_1,\ldots,b\_n$. One common use for the prime is in analysis, where it designates the derivative with respect to some "understood" variable. Another common usage is in linear algebra, where it is sometimes used to denote the transpose (one of several common notations for the transpose, including $^t$ and $^T$).
> 4 votes

# Answer
As well as "prime", well covered by the other answers, the symbol is often pronounced "dash" or "dashed", as in "$x$-dash(ed)" and "$x$-double-dash(ed)" for $x'$ and $x''$, respectively. I've no idea why this is, since the symbol is completely unrelated to the punctuation mark known as a dash ("–").
> 2 votes

# Answer
As Mowji already mentioned, it means a one thing is derived from another.

Think of it as what it come from, the prime used in mathematics, for the a kind of function, named **derivative** of a function, as in: $f(x) = 2 \times x, f'(x)$ = 2 or another example $f(x) = sin(x), f'(x) = cos(x)$.

The keyword to have in mind sawing this sign is, “derivative” and/or “derived”.
> -2 votes

---
Tags: terminology
---


# Question
Title: What is $Prop$ in the calculus of constructions?
I'm looking at the Calculus of Constructions and its place in the Lambda Cube.

If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the simply-typed calculus, $\lambda\_\to$. The first axis adds type-to-term operators, the second type-to-type operators, and the third dependent typing, or term-to-type operators. The CoC has all three.

However, the CoC introduces a term $Prop$, and states that $Prop : Type$ by the inference rules, but is otherwise not used. I understand that it is for the eponymous propositions, but the logical propositions are not defined in terms of it.

Could you explain to me what $Prop$ is for, where/when it appears, and explain it in terms of the cube's axes (if indeed it is possible to do so)?

# Answer
In traditional Martin-Löf type theory there is no distinction between types and propositions. This goes under the slogan "propositions as types". But there are sometimes reasons for distinguishing them. CoC does precisely that.

There are many variants of CoC, but most would have $$\mathsf{Prop} : \mathsf{Type}$$ but *not* $\mathsf{Type} : \mathsf{Prop}$. Another difference shows up when we have infinitely many type universes and make $\mathsf{Prop}$ impredicative (this is what Coq does). Concretely, consider a variant of CoC where we have $\mathsf{Prop}$ and infinitely many type universes $\mathsf{Type}\_1$, $\mathsf{Type}\_2$, $\mathsf{Type}\_3$ with \begin{align\*} \mathsf{Prop} &: \mathsf{Type}\_1 \\ \mathsf{Type}\_1 &: \mathsf{Type}\_2 \\ \mathsf{Type}\_2 &: \mathsf{Type}\_3 \\ &\vdots \end{align\*} The formation rule for $\prod$ has to explain how to form $\prod\_{x : A} B(x)$ when $A$ is either a proposition or a type, and $B(x)$ is either a proposition or a type. There are four combinations:

1. $$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Prop}} {\prod\_{x : A} B(x) : \mathsf{Prop}}$$
2. $$\frac{A : \mathsf{Type}\_i \qquad x : A \vdash B(x) : \mathsf{Prop}} {\prod\_{x : A} B(x) : \mathsf{Prop}}$$
3. $$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Type}\_i} {\prod\_{x : A} B(x) : \mathsf{Type}\_i}$$
4. $$\frac{A : \mathsf{Type}\_i \qquad x : A \vdash B(x) : \mathsf{Type}\_j} {\prod\_{x : A} B(x) : \mathsf{Type}\_{\max(i,j)}}$$

The most interesting is the difference between the second and the fourth case. The fourth rules says that if $A$ is in the $i$-th universe and $B(x)$ is in the $j$-th universe, then the product is in the $\max(i,j)$-th universe. But the second rule is telling us that $\mathsf{Prop}$ is *not* just "one more universe at the bottom", because $\prod\_{x : A} B(x)$ lands in $\mathsf{Prop}$ as soon as $B(x)$ does, no matter how big $A$ is. This is *impredicative* because it allows us to define elements of $\mathsf{Prop}$ by quantifying over $\mathsf{Prop}$ itself.

A concrete example would be $$\prod\_{A : \mathsf{Type}\_1} A \to A$$ versus $$\prod\_{A : \mathsf{Prop}} A \to A$$ The first product lives in $\mathsf{Type}\_2$, but the second one is in $\mathsf{Prop}$ (and not in $\mathsf{Type}\_1$, even though we are quantifying over an element of $\mathsf{Type}\_1$). In particular, this means that one of the possible values for $A$ is $\prod\_{A : \mathsf{Prop}} A \to A$ itself.
> 16 votes

---
Tags: terminology, lambda-calculus, type-theory, dependent-types
---


title: Get up to speed with algorithms

text:
# Question
Title: Get up to speed with algorithms
Does anyone have any advice about how I can fast track my understanding of what these types of algorithms mean:

http://en.wikipedia.org/wiki/Monad\_(category\_theory)

I don't want to have to sit 3 years of maths but is there anything I can do for this to make more sense?

# Answer
I wouldn't have said they were *algorithms* per se, more a collection of transformations.

If you want to get a theoretical viewpoint on monads, I'd suggest picking up a category theory textbook. You don't need to do "3 years of maths" to understand one, just some set theory (probably) and some dedication.

On the other hand, if you'd prefer a practical handle, I'd learn the Haskell programming language, which uses monads extensively to represent certain types of side-effects. "Learn You a Haskell" is very good. Try and avoid the infamous "monad tutorials" which inevitably over-simplify in order to produce an analogy. I think just reading the monad typeclass, then looking at examples is probably the best advice.
> 2 votes

---
Tags: algorithms
---