title: Turing Recognisable => enumerable

text:
# Question
Title: Turing Recognisable => enumerable
I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works.

According to my notes and the book (Intro to the Theory of Computation - Sipser), to get Turing enumerator from a Turing machine, we basically write all combinations of the alphabet. You then run the TM on this input, if it accepts print it out, replace with new string repeat ad infinitum.

The problem I am having is surely this requires the language to be decidable. Otherwise it might get stuck on the third word in some infinite loop doomed never to accept or reject and certainly never print out the whole language.

What am I missing?

# Answer
> 9 votes
What's missing is the way you run the Turing Machine $M$ on strings to get the Enumerator. Rather than generate each string, run $M$, and then output this string if the $M$ accepts – which as you identified will not work – you do something like the following, which adopts the strategy of simulating many instances of the $M$ on different strings "in parallel".

Assume the tape has contents $\langle w\_1, S\_1\rangle \\# \cdots \\# \langle w\_n, S\_n\rangle$, where $w\_i$ is some word under consideration and $S\_i$ is the current state of $M$ operating on $w\_i$. This represents that $n$ copies of $M$ are being simulated. $w\_i$ is stored so we know what the original input was.

Now run the following loop

1. At the end the tape write the next string from $w\in\Sigma^\*$, along with the initial configuration $S$ of $M$, that is, write $\\# \langle w, S\rangle$.
2. Simulate each copy of the $M$ on the tape for one step. (Presumably use another tape.)
3. If any of the $M$s enters an accepting state, put the corresponding string onto the output tape. Remove this instance of $M$ from the tape.
4. If any of the $M$s enters a rejecting state, remove that instance of $M$ from the tape.
5. Goto step 1.

It is not hard to argue that all strings $w\in\Sigma^\*$ accepted by $M$ will eventually be output on the tape.

---
Tags: computability, turing-machines, intuition
---


# Question
Title: Is connecting islands with pontoons NP-complete?
I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it.

Here is the problem:

There are **k** islands in a very big lake, and there are **n** fan-shaped pontoons. Those pontoons are in the same size but have different initial directions and are in different original positions in the lake. The pontoons can rotate freely around its center of mass, and no cost associated with rotation.

Now we need to move those pontoons so that all islands in the lake can be connected. We can guarantee the number of pontoons is enough to connect all the islands.

**\[Note\]: We cannot reuse the pontoons!!**

The task is to find the solution having the minimum total distance of the moving pontoons in order to make all islands connected. The distance of moving one pontoon can be calculated as the distance between the center of mass's original position and its deployed position.

To make it clear, I have drawn such a figure. Suppose we have 3 islands A, B and C. They are located somewhere in the lake. And I have several fan-shaped pantoons. Now the solution is to find a minimum moving distance summation to connect A, B and C, shown in bottom part of the figure. Hope it help understand the problem. :)

It seems that the problem is a NPC one, but I don't know to prove it. Can anyone help me on this?

# Answer
> 1 votes
After looking at the new diagrams, I see that you may need multiple pontoons to cross between islands. Given that, you could get very close to a solution of the Steiner Tree problem by turning the nodes into islands and creating a sufficiently diverse collection of pontoons with small arcs. Wikipedia says that there is in fact a PTAS for the Steiner tree problem, so I can't say immediately that this renders it NP-complete. However looking at the details of the Steiner tree might either get you a good approximate solution or show that the problem is NP-Complete.

# Answer
> 1 votes
First: This is not the Travelling Salesman Problem. The TSP requires the identification of a minimal weight Hamiltonian cycle; this cycle does not require a cycle, or even a minimal weight path at all. It requires a minimal cost *construction* of a connecting set of edges, where the construction cost is based on moving the pontoons around.

Second: This is not the Minimal Weight Spanning Tree Problem. See above-- we require a minimal cost *construction* not minimal weight identification.

Third: It seems that the constructed path will be a spanning tree, but not necessarily a minimal weight one. The alternative is that it would be a spanning tree plus some additional edges resulting in a cycle; but if we start in a configuration with no edges, then every edge has some positive cost and we can always find a lower weight spanning tree by simply not constructing the extra edges.

Fourth: You say the pontoons rotate freely; I assume that means that no costs is associated with rotating the pontoons. However, you do not specify what the pontoons rotate about: Their points? Their centers of mass? Any internal point? (If any external point, then we would have zero weight constructions, yes?)

This is a little bit subtle, because if we're rotating 90 degrees about an internal point, say, the center of mass, what is the cost? Nothing, because it's a rotation? Some finite amount because the point moved? Now we also need to know the size of the pontoons.

Fifth: One assumes both the pontoons and the islands both are embedded in the Euclidean Plane?

# Answer
> 0 votes
After the drawing, This is still an NPC problem. Even if we cut the problem down to each pontoon can assume 1 of n positions (i.e. known connection lines. To get the most optimal answer, we would have to try each pontoon in each position, adding their distance to get to those repsective positions each time, and comparing against all others. if each pontoon has to be tested in each position, then there are n! combinations needing to be tested.

Ive chosen to edit the original poster's images with some additions to show the graph ideas behind this problem.

The below image shows all (minus 2 to make it simpler) pontoons in differing colors, with all potential pontoon end locations in RED. I have only drawn the lines between 3 pontoons and all of the end locations, but one could see how CRAZY this could get.

Say that just for the heck of it, we choose for the turquoise pontoon to be placed at the end location closest to it as the first step (although FROM THE TSP we know that this may not be optimal in the end).

Below we see exactly that, the pontoon and the distance (a.k.a. weighted traveling distance) it will have to travel.

From here a virtual node with the two end locations next to the just placed location may be made. Distance from the set node, and the two adjacent nodes within the virtual node have a virtual travel distance of 0.

Below we see the virtual node created with ALL potential travel distance weights that can be placed there.

Seeing how this would continue, and how the most optimal solution (as seen many times with the TSP) will not always be by choosing the shortest distance for every choice, we would have to test essentially all paths for all nodes / virtual nodes.

In the end the first node of the (TSP) problem could be any one of the potential end pontoon points, and the lines drawn from that are the distances from that endpoint to all other pontoons. all other nodes afterwards become virtual nodes as I have depicted with their lines coming off as the distances / weights to all remaining pontoons, and so on and so forth. How this graph problem is NOT EXACTLY the traveling salesman problem without the LAST JUMP requirement from the hamiltonian cycle is beyond me. In order to have the exact answer one must test all paths through the graph.

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


# Question
Title: How are threads implemented in different OSs?
I was reading **Linux Kernel Development** by Robert Love, where I came across this

> Linux takes an interesting approach to thread support: It does not differentiate between threads and normal processes.To the kernel, all processes are the same— some just happen to share resources.

I do not know much about OSs (aspire to know more) and kernels and hence the above quote raised a question about thread implementations in different OSs(at least the popular ones like Windows, Linux and Unix).

Can someone please explain the different techniques for providing thread-support in an OS? ( and optionally contrast them)

# Answer
Threads and processes are execution contexts. They mostly differ only by the amount of shared state (memory, signal handlers, file descriptors,...) with the other execution contexts (processes share little with other processes; threads share a lot with the other threads in the same process).

Most OS keep the two things separated, and thus know about several kinds of execution context.

Linux kernel on the other hand has just one kind of execution context, which is able to share or not things with other. If you want a process, set it up so that it share little, it you want threads, set them up so that they share what they need. You can set things up so that they behave in a way unsuitable for the process/thread terminology.

The POSIX API commonly used when programming for Linux knows only about processes and threads and thus most programs don't really care about what is an implementation detail for them in the way responsibilities are divided between kernel and user space. Older implementations of threads leaked some the implementation details (ps showing threads, thread id and process id mixing up, ...) and didn't provide exact POSIX semantic in some cases (signal delivery was problematic IIRC).
> 2 votes

---
Tags: operating-systems, process-scheduling, threads
---


# Question
Title: Are there complete problems for P and NP under other kinds of reductions?
I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions.

Are these two classes the only possible classes of reductions under which $\mathsf{P}$ has complete problems?

Also, what classes of reduction can be used for $\mathsf{NP}$ beside polynomial-time reductions?

# Answer
Your questions contain a few incorrect or unclear phrases. Neither “complexity class X has Y reduction” nor “we can use Y reduction for complexity class X” makes sense. In addition, there are at least two definitions known under the name “polynomial-time reductions,” both of which are used to study NP-completeness: polynomial-time many-one reductions and polynomial-time Turing reductions. But in this answer, I will ignore the difference between many-one reductions and Turing reductions, and I will focus only on the resource restrictions of reductions, because otherwise the answer will become too long and unfocused.

Now I will restate what you might want to ask, and answer them.

*Are there any definitions of reductions with respect to which NP-completeness can be defined, other than polynomial-time reductions? Are there any definitions of reductions with respect to which P-completeness can be defined, other than NC reductions and log-space reductions?*

As Artem and Raphael said, you can define whatever you like.

*Are there any definitions of reductions actually used to study NP-completeness in the literature, other than polynomial-time reductions? Are there any definitions of reductions actually used to study P-completeness in the literature, other than NC reductions and log-space reductions?*

Yes. For example, Papadimitriou uses log-space reductions throughout his textbook \[Pap94\], including the definition of NP-completeness. (Note: in \[Pap94\], the term “L-reduction” means something completely different from log-space reduction.) As for P-completeness, NC<sup>*k*</sup> reductions are mentioned in \[GHMRSS00\]. This is a special case of NC reductions, and more general than log-space reductions for *k*≥2.

*But are they really different notions, or just different definitions for the same notion?*

Currently, no one knows. For example, log-space reducibility and polynomial-time reducibility are equivalent if and only if L=P.

\[GHMRSS00\] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi, and Takayoshi Shoudai. *The Parallel Computation Project: Volumes I–III*, 2000. http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/

\[Pap94\] Christos H. Papadimitriou. *Computational Complexity*. Addison-Wesley, 1994.
> 10 votes

# Answer
Note that if complexity class $C$ has a complete problem under a class of reductions $A$, then the same problem will be complete for $C$ under and class of reductions containing $A$.

Typically completeness proofs go through with much weaker class of reductions than usually stated (e.g. under $\mathsf{AC^0}$ reductions). Any class of reductions containing $\mathsf{AC^0}$ would suffice and there are uncountable many such classes.

You may also want to check the following paper:

* Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T., and Rudich, S., "Reducing the Complexity of Reductions", Journal of Computational Complexity, 10, pp.117-138, 2001. Preliminary version in Proceedings of ACM STOC, 2001.
> 4 votes

# Answer
As Artem notes in his comment, the question is rather unmeaning as you can define whatever you like. Let me illustrate where things start to be "kind of silly".

Some notation: For two problems $P,Q$, write $P \leq\_F Q$ for some class of functions $F$ if there is $f \in F$ such that $P(x) = Q(f(x))$ for all inputs $x$ (of $P$), that is if $P$ can be $F$-reduced to $Q$. Write $XC\_F$ for the class of $X$-complete problems with respect to $F$, that is

$\qquad \displaystyle XC\_F = \\{P \in X \mid \forall Q \in X.\ Q \leq\_F P \\}$.

Denote furthermore with $T\_X$ the set of (asymptotically optimal) runtime functions of algorithms that compute functions in some set $X$.

Now consider an arbitrary (complexity) class of problems $X$¹. If we restrict reduction space $F$ in terms of time complexity -- everything is possible here -- there are roughly two cases:

* $T\_F \supseteq \Omega(T\_X)$² -- reductions are not faster than problem solvers.

In this case, $XC\_F = X$ -- this is clearly not very interesting for complexity theory. Considering such $F$ may be useful in practice, especially if $T\_F \subseteq \Theta(X)$; you can reduce all problems in $X$ to a handful of problems which you can solve very well. Linear programming and SAT are typical examples because of highly optimised LP- resp. SAT-solvers.
* $T\_F \subseteq o(X)$ -- reductions are faster than problem solvers

Here interesting things can happen, that is $XC\_F \subset X$ or $XC\_F \neq XC\_{F'}$ for different reduction spaces. Whether these facts have interesting ramifications depends on the concrete choice of $X$ and $F$. Note that $XC\_F = \emptyset$ might happen, which is in itself interesting enough.

Things definitely become rather uninteresting when you choose $F$ so "small" that $\leq\_F$ is sparse, that is few reductions are possible. Think of $X=\mathsf{NP}$ and $F$ such that $T\_F \subseteq o(n)$; reductions have to shrink input sizes significantly and cannot spend too much time on it, so $F$ is not very powerful.

Note, though, that even a restriction to $T\_F \subseteq O(1)$ leaves meaningful relations; for instance, "Is $x$ an even integer?" can be reduced to "Is $x$'s first bit 0?" in $O(1)$ time and space. So it might be interesting to study even such weak reductions to find out which problems are close to which others in terms of reduction complexity; you definitely see such differences in classic $\mathsf{NPC} = \mathsf{NP}C\_P$ reductions.

Technically, there is a third case, for example $T\_F = P$ and $T\_X = \Theta(n^3)$; in this case -- if $F$ is reasonably rich -- the comments on case one apply. Note also that the question which case $F$ falls into may be interesting in itself: "$\mathsf{P=NP}$?" is essentially asking whether $T\_F=\Theta(X)$ (and even whether $F = \Theta(XC\_F)$).

---

1. In order to be a "proper" complexity class, it needs to be some sort of "downward closed" w.r.t. complexity.
2. $\circ(X)$ for a function class $X$ and $\circ$ a Landau symbol is the natural extension of the usual Landau symbols, i.e. $\circ(X) = \bigcup\_{f \in X} \circ(f)$.
> 0 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Probabilities of duplicate mail detection by comparing notes among servers
I have the following problem:

> We want to implement a filtering strategy in e-mail servers to reduce the number of spam messages. Each server will have a buffer, and before sending an e-mail, it checks whether there is a duplicate of the same message in its own buffer and contacts k distinct neighboring servers at random to check whether the duplicate is in another buffer. In case any duplicate message is detected, it will be deleted as spam, otherwise it will be sent after all negative replies are received.
>
> Let us assume that there are N mail servers, and that a spammer sends M copies of each spam mail. We assume that all copies are sent simultaneously and that each mail is routed to a mail server randomly.

Given M, N and k I need to find out the probabilities that no spam message is deleted (i.e. no server detects spam), all spam messages are deleted (all servers detect spam) and spam messages are deleted from at at least one server.

So far, I have used combinations without repetition to find out the cases that need to be taken into account for an M and N. Now I need to find out the probability that one server receives at least two copies of a message, but I am at complete loss. Could you please provide some insight into the problem?

# Answer
If a given server receives $m \leq M$ copies, it does not receive $M-m$ copies. Also, there are many ways to pick $m$ messages out of $M$; you have to consider all of them. Furthermore, important assumptions are that

* "randomly" means "uniformly at random", that is the probability that any given copy goes to any given server is $\frac{1}{N}$, and that
* each copy is routed independently of its siblings, that is we have independent random events for the individual copies.

This is all you need to piece together the probability $\operatorname{Pr}(S\_i = m)$ that server $i$ receives $m$ messages.

> If you put the above together, you get
> $\qquad \displaystyle \operatorname{Pr}(S\_i = m) = \binom{M}{m} \left(\frac{1}{N}\right)^m \left(1 - \frac{1}{N}\right)^{M-m}$
> for $S\_i$ being the number of copies the $i$-th server receives, $1\leq i \leq N$. You should recognize this kind of probability weight.
> If you have doubts that this is correct, run some simulations (not a proof!).

Now it is easy to compute $\operatorname{Pr}(S\_i \geq 2) = 1 - \operatorname{Pr}(S\_i = 1) - \operatorname{Pr}(S\_i = 0)$.

> When using the derived weight in other calcuations, keep in mind that the $S\_i$ are *not* independent because $\sum\_{i=1}^N S\_i = M$. The underlying probability distribution is the well-studied multinomial distribution.
> 5 votes

---
Tags: combinatorics, probability-theory
---


# Question
Title: Why is it seemingly easier to resume torrent downloads than browser downloads?
I really wonder how torrent downloads can be resumed at later point of time. If such a technology exists, then why is it not possible in browsers?

It is often not possible to pause a browser download so that it can be resumed at a later point of time. Often, the download will start again from the beginning. But in the case of a torrent download, you can resume anytime.

One reason I could think of is that a browser makes an HTTP connection to the server which contains the file, and when this connection breaks, there is no data regarding how much file was saved so no resume is possible.

Is there a fundamental reason why torrent downloads are easier to resume than web downloads?

# Answer
The bittorrent protocol was designed to transfer large files out-of-order. It divides files in chunks (*pieces* in bittorrent terminology), and maintains a map of which participant holds which chunks. One of the elementary commands is for one participant to request a chunk from another participant. If a client crashes or disconnects, it can check which chunks it has already downloaded (the base data includes a cryptographic checksum for each chunk) and request only chunks that it does not already have. I think bittorrent includes a command to request part of a chunk, too, but if worst comes to worst only chunks that have not been fully downloaded need to be re-requested.

The HTTP protocol was designed to transfer mainly small files and to be simple to implement. Its most basic command is to download one file with a minimum of fuss. A simple server may only understand one command, to download a file in full. Hence, if the download is interrupted, there is no choice but to download the whole file again. There is a way for a client to request only part of a file (with the `Range:` header). Not all servers implement it (because it is not a fundamental feature of HTTP). Web browsers typically don't bother with it (because they are primarily designed to download small files: web pages), but all download managers support it (because they are designed to load large files) and will use it if the server accepts.
> 8 votes

# Answer
Actually, most browsers can resume downloads, provided they are from an FTP-server.

The difference between HTTP and FTP downloads is that whereas FTP has the `REST`(art) command to start a file transfer from a specified point, ~~the HTTP protocol knows no such method~~. With HTTP, you always get the whole file, starting from the first byte.

As for the BitTorrent protocol, the file or files are split into chunks and individual chunks are fetched from different machines. The BitTorrent client keeps track of which chunks have been received and which are missing, and on restart only requests the missing chunks from other clients.

**Update**

As svick pointed out in the comments, HTTP does support sending only parts of a file, but as Raphael, this is somewhat an abuse of the original protocol.
> 3 votes

# Answer
It depends of the server. If the server accepts the *resume* or *continue* operation then you can resume the download if you have the appropriate software, e.g. wget that does that since the beginning, even for HTTP.

Some download manager that you can integrate in your browser does that, but for some reason browsers usually don't do that by default.

BitTorrent manages this very easily since it only downloads files pieces by pieces.
> 2 votes

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Enumerating all the walks in a graph between a start vertex and a terminal vertex?
I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?

# Answer
> 8 votes
## If the input graph is undirected:

* If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.
* If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.
* Otherwise, there are infinitely many walks from $s$ to $t$.

---

## If the input graph is directed:

Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable. Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$. Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.

* If $H$ is empty, there are no walks from $s$ to $t$.
* If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a *simple path*. The number of *paths* in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming. **Remaining details are left as a homework exercise.**
* Otherwise, there are infinitely many walk from $s$ to $t$.

---
Tags: algorithms, reference-request, graphs
---


# Question
Title: Is a device with restrictive execution policies Turing-complete?
There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor.

Take an iPhone as an example where new applications are loaded (solely) from app-store and programs that would allow execution of arbitrary code by user (without permission of Apple) are not permitted (e.g. Flash).

Are such machines where users cannot execute arbitrary code on themselves still Turing-complete computers? Can they still be considered as *universal Turing machines*?

# Answer
> 5 votes
First, Apple may wish to restrict applications, but in practice, all versions of the iPhone can be jailbroken: you can then upload arbitrary machine executables. Whether the phone vendor likes or dislikes that you jailbreak the phone is immaterial to evaluating its computing power. But, for the same of the argument, let's add the hypothesis that the iPhone is not jailbroken, and more generally that you only use the iPhone in ways that are approved by Apple.

Whether you can load your code without Apple's approval or not is not relevant. The iPhone is Turing complete if there is *some* way of programming every computable function and of encoding arbitrarily long inputs and outputs. Turing completeness doesn't say that the encoding has to be what you consider the most natural, which is to install arbitrary machine code.

There is a killer argument which shows that the iPhone, like any other computer, is not Turing-complete: it only has a finite amount of memory. Therefore, the class of computing power is that of a finite automaton, no more.

If the iPhone was allowed to rely on an external storage medium that allowed to store an arbitrarily large amount of data (finite, but whose length is not bounded by the input size), and if network access was allowed, then it would be Turing-complete. One way would be to browse a website containing a Turing machine emulator or other Turing-complete computation mechanism, with input being defined as typing in a form and output being defined as changing the content of the page.

There are other ways of encoding Turing machines that don't require network access or non-default apps to begin with. You would need an iPhone augmented with an infinite tape to pull it off, though, so such an encoding would have to specify how the tape is used in addition to the use of actual iPhone features.

For example, you can type arbitrary JavaScript in bookmarklets in the web browser. If we ignore the problem that a concrete physical device has a finite amount of memory, JavaScript is a Turing-complete language. If you treat the bookmarklet arguments as input and the target URL as output, you can implement a universal Turing machine. JavaScript cannot i nteract with all hardware devices, but as far as pure computing power is concerned, it is sufficient to perform any calculation.

# Answer
> 4 votes
The iPhone has a Turing Machine App. Therefore, if it has an infinite amount of memory, the iPhone would be Turing complete.

But no general purpose computer is Turing complete because it has a finite amount of memory, which is insufficient to model the infinite amount of memory required by a Turing Machine.

If you were to have an infinite amount of memory, then the fact that Apple controls what can go onto the device only plays a role if they limit the amount of memory available to the TM App.

# Answer
> 3 votes
It depends on what system you are considering.

No:

One of the criteria that could/should/must be used for approbation from the device vendor would be that the program does something, at least sometimes. It reasonably implies that the program terminates on at least one input.

Unfortunately for a system to be Turing-complete means that it can simulate all computable functions and that includes the partial function that is defined nowhere. (i.e. that never terminates). Surely such a program would not be approved. Therefore Turing completeness is impossible.

Yes:

You could consider that you can build a system *on top of the system* for example if you can have an interpreter being approved (see Dave's comment) then you can compose it with an external tool to be able to compute every computable function (just input the Turing machine into it), including the nowhere-defined function, even though the interpreter is only *one* function and thus is not all computable functions.

# Answer
> 3 votes
Just an additional comment to complement the good answers above:

... just check in the *game section* of your favourite smartphone, if you find a puzzle game that is PSPACE complete (my favourite is Sokoban) and the game has a *level editor* and a *help option to automatically find the solution*, then you have a (*deadly weird*) Turing Machine (with finite amount of memory)!!! :-D

---
Tags: computability, turing-completeness
---


# Question
Title: Representing Negative and Complex Numbers Using Lambda Calculus
Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?

# Answer
First encode natural numbers and pairs, as described by jmad.

Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus):

```
neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

```

The case of complex numbers is similar in the sense that a complex number is encoded as a pair of reals. But a more complicated question is how to encode reals. Here you have to do more work:

1. Encode a rational number $q$ as a pair $(k,a)$ where $k$ is an integer, $a$ is natural, and $q = k / (1 + a)$.
2. Encode a real number $x$ by a function $f$ such that for every natural $k \in \mathbb{N}$, $f k$ encodes a rational number $q$ such that $|x - q| \< 2^{-k}$. In other words, a real is encoded as a sequence of rationals converging to it at the rate $k \mapsto 2^{-k}$.

Encoding reals is a lot of work and you do not want to actually do it in the $\lambda$-calculus. But see for example the `etc/haskell` subdirectory of Marshall for a simple implementation of reals in pure Haskell. This could in principle be translated to the pure $\lambda$-calculus.
> 18 votes

# Answer
Lambda-calculus can encode most data structures and basic types. For example, you can encode a pair of existing terms in the lambda calculus, using the same Church encoding that you usually see to encode nonnegative integers and boolean:

$$\mbox{pair}= λxyz.zxy$$ $$\mbox{fst} = λp.p(λxy.x)$$ $$\mbox{snd} = λp.p(λxy.y)$$

Then the pair $(a,b)$ is $p=(\mbox{pair }ab)$ and if you want to get back $a$ and $b$ you can do $(\mbox{fst }p)$ and $(\mbox{snd }p)$.

That means that you can easily represent positive and negative integers with a pair: the sign on the left and the absolute value on the right. The sign is be a boolean that specified whether the number is positive. The right is a natural number using Church encoding.

$$(sign,n)$$

And now that you have relative integers. The multiplication is easy to define, you just have to apply the $\mbox{xor}$ function on the sign and the multiplication on natural numbers on the absolute value:

$$\mbox{mult}\_ℤ=λab.\mbox{pair} ~~(\mbox{xor}(\mbox{fst }a)(\mbox{fst }b)) ~~(\mbox{mult}\_ℕ(\mbox{snd }a)(\mbox{snd }b))$$

To define the addition, you have to compare two natural numbers and use subtraction when the signs are different, so this is not a λ-term but you can adapt it if you really want to:

$$\mbox{add}\_ℤ=λab.\left\\{\begin{array}{ll} (\mbox{true},\mbox{add}\_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a≥0∧b≥0 \\ (\mbox{false},\mbox{add}\_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a\<0∧b\<0 \\ (\mbox{true},\mbox{sub}\_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a≥0∧b\<0∧|a|≥|b| \\ (\mbox{false},\mbox{sub}\_ℕ(\mbox{snd }b)(\mbox{snd }a)) & \mbox{if } a≥0∧b\<0∧|a|\<|b| \\ (\mbox{true},\mbox{sub}\_ℕ(\mbox{snd }b)(\mbox{snd }a)) & \mbox{if } a\<0∧b≥0∧|a|\<|b| \\ (\mbox{false},\mbox{sub}\_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a\<0∧b≥0∧|a|≥|b| \\ \end{array}\right.$$

but then subtraction is really easy to define:

$$\mbox{minus}\_ℤ=λa.\mbox{pair}(\mbox{not}(\mbox{fst } a))(\mbox{snd } a)$$ $$\mbox{sub}\_ℤ=λab.\mbox{add}\_ℤ(a)(\mbox{minus}\_ℤb)$$

Once you have positive and negative integers you can define complex integers very easily: it is just a pair of two integers $(a,b)$ which represents $a+b\mbox{i}$. Then addition is point-wise and multiplication is as usual, but I won't write it, it should be easy:

$$\mbox{add}\_{ℤ\[\mbox{i}\]}=λz\_1z\_2.\mbox{pair} (\mbox{add}\_ℤ(\mbox{fst }z\_1)(\mbox{fst }z\_2)) (\mbox{add}\_ℤ(\mbox{snd }z\_1)(\mbox{snd }z\_2))$$
> 13 votes

---
Tags: data-structures, lambda-calculus, integers, real-numbers
---


# Question
Title: Numbers of ways of expressing the sum of a number between [a,b]
I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval \[a, b\]

# Answer
What you want is the number of integer partitions restricted to the interval $\[a,b\]$. I suggest you take a look at the approaches to count *all* partitions (check references and external links of the article) and adapt it to your needs.
> 4 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Optimizing a join where each table has a selection
Consider the following query:

```
SELECT Customer.Name FROM Customer
INNER JOIN Order on Order.CustomerId = Customer.Id
WHERE Customer.Preferred = True AND
      Order.Complete = False

```

Let's suppose all of the relevant attributes (Customer.Preferred, Order.Complete, Order.CustomerId and Customer.Id) are indexed. How can I evaluate this as quickly as possible?

Standard optimization advice would say that I should do the select on each table first, then the join using sort-merge or whatever the cardinality would imply. But this involves two passes through the data - I'm wondering if there's a better way.

---

**EDIT**: I think asking if there was a "better way" was too ill-defined. Suppose we are trying to find $\sigma\_a(A)\bowtie\_j\sigma\_b(B)$. Observe that we can find this in $O(\alpha)$ (where $\alpha$ is the cardinality of $\sigma\_a(A)$) with the following pseudocode:

```
for each a in A:
   find foreign tuple in B  // constant-time, if using hash table
   check if foreign tuple meets foreign constraint  // again, constant time

```

As mentioned by some answerers, there are various minor permutations (do the for loop over B instead, etc.). But they all seem to be $O(\alpha)$ or $O(\beta)$. Is there a better way?

Note that if it the query were a self join, we could just do the merge part of a sort-merge join, (since our indexes would already be sorted) which would run in time proportional to the number of results. So I ask if a similar thing can be done here.

I am more than happy to accept a proof that there is no better method as an answer. I believe that there is no faster algorithm, but I'm unable to prove it.

# Answer
When an SQL statement is turned into an execution plan, several optimization techniques are used. The use of indices allow to efficiently (without a full scan) select tuples that agree with a selection condition. Another technique in use is semantic optimization, *id est*, to turn a query into an equivalent one with better behaviour. To do so, identities of relational algebra are used.

For specifically, in the example, the identity between selection and product

$\qquad \displaystyle \sigma\_{\alpha}(C \times O) = \sigma\_{\beta \wedge \gamma \wedge \delta}(R \times P) = \sigma\_{\delta}(\sigma\_{\beta}(R) \times \sigma\_{\gamma}(P))$

(with $\beta$ being the part of the condition $\alpha$ which refers *only* to attributes from $C$ and $\gamma$ the one with attributes from $O$) can be used. Informally worded this identity is "pushing selection through joins/product" (the identity holding for join too). The identity can be thought as a kind of rewrite rule, reading it from left to right. So the following identity holds in the example :

$\qquad \displaystyle \begin{align} &\pi\_{Name}(\sigma\_{Preferred=True \wedge Complete=False}(C \Join\_{CustomerId = Id} O)) \\ = &\pi\_{Name}(\sigma\_{Preferred=True}(C) \Join\_{CustomerId = Id} \sigma\_{Complete=False}(O)) \end{align}$

Doing so, you do not waste time computing the product of irrelevant tuples of $C$ and $O$. The more selective the $\beta$ and $\gamma$ predicates are, the larger the gain is. And IMO, I don't think you can ever lose some time using this rule. For a more formal treatment of this aspect of optimization, one can look at the Static Analysis and Optimization chapter of the Foundation of Databases book.
> 4 votes

# Answer
There are different schools of thought. The prevailing wisdom, originated with *System R*, is calculate cost of every execution strategy and select the minimal one. This leaves you at the mercy of optimizer calculating/guessing statistics and costing everything properly. Some people believe that this is almost never done reliably for any query of moderate complexity. Even in your simple case, there is overwhelming number of possible execution scenarios:

1. Perform single table predicate selection (indexed or not) on Customer.Preferred = True first, then join with Order.
2. Perform single table predicate selection on Order.Complete = True first, then join with Customer.

Then there are 3 types of join, and even more if we take into account indexed nested loops leveraging different compound indexes.

Hence, heuristics like you suggest: "apply single table predicate first, then join". One can argue that heuristics, failing to deliver optimal plan, would, at least, guarantee some "good enough" solution. In your particular case an execution plan that leverages Indexed Nested loops is certainly be not the worst. Please keep in mind, that unless you leverage compound index, such as (Order.Complete, Order.CustomerId) when joining with Order table, you would have to apply single table predicate on it **the last**.
> 3 votes

---
Tags: optimization, database-theory, relational-algebra, databases
---


title: voting scheme for peaceful coexistence

text:
# Question
Title: voting scheme for peaceful coexistence
Many areas in the world suffer from conflicts between two groups (usually ethnic or religious). For the purpose of this question, I assume that most people of both sides want to live in peace, but there are few extremists who incite hatred and violence. The goal of this question is to find an objective way to filter out those extremists.

Imagine a town with 2 conflicting groups, A and B, each has N people. I propose the following voting scheme (which I explain from the point of view of group A, but it's entirely symmetric for the other group):

* **equality-rule**: The number of people in each group must always remain equal.
* **expel-vote**: At any time, each person of group A can claim that a certain person of group B is "extremist", and start a vote. If more than 50% of the people in group A agree, then that certain person is expelled from town.
* **counter-vote**: To keep the equality-rule, a single person of group A should also leave the town. This person is selected by a vote between the people in group B (i.e. each person in group B votes for a single person in group A, and the one with most votes is expelled from town).

My intuition is that:

* On one hand, this scheme encourages people to be nice to people of the other group, so that they won't be subject to expel-votes.
* On the other hand, the equality rule encourages people to think twice before starting an expel-vote, because this will put them in danger of expel in the counter-vote.

\[ADDITION\] Several questions can be asked about this scheme, for example:

* Under what conditions does it diverge to a situation where people vote and counter-vote, until the number of citizens in one of the groups reaches 0?
* Under what conditions does it stabilize on a situation where the two group has more than 0 citizens?
* Under what conditions, the stable number of citizens is more than half the initial number?

Note that this scheme does not even try to reach an objective measure of "extremism". The only goal is stability.

I would like to know, has this voting scheme has been studied in the past?

# Answer
> 3 votes
If a person owns property in the town, then when voted out, they presumably forfeit the property. This creates an economic incentive to systematically rob minority groups via things like the Spanish Edict of Expulsion which expelled the community of Jews that had thrived prior to the *Reconquista* from Spain. Although the decree technically allowed them to sell their possessions (at firesale prices) before fleeing, they were not allowed to take the proceeds with them:

> And we likewise give license and faculty to those said Jews and Jewesses that they be able to export their goods and estates out of these our said kingdoms and lordships by sea or land **as long as they do not export gold or silver or coined money** or other things prohibited by the laws of our kingdoms, excepting merchandise and things that are not prohibited.

Such incentives might be sufficient for cartels to arise. A cartel that can corner the market on readily available portable wealth can combine that control with bloc voting to vote out an identifiable minority group in such a way that they have little option but to liquidate assets through the cartel making the cartel members wealthy.

Any analysis should take into account such incentives. Game theory, since it does not by itself model irrational tendencies like in-group/out-group bias, might have a hard time predicting such things.

---
Tags: reference-request, game-theory, voting
---


# Question
Title: Recursive, Recursively Enumerable and None of the Above
Let

* $A = \mathrm{R}$ be the set of all languages that are recursive,
* $B = \mathrm{RE} \setminus \mathrm{R}$ be the set of all languages that are recursively enumerable but not recursive and
* $C = \overline{\mathrm{RE}}$ be the set of all languages that are not recursively enumerable.

It is clear that for example $\mathrm{CFL} \subseteq A$.

What is a simple example of a member of set B?

What is a simple example of a member of set C?

In general, how do you classify a language as either A, B or C?

# Answer
You can choose the language of the halting problem

$\qquad \displaystyle B\_1 = \\{\langle T \rangle \mid T \text{ halts on } \langle T \rangle\\} \in B$

and its complement

$\qquad \displaystyle C\_1 = \overline{B\_1} \in C$.

This is fairly standard material. The proof for $B\_1$ not being recursive is the well-known diagonalization. Proving $B\_1$ to be RE (recursively enumerable) is a tad tricky, involving interleaved simulation of multiple TMs, but is widely documented. If $C\_1$ were RE, then $B\_1$ being RE would imply that both are recursive; hence $C\_1$ is not RE. This illustrates *some* of the techniques for such proofs in general.
> 5 votes

# Answer
To add to David Lewis's answer, I will answer the final part of your question. To show that a language L is in A (this set is usually denoted as R) there are (at least) 3 popular techniques:

1. Show there exists a turing machine M that halts on all input (this means it will always stop) and that accepts a word $w$ if and only if $w \in L$. This is the definition of R.
2. Show a Turing reduction from L to any other language K that is known to be in R. Intuitively this means that L is easier then K, and if K is recursive so is L.
3. Show that L is in B (usually denoted as RE) and co-RE (All the languages K s.t. $K^c \in$ RE). This will show that L is in R because R = RE $\cap$ co-RE.

To show that a language L is in B (RE) you can either:

1. Show there exists a turing machine M that halts and accepts on every w $\in$ L. This is the defenition of RE. Notice that unlike in A1, you don't care if M halts or keeps running forever on any w $\notin$ L, as long as it doesn't accept it.
2. Show a Turing reduction from L to any other language K that is known to be in RE.

To show that a language L is in co-RE you need to show that $L^c\in RE$. Again, this is from the defenition of co-RE.

An important fact is that the set C you defined is not equal to co-RE. There are languages that are neither in RE or in co-RE.
> 4 votes

---
Tags: formal-languages, computability
---


# Question
Title: "Flow layouts" inside a GUI -- how do I come up with a good algorithm?
I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode):

```
int rowHeight = 0;
RECT rect = parent.getClientRect();
POINT pos = rect.position;  // Start at top-left corner, row by row

foreach (Window child in parent.children)
{
    // POINT is a tuple of: (x, y)
    // SIZE is a tuple of: (width, height)
    // RECT is a tuple of: (left, top, right, bottom)
    RECT proposed1 = RECT(rect.left + pos.x, rect.top + pos.y, rect.right, rect.bottom),
         proposed2 = RECT(rect.left, rect.top + pos.y + rowHeight, rect.right, rect.bottom);
    SIZE size1 = child.getPreferredSize(proposed1),
         size2 = child.getPreferredSize(proposed2);
    if (size1.width <= proposed1.width)
    {
        child.put(proposed1);  // same row
        pos.x += size1.width;
        rowHeight = max(rowHeight, size1.height);
    }
    else
    {
        child.put(proposed2);  // new row
        pos.x = rect.left;
        pos.y += rowHeight;
        rowHeight = size2.height;
    }
}

```

In other words, the algorithm is very simple:
The layout manager asks every component, "is the remaining portion of the row enough for you?" and, if the component says "no, my width is too long", it places the component on the next row instead.

There are two major problems with this approach:

* This algorithm results in very long, thin components, because it is essentially greedy with the width of each component -- if a component wants the whole row, it will use the whole row (ugly), even if it could use a smaller width (but larger height).
* It only works if you already *know* what the parent's size is -- but you might not! Instead, you might simply have a restriction, "the parent's size must be between these two dimensions", but the rest might be open-ended.

I am, however, at a loss of how to come up with a better algorithm -- how do I figure out what would be a good size to to 'propose' to the component? And even when I figure that out, what should I try to optimize, exactly? (The area, the width, the aspect ratio, the number of components on the screen, or something else?)

Any ideas on how I should approach this problem?

# Answer
I've encountered variations of this problem several times doing GUI layout work. Your question about "What should I optimize?" is key to answering your question. Until you've decided that you really can't create a better algorithm.

More than likely you'd like to consider the size-ratios. Each child will have likely a minimum size, possibly a maximum in each dimension, and a preferred ratio, or range of acceptable ratios. You can use this basic data to make a guess as to what the layout should be. Now, for the resulting layout of each child you need a way to produce the preference score.

Now you simply have an optimization problem: maximize the total score of all the children. You can also include global scoring attributes, like the parent size (to cover your second problem). Some layouts you can also reject if they produce invalid results (parent too wide, child not acceptable).

Depending on how many children you have, and how optimal your layout needs to be, will determine how good your algorithm needs to be. For a very simple greedy approach you can simply do line-based. For example, just consider two lines at a time, the current line, and the next line. You should be able to come up with a list of items that easily have enough space on this line, and some that maybe don't. Then just try a few combinations of those trailing components (this line or next) and find a maximum score.
> 3 votes

# Answer
If you're building the components from ground-up, you might never know what the right size is.

This is the classic chicken-egg problem. For flow-layout to work, you need to propagate parent changes to the child. That is the definition of flow-layout.

When you attach a layout to your component, you take on your component's size. When the child is added to the parent, the parent sends it's size to the child's default layout.

Technically, flow layout won't work if even one child's width is greater than the parent's width significantly. You'd then have an option to truncate, or resize.

Most flow layouts work like this: Keep, h = the height of the tallest child in the current row. x, y = moving cursor where children are kept. x keeps getting added by the width of the child, h getting adjusted. When x crosses the width, go to next row, where y is incremented by h. Padding is applicable to x and y.

After this, If width of the child is greater than your width, ask a preferred width option. After this, if the component is too thin, give it the current row height and get it's preferred width again.

You almost always determine the x-y of the child, nothing to do with their size. You should only consider resizing Iff the child goes out of the current whole line.
> 0 votes

---
Tags: algorithms, computational-geometry, greedy-algorithms, user-interface
---


title: Solve a problem through reduction

text:
# Question
Title: Solve a problem through reduction
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).

Let's assume that you have proven that a problem `Y` is NP-Hard, and you have a problem `X` which you know is in NP, and you would like to solve.

To solve `X`, which of the following reductions would be carried out?

1. X -\> Y
2. Y -\> X

Which of the following? i.e. would you reduce `X` to `Y` or vice-versa, if you would like to solve `X` which is in NP, and `Y` which is NP-Hard?

# Answer
> 3 votes
What do you mean by "solve"?

1. Do you want to provide an algorithm for the problem? Then you reduce $X$ to $Y$ and use a supposedly known algorithm $A\_Y$ to solve it. That is, if you have an instance $x$ of $X$ , you use the reduction $f$ to convert it to some instance $y=f(x)$ of $Y$ and then use the algorithm that solves $Y$ on instance $y$. In that way, you have an algorithm with running time $T\_f + T\_{A\_Y}$ for $X$.
2. What if by solve you mean to find out the complexity of $X$, in this case prove that $X$ is $\mathbb{NP}$-hard?

Instead of providing a one-time answer, I would like to show you why this answer holds. As it is common in mathematics and science in general, the level of abstraction you are working on might be helpful, yet it covers some fine details. For example, the intuitive measurement of the resources spent, most notably time, has its basis on a complicated scheme with the purpose to define reductions with some desirable properties.

For polynomial-time reductions, like the ones we use to prove $\mathbb{NP}$-completeness, you can treat reductions as the $\leq$ operator (in mathematical terms, polynomial-time reductions define a partial order. In general, reductions define a preorder). That is, the right hand side is always **at least as hard** as the left hand. At this point of the discussion, I beg you to remember that we compare problems, so in the extreme case that a single instance is hard and the rest easy, this single instance determines the complexity of the entire problem.

Now, we can answer your question. We know that $Y$ is a $\mathbb{NP}$-hard problem and we want to prove that $X$ is **at least as hard** as $Y$. Therefore, thinking in terms of the $\leq$ operator, it is suffices to reduce $Y$ to $X$, that is $Y \leq \_{p} X$. Provided you have that reduction, $X$ is at least as hard as $Y$. And $Y$ is $\mathbb{NP}$-hard, so $X$ must be $\mathbb{NP}$-hard too. By definition, if you can prove that $X \in \mathbb{NP}$, then $X$ is $\mathbb{NP}$-complete.

At the end of this discussion, you might have noticed a problem. The satisfiability problem $SAT$ is $\mathbb{NP}$-complete, yet there exists a simple $O(n)$ nondeterministic time algorithm for it. How can it be as least as hard as any problem in $\mathbb{NP}$? The answer is simple: Polynomial-time differences are not of an interest to us, as we have defined our model. So, the polynomial-time reduction behaves like the $\leq$ operator, though it allows the complexity of the left hand side to be larger up to a polynomial than the running time of the harder problem. This is why we don't use exponential time reductions, since the error margin would be larger than the complexity of the problems themselves (and the definition of the respective classes), making them useless.

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


# Question
Title: Complexity of space density and sequentiality
I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms.

When we measure algorithms we tend to give the big-Oh notation such as $O(n)$ and usually we are measuring time complexity. Somewhat less frequently, though still often, we'll also measure the space complexity of an algorithm.

Given current computing systems however the density of memory and the sequence in which it is accessed plays a major role in the practical performance of the algorithm. Indeed there are scenarios where a time complexity algortihm of $O(\log n)$ with disperse random memory access can be slower than a $O(n)$ algorithm with dense sequential memory access. I've not seen these aspects covered in formal theory before; surely it must exist and I'm just ignorant here.

What are the standard metrics, terms, and approaches to this space density and access sequentiality?

# Answer
> 4 votes
There are a few models that take into account the number of memory transfers an algorithm makes. One of the most successful ones is the cache-ideal model introduced by Frigo et al, Cache-oblivious algorithms, 1999. It is based on the external memory model introduced by Aggarwal and Vitter, The Input/Output Complexity of Sorting and Related Problems, 1988. The notes by Demaine give a nice, readable overview of the model and of some of the algorithms and data structures out there. Alternatively, check out the chapter on cache-oblivious data structures in the Handbook of Data Structures and Applications. If you prefer videos, Demaine covers all the basics and perhaps even more on the MIT Introduction to Algorithms lectures.

The model assumes no knowledge of the number of levels in the memory hierarchy. In addition, there are no parameters such as cache-line length or cache size to configure. One property is that if an algorithm performs optimally in the cache-ideal model, it performs optimally on any $k$-level memory hierarchy. Furthermore, algorithms that do perform optimally in the model are called cache-oblivious. They offer the advantages of simplicity, robustness and portability over the cache-aware algorithms, whose resource usage must be managed explicitly.

The ideal-cache model has two complexity measures. The first one is work complexity, that is the conventional running time of an algorithm in the RAM model. The second one comes from the external memory model, that is the number of memory transfers. The ideal-cache model however modifies the external memory model in a few ways. It has a optimal block replacement strategy, automatic replacement and full associativity. All of these assumptions are justified by a collection of reduction by Frigo et al.

Algorithms and data structures are then analyzed in the model. For example, consider the classic binary search. The runtime leads to a recurrence

$$T(N) = T(N/2) + O(1).$$

Looking at the recursion tree, each level attributes an $\log N$ factor yielding the solution of $\Theta(\log N)$. When analyzing algorithms in the RAM model, we often assume the base case of $T(1)=O(1)$ for our recurrences. However, in the cache-ideal model we often let the algorithm divide the problem all the way, but consider the point at which the problem either fits the cache or fits in $O(B)$ number of memory blocks. In fact here, we can we can improve on our analysis by using a stronger base case of $T(O(B))=O(1)$. With this, the classic binary search incurs $\Theta(\log N - \log B)$ memory transfers. What is more, the classic binary search is *not* optimal the in cache-ideal model. There are more clever ways needed to achieve the optimal $\Theta(\log\_B N)$ bound.

I guess the success of the model comes from the fact that it is easy and fun to work with, and it also works in practice, meaning it has been fairly effective at predicting the costs of an algorithm on real systems. There are a lot of cache-oblivious algorithms and data structures. For example, we have cache-oblivious algorithms for many problems in computational geometry, scanning of dynamic sets, bioinformatics, stencil computations, linear algebra, suffix array construction and for some fundamental graph problems using cache-oblivious priority queues. The main techniques that are effective are linear scanning of memory and divide-and-conquer.

In practice, the overall conclusion has been such that cache-oblivious algorithms often outperform RAM algorithms. However, the cache-aware algorithms are usually even faster, since they are tuned for a specific problem size and memory hierarchy. For a nice example see Ladner et al., A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002.

---
Tags: complexity-theory, reference-request, terminology, space-complexity
---


# Question
Title: Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?
Let $C$ be a non-trivial set of recursively enumerable languages ($\emptyset \subsetneq C \subsetneq \mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language in $C$: $$L=\\{\langle M \rangle \mid L(M) \in C \\}$$

Suppose that $\langle M\_{loopy}\rangle \in L$, where $M\_{loopy}$ is a TM that never halts. I wonder if it is possible that $L \in \mathrm{RE}$?

By Rice's theorem I know that $L \notin \mathrm{R}$ (the set of recursive languages), so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$. Does it have to be the first option since $M\_{loopy} \in L$?

# Answer
No, that is not possible. There is an extended version of Rice's theorem¹ to prove an index set is not recursively enumerable.

In your notation, the theorem states that if a (non-trivial) $C$ contains a language $L\_1$ which has a proper superset $L\_2$ *not* in $C$, then $L \notin \mathrm{RE}$. The intuition is that no algorithm can separate encodings of $L\_1$ and $L\_2$; they can not decide that the encoded machine does *not* accept any word from $L\_2 \setminus L\_1$ after a finite amount of time, which they had to.

Now you require $\emptyset \in C$ but $C \neq 2^{\Sigma^\*}$, therefore the theorem applies and $L$ is not recursively enumerable.

---

1. The Wikipedia article is horrible, beware!
> 3 votes

# Answer
to complete Raphael's answer, there is an extension of Rice's theorem that says the following:

> # Generalized Rice's Theorem
>
> Let $S \subseteq RE$ be some property, and let $L\_S$ be all the TMs that satisfy the property $S$, that is, $$L\_S = \\{ \langle M \rangle \mid L(M) \in S \\}.$$ Then, $L\_S \in RE$ if and only if *all* the following conditions hold:
>
> 1. for any $L\_1,L\_2 \in RE$, if $L\_1 \in S$ and $L\_1 \subseteq L\_2$ then $L\_2 \in S$.
> 2. if $L\_1\in S$ then there exists a finite $L\_2 \subseteq L\_1$ such that $L\_2 \in S$.
> 3. The language of 'all finite languages in $S$' is in RE.
> (in other words, there exists a TM $M\_S$ that, if $L$ is a finite language $L=\\{w\_1, w\_2, \ldots w\_k)$, and $(w\_1, w\_2, \ldots, w\_k)$ is given to $M\_S$ as an input, $M$ accepts only if $L\in S$.

Now back to the original question. We now that $\langle M\_{loopy}\rangle\in L$ so $L(\langle M\_{loopy}\rangle)\in C$. But $L(\langle M\_{loopy}\rangle)=\emptyset$ since this TM never halts. This means that $\emptyset \in C$.

Now lets look on the first condition of the above theorem. **ANY** language $L$ satisfies $\emptyset \subseteq L$. Thus in order to satisfy condition 1, it must be that $C=RE$. However, the question states that $C\subsetneq RE$ and therefore, by the theorem, $L\notin RE$.
> 4 votes

# Answer
It is possible that $L$ is an r.e. set. Consider the case $C = RE$. Then $L$ is the set of all codes of all Turing machines. This is a recursive set, in fact, depending on the details of the encoding, we could have $L = \mathbb{N}$. So it is actually false that $L$ cannot be recursive.

I suspect you misformulated the question.
> 0 votes

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


# Question
Title: How can a TM M' have a property P if it only accepts a single string x from language of P?
Here is the document: More Undecidable Problems

For a given property $P$ of languages, define $L\_P$ as the set of all Turing machines (resp. their encodings) that accept languages with $P$, that is

$\qquad \displaystyle L\_{p} = \\{ ⟨M⟩ \mid \mathcal{L}(M) \text{ has property } P \\}$

If $P$ is a trivial property, that is if $P$ holds for all or no language, $L\_P$ is decidable, too (as $L\_P=\emptyset$ or $L\_P = \\{\langle M\rangle \mid M \text{ Turing machine }\\}$. If $P$ is not trivial, $L\_p$ is undecidable (by Rice's theorem), which means the strings in this language (or with such property) cannot be determined if it can be halt.

We determine a language $M$ has property $P$ by reduce $M$ to another $M'$, and check that if $M'$ accepts the reduced string $x$ from the initial string $w$, we can conclude that $L(M)$ and $L(M')$ have property $P$.

However, as the title suggests, we only reduce a single string $w$ to $x$ and if $x$ is accepted, but we conclude the whole $L(M')$ has property $P$. Thus, $M'$ is obviously part of $L\_p$. *What if some random strings in $L(M')$ do not have property $P$?*

*What if M accepts some string, but the reduction of those strings are not accepted by M'?*

A reduction from language $L$ to language $L’$ is an algorithm (TM that always halts) that takes a string $w$ and converts it to a string $x$, with the property that: **$x$ is in $L’$ if and only if $w$ is in $L$**.

*Does this imply the reduced language $L'$ will contain every property $P$ from $L$?* Since we can conclude that if $L'$ is decidable, then $L$ is decidable as well and vice verse. *Can we conclude the same thing to property $P$?*

# Answer
I think I got it. Here is Rice's Theorem (Rice Theorem and Turing machine b ehavior prop erties):

I looked it up here: Decidability for the definition of a problem in the context of Turing Machine (slides 9 and 11):

> * Formally, a problem is a language.
> * Each string encodes some instance.
> * The string is in the language if and only if the answer to this instance of the problem is “yes.”
>
> A problem is decidable if there is an algorithm to answer it.
>
> * Recall: An “algorithm,” formally, is a TM that halts on all inputs, accepted or not.
> * Put another way, “decidable problem” = “recursive language.”
>
> Otherwise, the problem is undecidable

That answers why I only need one string w and reduced x from w to prove a language L with property P is undecidable.

According to Rice's Theorem, if language L with property P has Turing Machines that does not accept language of L, L is undecidable. Thus:

$$L\_{p} = \\{ L(M\_{0}), L(M\_{1}), L(M\_{2}),..., L(M\_{n})\\}$$ $$L'\_{NotInp} = \\{ L(M\_{0}), L(M\_{1}), L(M\_{2}),..., L(M\_{n}) \\}$$

$$M\_{i}\mspace{8mu} \text{is}\mspace{8mu} \text{an}\mspace{8mu} i\text{th}\mspace{8mu} \text{Turing} \mspace{8mu} \text{machine},\mspace{8mu} i ≤ n. $$

If the language L' (which contains TMs not in P) is not an empty set, the above L sub P is undecidable. Recall that language with property P is decidable if and only if it is trivial, which means either it contains every RE languages or not at all. Since if a language L with property P is decidable, every Turing Machines accept every string in L, so we don't need to test the acceptance of input to a given TM.

Also, according to the definition of a problem in the context of Turing Machine, if we have the answer (an algorithm) to every instance of the language L sub P (obviously, since L sub P contains every TM), L sub P is decidable. Otherwise, it's not.

Let's be more concrete with an example from here: More Reduction Examples

Aside from the proof given on the page, let's look at it more intuitively. We may have Turing Machine M which accepts the three strings. Other than that, the input w can be anything which is not in M, but belong to other M'. Input w can be "Not UIUC", "Not Iowa", or "Not Michigan" or any other strings which do not belong to M. Since we do not have the answer to every instance of the problem with M (because if we do, M will accept every string since every string has property P. In this case, it's not). The language is not trivial, thus it is undecidable.

This is my reasoning. What do you think?
> 1 votes

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


# Question
Title: Is the following recurrence for this program's runtime correct?
Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:

```
Recurs(v,p) :
  find s < v such that f(s,v) < v/2 and g(s,v-s) < p

  if no such s exists then
    return v
  else if s <= v/4 then
    return v-s U Recurs(s,p)
  else if s > v/4 then
    return Recurs(s,p) U Recurs(v-s,p)
end

```

Can the recurrence for the running time of this recursion be $T(v)=T\left(\frac{v}{4}\right)+T\left(\frac{3v}{4}\right)+1$?

# Answer
**tl;dr: NO. Well, okay, maybe.**

Translating the pseudocode mechanically into a recurrence gives me $$ T(n) = \Theta(1) + F(n) + \max \begin{cases} \max\_{0\le s \le n/4} T(s) \\ \\ \max\_{n/4 \< s \< n} (T(s) + T(n-s)) \end{cases} $$ where $F(n)$ is the time for the first "find" step. Every outcome that is not known in advance is folded into the $\max$; since we're bounding the worst-case running time, we always assume the worst possible outcome. The initial $\Theta(1)$ includes all the time for bookkeeping, comparisons, stack manipulation, and that union operation in the output. (Performing a set union in constant time is somewhat magical, but I'll let that slide.) I'm also assuming here that the variable $s$ always lies between $0$ and $v-1$, since otherwise the algorithm never terminates, although this assumption is never specified in the code.

Under the reasonable assumption that $T(n)$ is monotonically increasing, we have $$ \max\_{0\le s \le n/4} T(s) = T(n/4) $$ Under the further assumption that $T(n)$ is "nice" and convex, we have $$ \max\_{n/4 \< s \< n} (T(s) + T(n-s)) = \begin{cases} T(n-1) + T(1) & \text{if $T$ is convex}\\ T(n/4+1) + T(3n/4-1) & \text{if $T$ is concave} \end{cases} $$ Here, "convex" means that $(T(a) + T(b))/2 \ge T((a+b)/2)$ for all $a$ and $b$, or less formally, that the function "curves upward". If $T$ is "nice", this is equivalent to assuming $T(n) = \Omega(n)$. Symmetrically, $T$ is concave (curves downward) iff $T(n) = O(n)$.

("Nice" means a function whose second derivative is well-defined and doesn't oscillate between positive and negative forever; for example, the product of a polynomial and some logarithms is nice. Wacky functions like $n^{2 + \sin(2\pi n)}$ are not nice, but I'll bet you a dollar that your algorithm doesn't have that function as a time bound.)

So our recurrence is now $$ T(n) = \Theta(1) + F(n) + \max\begin{cases} T(n/4) \\ T(n-1) + T(1) \\ T(n/4 + 1) + T(3n/4 - 1) \end{cases} $$ If $T$ is increasing, the first case is smaller than the other two, so we can ignore it. So we have two possibilities to consider.

First, suppose $$ T(n) = \Theta(1) + F(n) + T(n-1) $$ (I folded the extra $T(1)$ into the $\Theta(1)$ term.) This recurrence unrolls into a simple summation $$ T(n) = \Theta(n) + \sum\_{i=1}^n F(i) $$ which implies that $T(n)$ is convex no matter what function $F(n)$ is. So this recurrence seems to work. (The apparently circular argument about convexity can be unwound into a boring and mechanical proof by induction, if you care.)

On the other hand, suppose $$ T(n) = \Theta(1) + F(n) + T(n/4 + 1) + T(3n/4 - 1). $$ Then even with the *very* strong assumption that $F(n) = O(1)$, a quick recursion tree argument implies that $T(n) = \Theta(n)$. The same recursion tree argument implies that if $F(n)$ is grows even slightly faster than a constant, then $T(n)$ is strictly convex, which means this is the wrong recurrence.

So this recurrence only works when $F(n) = O(1)$. In that case, we can simplify the recurrence further to $$ T(n) = \Theta(1) + T(n/4 + 1) + T(3n/4 - 1). $$ We still have those pesky off-by-ones in the recursive arguments, but whatever. We've already figured out that $T(n) = \Theta(n)$, so who cares about the recurrence any more?
> 4 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Expression Problem – looking for a similar standard problem
The Expression Problem, populated by Philip Wadler, is a often used to standard problem to evaluate programming languages.

I think it is a very clear and popular example and I wonder if there are any similar standard problems that are possibly also as widely used and as clear.

So, are there any similar standard problems?

(In the case of Feature Oriented Programming (link link) I found some standard problems, like: \- implementation of a stack with different features \- implementation of linked lists \- implementation of a calculator \- the graph product line \- stock broker and bank account examples \- hierarchical display )

# Answer
> 2 votes
I'm not sure that the problem is formulated quite as nicely, but the problem of implementing concurrency in an efficient manner has occupied at least as much effort as the expression problem, and prompted a number of solutions, including the use of semaphores and software transactional memory.

I'm certainly not an expert, but I believe the problem of concurrency can be formulated in a similar manner to the expression problem: create language constructs which allow us to simultaneously:

1. Have sufficient expressivity to create complex concurrent programs, say, a web server.
2. Be able to have a reasonable assurance that these complex programs will not incur deadlock.

---
Tags: reference-request, programming-languages, software-engineering
---


# Question
Title: Machine learning algorithm to play Connect Four
I'm currently reading about machine learning and wondered how to apply it to playing Connect Four.

My current attempt is a simple multiclass classificator using a sigmoid function model and the one-vs-all method.

In my opinion, the input features have to be the state (disc of player 1, disc of player 2, empty) of the 7x6=42 grid fields.

The output would be the number of the row to put the disc into. Because that is a discrete number between 1 and 7, I guess this can be treated as a multiclass classification problem.

But how do I generate training examples usable in supervised learning?

The main goal is to win the game but the outcome obviously isn't known when doing every but the last turn. If I just let two players who decide randomly what to do play against each other thousands of times, will it be sufficient to simply take all turns made by the winner of each game round as training examples? Or do I have to do this in a completly different way?

**Edit: As suggested in the comments I read a little about reinforcement learning.** From what I know understand, Q-Learning should do the trick, i.e. I have to approximate a function Q of the current state and the action to take to be the maximum cumulative reward beginning in that state. Then each step would be to choose the action which results in the maximum value of Q. However, this game has way too many states in order to do this e.g. as a lookup table. So, what is an effective way to model this Q-Function?

# Answer
Just to offer a simpler alternative to reinforcement learning, you can use the basic minimax algorithm to search for good moves, and use machine learning to evaluate board positions.

To clarify, minimax builds a game tree where each node is labeled with the outcome from the leaves up (1=player A wins, 0=player B wins), assuming that A chooses the moves that maximize this number, and B chooses the moves that minimize it.

Unless the game is very simple, you won't be able to construct the whole game tree down to the terminals. You'll instead need to stop at unfinished board positions and evaluate the leaves with some heuristic (essentially the probability that player A will win from the given position). You can let a machine learning algorithm like a neural network try to learn this probability from connect four positions with known outcomes.

To generate training examples you could build your minimax player with a simple heuristic, let it play itself a thousand times, use those games to train your first neural network, then let that pay itself a thousand games and so on. With a little luck, your system will improve with each generation.
> 8 votes

# Answer
I wrote a blogpost about using minimax to play connect four a while ago. You can see the code in action here. If you need to train your models, you can perhaps let it play a couple of thousand games against my minimax implementation.
> 2 votes

---
Tags: machine-learning, board-games
---


# Question
Title: Can exactly one of NP and co-NP be equal to P?
Maybe I am missing something obvious, but can it be that P = co-NP $\subsetneq$ NP or vice versa? My feeling is that there must be some theorem that rules out this possibility.

# Answer
> 14 votes
No, because $\mathsf{P}$ is closed to complement this cant be, and we even know that $\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$.

Let us assume that $\mathsf{P}=\mathsf{NP}$, and let $L \in \mathsf{co\text{-}NP}$, thus $L^c \in \mathsf{NP}$. We assumed $\mathsf{P}=\mathsf{NP}$, and therefore there exists a TM $M$ s.t. $L(M)=L^c$. If we take the "complement" of $M$, that is a machine $M'$ which is identical to $M$ except its accept and reject states are reversed, we get that $L(M')=(L^c)^c=L$, and thus $L$ is in $\mathsf{NP}$.

This shows that, under the assumption that $\mathsf{P}=\mathsf{NP}$, we get $(\mathsf{P}=)\mathsf{NP}=\mathsf{co\text{-}NP}$ and thus $\mathsf{P}=\mathsf{co\text{-}NP}$.

# Answer
> 9 votes
$\mathsf{P}$ is closed under complement (i.e. $\mathsf{P}=\mathsf{co\text{-}P}$ ¹); so if $\mathsf{P}=\mathsf{co\text{-}NP}$ (or $\mathsf{P}=\mathsf{NP}$) then $\mathsf{co\text{-}NP} = \mathsf{NP}$

---

1. Given a language $L \in \mathsf{P}$, we can construct a deterministic TM' that decides $\overline L$ in polynomial time simply by taking the TM that decides $L$ and ...

---
Tags: complexity-theory, p-vs-np
---


title: Type inference with product types

text:
# Question
Title: Type inference with product types
I’m working on a compiler for a concatenative language and would like to add type inference support. I understand Hindley–Milner, but I’ve been learning the type theory as I go, so I’m unsure of how to adapt it. Is the following system sound and decidably inferable?

A term is a literal, a composition of terms, a quotation of a term, or a primitive.

$$ e ::= x \\:\big|\\: e\\:e \\:\big|\\: \[e\] \\:\big|\\: \dots $$

All terms denote functions. For two functions $e\_1$ and $e\_2$, $e\_1\\:e\_2 = e\_2 \circ e\_1$, that is, juxtaposition denotes reverse composition. Literals denote niladic functions.

The terms other than composition have basic type rules:

$$ \dfrac{}{x : \iota}\text{\[Lit\]} \\ \dfrac{\Gamma\vdash e : \sigma}{\Gamma\vdash \[e\] : \forall\alpha.\\:\alpha\to\sigma\times\alpha}\text{\[Quot\]}, \alpha \text{ not free in } \Gamma $$

Notably absent are rules for application, since concatenative languages lack it.

A type is either a literal, a type variable, or a function from stacks to stacks, where a stack is defined as a right-nested tuple. All functions are implicitly polymorphic with respect to the “rest of the stack”.

$$ \begin{aligned} \tau & ::= \iota \\:\big|\\: \alpha \\:\big|\\: \rho\to\rho \\ \rho & ::= () \\:\big|\\: \tau\times\rho \\ \sigma & ::= \tau \\:\big|\\: \forall\alpha.\\:\sigma \end{aligned} $$

This is the first thing that seems suspect, but I don’t know exactly what’s wrong with it.

To help readability and cut down on parentheses, I’ll assume that $a\\:b = b \times (a)$ in type schemes. I’ll also use a capital letter for a variable denoting a stack, rather than a single value.

There are six primitives. The first five are pretty innocuous. `dup` takes the topmost value and produces two copies of it. `swap` changes the order of the top two values. `pop` discards the top value. `quote` takes a value and produces a quotation (function) that returns it. `apply` applies a quotation to the stack.

$$ \begin{aligned} \mathtt{dup} & :: \forall A b.\\: A\\:b \to A\\:b\\:b \\ \mathtt{swap} & :: \forall A b c.\\: A\\:b\\:c \to A\\:c\\:b \\ \mathtt{pop} & :: \forall A b.\\: A\\:b \to A \\ \mathtt{quote} & :: \forall A b.\\: A\\:b \to A\\:(\forall C. C \to C\\:b) \\ \mathtt{apply} & :: \forall A B.\\: A\\:(A \to B) \to B \\ \end{aligned} $$

The last combinator, `compose`, ought to take two quotations and return the type of their concatenation, that is, $\[e\_1\]\\:\[e\_2\]\\:\mathtt{compose} = \[e\_1\\:e\_2\]$. In the statically typed concatenative language Cat, the type of `compose` is very straightforward.

$$ \mathtt{compose} :: \forall A B C D.\\: A\\:(B \to C)\\:(C \to D) \to A\\:(B \to D) $$

However, this type is too restrictive: it requires that the production of the first function *exactly match* the consumption of the second. In reality, you have to assume distinct types, then unify them. But how would you write that type?

$$ \mathtt{compose} :: \forall A B C D E. A\\:(B \to C)\\:(D \to E) \to A \dots $$

If you let $\setminus$ denote a *difference* of two types, then I *think* you can write the type of `compose` correctly.

$$ \mathtt{compose} :: \forall A B C D E.\\: A\\:(B \to C)\\:(D \to E) \to A\\:((D \setminus C)\\:B \to ((C \setminus D)\\:E)) $$

This is still relatively straightforward: `compose` takes a function $f\_1 : B \to C$ and one $f\_2 : D \to E$. Its result consumes $B$ atop the consumption of $f\_2$ not produced by $f\_1$, and produces $D$ atop the production of $f\_1$ not consumed by $f\_2$. This gives the rule for ordinary composition.

$$ \dfrac{\Gamma\vdash e\_1 : \forall A B.\\: A \to B \quad \Gamma\vdash e\_2 : \forall C D. C \to D}{\Gamma\vdash e\_1 e\_2 : ((C \setminus B)\\:A \to ((B \setminus C)\\:D))}\text{\[Comp\]} $$

However, I don’t know that this hypothetical $\setminus$ actually corresponds to anything, and I’ve been chasing it around in circles for long enough that I think I took a wrong turn. Could it be a simple difference of tuples?

$$ \begin{align} \forall A. () \setminus A & = () \\ \forall A. A \setminus () & = A \\ \forall A B C D. A B \setminus C D & = B \setminus D \textit{ iff } A = C \\ \text{otherwise} & = \textit{undefined} \end{align} $$

Is there something horribly broken about this that I’m not seeing, or am I on something like the right track? (I’ve probably quantified some of this stuff wrongly and would appreciate fixes in that area as well.)

# Answer
> 9 votes
The following rank-2 type $$\text{compose}:\forall ABC\delta. \delta\ (\forall \alpha.\alpha\ A\to \alpha B)\ (\forall \beta.\beta\ B\to \beta C) \to \delta\ (\forall \gamma.\gamma\ A\to \gamma C)$$ seems to be sufficiently general. It is much more polymorphic than the type proposed in the question. Here variable quantify over contiguous chunks of stack, which captures multi-argument functions.

*Greek letters are used for the rest-of-the-stack variables for clarity only.*

It expresses the constraints that the output stack of the first element on the stack needs to be the same as the input stack of the second element. Appropriately instantiating the variable $B$ for the two actually arguments is the way of getting the constraints to work properly, rather than defining a new operation, as you propose in the question.

Type checking rank-2 types is undecidable in general, I believe, though some work has been done that gives good results in practice (for Haskell):

* Simon L. Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields: Practical type inference for arbitrary-rank types. J. Funct. Program. 17(1): 1-82 (2007)

The type rule for composition is simply:

$$ \dfrac{\Gamma\vdash e\_1:\forall \alpha. \alpha\ A\to \alpha\ B\qquad \Gamma\vdash e\_1:\forall \alpha. \alpha\ B\to \alpha\ C} {\Gamma\vdash e\_1\ e\_2:\forall \alpha.\alpha\ A\to\alpha\ C} $$

To get the type system to work in general, you need the following specialisation rule:

$$ \dfrac{\Gamma\vdash e:\forall \alpha. \alpha\ A \to \alpha\ B} {\Gamma\vdash e:\forall \alpha.C\ A\to \alpha\ C\ B} $$

---
Tags: programming-languages, logic, compilers, type-theory, type-checking
---


# Question
Title: What's the difference between a bridge, a mediator and a wrapper?
The slides from my course in software architecture hints that these are seperate terms, but I can't seem to find the difference. Aren't all of them just translating interfaces?

# Answer
> 8 votes
It was very common for early patterns research to put a lot of emphasis on the "intended use" of a pattern, over and above any structural differences in the implementation. Then, people who were at that stage of architectural maturity where they were "doing patterns because patterns is what you do" developed long, often elaborate explanations on why these alleged differences were important.

However, research has shown that the structure is really all that matters, because the semantic distinctions:

* have no formal distinctions, even in the mathematical treatment of type theory
* are not enforceable without syntactic differences in developing the type relations (compiler needs something to enforce)
* therefore change with changing requirements
* and should not be forced not to change, as reuse is the point of good architecture

So much of those large discussions on why strategy is different than state have turned out quite labored, unconvincing, ineffectual, and slightly humorous as the years have moved on.

My suggestion is to ignore any "is used for" discussion at all and completely focus on the type relationships. If you do that, then you will find that (depending on your particular definition of these patterns, but fairly standard here)

Mediator \> Bridge \> Adapter

where the \> relation should be read as "is implemented using". Adapter is a functional relationship between three or more types around on one abstraction tree. Bridge and Mediator are functional relationship between four or more types around two abstraction trees, defining an interface between the abstraction trees. Mediator adds to the type coupling usage relationships between concrete nodes of the abstraction trees.

Typically, Mediator is a bad pattern (antipattern) that doesn't scale well and causes an application to become monolithic. It is used very frequently because people read what it does and go "oh, I need that" and use a pattern becasue, as above, well, patterns are "what you use". They may be an intermediate step while decoupling a heavily coupled application during refactoring, but typically if you are making that step, full decouple to Bridge (with a factory) is indicated and just as easy.

# Answer
> 6 votes
Generally there are *a lot* of notions of interfaces in computer science. You should probably say that you are talking about about design patterns. In the corresponding Wikipedia article, there is a classification of different patterns that clears things up:

* The mediator pattern is behavioral (about communication between interfaces) and unifies several interfaces, notably their way of communicating together much like an actual mediator.
* The other two are structural (actually comparing interfaces):

+ the wrapper/adapter pattern is focused on making an interface compatible, for example if a client uses different conventions;
    + the bridge pattern is about separating what the class is supposed to do (abstraction) from how it actually does it (implementation). That way you can use the abstraction without knowing how it is implemented, which is useful when the code changes (for both sides).

# Answer
> 5 votes
There are differences. Most of them are subtle enough that you wouldn't care, but they generally differ either in intent or in implementation. The overarching idea is to provide class A with access to the functionality of class B, without A having to care that it's B doing the work (so that a class C can be substituted without any of these objects having to change). This idea is typically called "loose coupling" and is generally to be encouraged..

* A Bridge is the most basic definition of the intent to decouple A and B; that, in and of itself, is the purpose. A instead knows about an interface I, which B implements. A class C can also implement I and can be substituted freely.
* A "wrapper" or Adapter is typically written with the intention of changing the interface of B to match the set of functionality that A expects of its dependency I. If A expects I to have a "DoThis()" method with three parameters, but the method with the functionality A needs on B is actually named "DoThat()" and takes a parameter, an Adapter W can be written that is dependent on B (or B's interface IB), implements I, and calls B.DoThat() from its own DoThis() method (passing the parameter, which it can gain without A's knowledge). If C is needed instead and differs from B, a different Adapter W2 can be written which takes a C and also implements I, so A, W, I, B, and C don't have to change.
* Mediator patterns are basically an Adapter used as a Bridge. A Mediator is its own object M, which knows about B and is given to A. When A calls methods on M, those calls are passed through to B. M may do additional things, such as providing two-way communication between A and B. B may be required to change A's data or call its members, but cannot know about A itself. M may resolve this "circular" or "many to many" dependency structure by allowing both A and B to depend on M.

---
Tags: terminology, software-engineering
---


# Question
Title: Is computational power of Neural networks related to the activation function
It is proven that neural networks with rational weights has the computational power of the Universal Turing Machine Turing computability with Neural Nets. From what I get, it seems that using real-valued weights yields even more computational power, though I'm not certain of this one.

However, is there any correlation between the computational power of a neural net and its activation function? For example, if the activation function compares the input against a limit of a Specker sequence (something you can't do with a regular Turing machine, right?), does this make the neural net computationally "stronger"? Could someone point me to a reference in this direction?

# Answer
> 15 votes
Just a note:

* rational-weighted recurrent $NN$s having boolean activation functions (simple thresholds) are equivalent to finite state automata (Minsky, "Computation: finite and infinite machines", 1967);
* rational-weighted recurrent $NN$s having linear sigmoid activation functions are equivalent to Turing Machines (Siegelmann and Sontag, "On the computational power of neural nets", 1995);
* real-weighted recurrent $NN$s having linear sigmoid activation functions are more powerful than Turing Machines (Siegelmann and Sontag, "Analog computation via neural networks", 1993);

but ...

# Answer
> 5 votes
I'm going to take the easy solution and say "Yes". Consider an activation function which accepts any inputs and simply returns a constant value (that is, it ignores the inputs). This network always results in a constant output, and thus the computational power (likely by any definition) of this network is zero. It is not capable of calculating anything.

This is enough to show a correlation between the activation function on the the *power* of the network. It of course does not show, nor disprove, that a network could have more *power* than a universal turing machine.

---
Tags: computability, neural-networks
---


# Question
Title: Generating number of possibilites of popping two stacks to two other stacks
Context: I'm working on this problem:

> There are two stacks here:
>
> ```
> A: 1,2,3,4 <- Stack Top
>   B: 5,6,7,8
>
> ```
>
> A and B will pop out to other two stacks: C and D. For example:
>
> ```
>  pop(A),push(C),pop(B),push(D).
>
> ```
>
> If an item have been popped out , it must be pushed to C or D immediately.

The goal is to enumerate all possible stack contents of C and D after moving all elements.

More elaborately, the problem is this: If you have two source stacks with $n$ unique elements (all are unique, not just per stack) and two destination stacks and you pop everything off each source stack to each destination stack, generate all unique destination stacks - call this $S$.

The stack part is irrelevant, mostly, other than it enforces a partial order on the result. If we have two source stacks and one destination stack, this is the same as generating all permutations without repetitions for a set of $2N$ elements with $N$ 'A' elements and $N$ 'B' elements. Call this $O$.

Thus

$\qquad \displaystyle |O| = (2n)!/(n!)^2$

Now observe all possible bit sequences of length 2n (bit 0 representing popping source stack A/B and bit 1 pushing to destination stack C/D), call this B. |B|=22n. We can surely generate B and check if it has the correct number of pops from each destination stack to generate |S|. It's a little faster to recursively generate these to ensure their validity. It's even faster still to generate B and O and then simulate, but it still has the issue of needing to check for duplicates.

My question

Is there a more efficient way to generate these?

Through simulation I found the result follows this sequence which is related to Delannoy Numbers, which I know very little about if this suggests anything.

Here is my Python code

```
def all_subsets(list):
    if len(list)==0:
        return [set()]
    subsets = all_subsets(list[1:])

    return [subset.union(set([list[0]])) for subset in subsets] + subsets

def result_sequences(perms):
    for perm in perms:
        whole_s = range(len(perm))
        whole_set = set(whole_s)
        for send_to_c in all_subsets(whole_s):
            send_to_d = whole_set-set(send_to_c)
            yield [perm,send_to_c,send_to_d]

n = 4
perms_ = list(unique_permutations([n,n],['a','b'])) # number of unique sequences
result = list(result_sequences(perms_))

```

# Answer
> 2 votes
(answer for another problem, see the edit below)

First, generate all subsets $A\_1$ of $A$. $A\_1$ will go in $C$ and $A\_2=A\backslash A\_1$ in $D$. Likewise, generate all subsets $B\_1$ of $B$. You then have to generate all possible ordered combinations of $A\_1$ and $B\_1$ for $C$ and the same for $A\_2$ and $B\_2$ in $D$.

This amounts to enumerate, given $(a\_1,…,a\_n)$ and $(b\_1,…,b\_m)$ all interleavings of length $n+m$ which can be viewed as an exploration of the intersections of a grid of size $n×m$. (There are $\frac{(n+m)!}{n!m!}$ paths)

This is a way of generating all possible $C$s and $D$s uniquely.

But maybe I misunderstood the question. Is this what you want? To help comparing with what you already have tried, here is the number of pairs of stacks it generates (where $A$ is the *size* of $A$):

$$N(A,B)=\sum\_{n=0}^{A}\sum\_{m=0}^{B}\binom{A}{n}\binom{B}{m}\frac{(n+m)!}{n!m!}\frac{(A+B-n-m)!}{(A-n)!(B-m)!}$$

EDIT: I am wrong: my algorithm behaves like separating $A$ and $B$ into $(A\_1,A\_2)$ and $(B\_1,B\_2)$ before interleaving $(A\_1,B\_1)$ and $(A\_2,B\_2)$ which is presumably what you don't want (it generates too many stacks, e.g. from $A=\[2,1\], B=\[4,3\]$ it includes $C=\[2,3\],D=\[4,1\]$).

(Mitchus's answer does not have this problem.)

# Answer
> 2 votes
It seems to me that an efficient way to enumerate those sequences is simply by constructing all possible stacks recursively. See Python example below (n.b. my stacks have the top on the right-hand side).

```
def enumerate_stacks(A, B, C=[], D=[], seq=[]):
    if len(A)+len(B) == 0:
        print seq, C, D
    else:
        if len(A)>0:
            enumerate_stacks(A[1:], B,     [A[0]]+C, D       , seq + [0,0])
            enumerate_stacks(A[1:], B,     C,        [A[0]]+D, seq + [0,1])
        if len(B)>0:
            enumerate_stacks(A,     B[1:], [B[0]]+C, D       , seq + [1,0])
            enumerate_stacks(A,     B[1:], C,        [B[0]]+D, seq + [1,1])

A = [2,1]
B = [4,3]

enumerate_stacks(A,B)

```

---
Tags: algorithms, combinatorics, efficiency
---


# Question
Title: per-record timeline consistency vs. monotonic writes
It seems to me that the *per-record timeline consistency* as defined by Cooper et al. in "PNUTS: Yahoo!’s Hosted Data Serving Platform" mimics the (older?) definition of *monotonic writes*. From the paper:

> per-record timeline consistency: all replicas of a given record apply all updates to the record in the same order.

This is quite similar to a definition for monotonic writes:

> A write operation by a process on data item x is completed before any successive write operation on x by the same process.

Can I conclude that those things are the same, or is there a difference that I misunderstand? Note that the link above also mentions possible copies of data item `x`, so monotonic write includes replicas.

# Answer
> 1 votes
I'm not sure these two concepts are really comparable.

*monotonic writes* is a client based consistency model. It defines what a process sees.

*per-record timeline consistency* strikes me as a memory based model. It doesn't even mention what a client sees or does.

So I would say they are not same or even comparable.

---
Tags: terminology, distributed-systems
---


title: Restricted version of vertex cover

text:
# Question
Title: Restricted version of vertex cover
I am interested in the complexity of the restricted version of the vertex cover problem below:

> **Instance:** A bipartite graph $G =(L, R, E)$ and an integer $K$.
>
> **Question:** Is there $S \subset L$, $|S| \leq K$ and every vertex in $R$ has a neighbor in $S$ $( S$ is vertex cover for $R)$

Vertex cover is $\mathsf{P}$ if $S \subset L \cup R$ and cover $L \cup R$; and it is $\mathsf{NP}$-complete for nonbipartite graphs. However, the problem I am looking at does not fit in either cases. Any pointers where I could find an answer will be appreciated.

# Answer
Let us call your problem as $\mathsf{RESVC}$. $\mathsf{RESVC}$ is NP-Complete.

* Given a subset $S \in L$ its easy to verify in poly. time whether it forms a valid cover of size k. Hence, $\mathsf{RESVC} \in \mathsf{NP}$
* $\mathsf{RESVC}$ is also NP-hard because the decision version of the *Minimum Dominating set problem* reduces to it. And, we know that the decision version of Minimum Dominating set is NP-complete. The reduction goes as follows:

$\qquad \displaystyle \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET} = \\{ \langle G,k \rangle : G \text{ has a dominating set } S \text{ s.t. } |S| \leq k \\}$

Reduce the instance $\langle G,k \rangle$ of above language to $\langle G',k \rangle$ as follows:

Lets say $G = (V,E)$ and $V = \\{v\_1,v\_2,\dots,v\_n\\}$ and define $G' = (L \cup R, E')$ with

+ $L = \\{v\_{11},v\_{21},...,v\_{n1}\\}$
    + $R = \\{v\_{12},v\_{22},...,v\_{n2}\\}$
    + $E' = \\{(v\_{i1},v\_{j2}) : (v\_i,v\_j) \in E \vee (v\_j,v\_i) \in E\\} \cup \\{(v\_{i1},v\_{i2})\\}$

Now, it is easy to see that $\langle G',k \rangle \in \mathsf{RESVC}$ *if and only if* $\langle G,k \rangle \in \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET}$.
> 2 votes

---
Tags: complexity-theory, algorithms, graphs
---