# Question
Title: Dijkstra's shortest path algorithm without relaxation
Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory answer there, hence comes this question.

So I have done competitive programming for fun for a while, whenever I need to find shortest path, I always implement something like this:

For the sake of brevity, this algorithm only finds shortest path's weight from a vertext `s` to a vertex `d` (instead of all vertices) (assuming there is no negative cycle in the graph of course)

`1. Create an empty min heap with comparator is the weight
2. Create an empty set (most of the time hash set)
3. Add s to the heap with weight is 0
4. Add s to the set
5. while (heap is not empty)
6. min = extract min from heap
7. if (min == d) return min.weight
8. add min to set
9. for (v in adj of min)
10. if (set is not already contains v)
11. add v to heap with weight is min.weight + weight(min, v)`

I have always believed that this is Dijkstra shortest path algorithm until today when I saw a video of lecture on Dijkstra algorithm from MIT. I realized that I never had the relaxation step in my Dijkstra algorithm.

So I'm really not sure if it is or just a variant of Dijkstra or not even Dijkstra (maybe A\*? I'm not sure)? Also, I have used this algorithm in programming contests many times, it always worked, but now I doubt about its correctness?

Yet, half of me still thinks this algorithm is correct because this not very formal proof:

* At a given time, there could be multiple paths to `v` with different weights in the heap, but once we extract first path to `v` from the heap (calls it `min_path`), it has to be smallest weight path to `v` in all the paths.
* For all the other paths to `v` which haven't been added to the heap, they have to have weight more than `min_path`'s weight because: when they are added to the heap, they can only be added after extracting some other paths which have bigger weight than `min_path`'s weight, so their weights are bigger than `min_path`'s weight.

If my algorithm is correct, then I think the running time would be `O(ElogV)` and `O(E)` of space because:

* The heap can have at most E elements at a given time
    + extract min costs `log(E)` \< `log(V^2)` = `2log(V)` = `log(V)`
    + same goes to adding an elmenet to the heap
* In total, `O(ElogV)` for running time.

So in the end, I believe my algorithm has same running time with standard Dijkstra that has relaxation and decrease key step (that costs `logV`), only downside is my algorithm costs `O(E)` for space. Is this correct?

UPDATE1: Java sample code

```
public class Test30 {
    public static void main(String[] args) {
        List<int[]>[] map = new List[4];
        map[0] = Arrays.asList(new int[]{1, 2}, new int[]{2, 2});
        map[1] = Arrays.asList(new int[]{3, 9});
        map[2] = Arrays.asList(new int[]{3, 1});
        System.out.println(dijkstra(map, 4, 0, 3));
    }

    public static int dijkstra(List<int[]>[] map, int n, int src, int dst) {
        boolean[] been = new boolean[n];
        // 0: vertex, 1: weight
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        been[src] = true;
        pq.add(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] pop = pq.remove();
            int v = pop[0];
            int weight = pop[1];

            if (v == dst) return weight;

            for (int[] i : map[v]) {
                if (been[i[0]]) continue;
                pq.add(new int[]{i[0], weight + i[1]});
            }
        }
        return -1; // impossible
    }
}

```

# Answer
**This answer refers to a previous version of the pseudocode, which had a bug. Once reaching a vertex, it doesn't update its weight ever again.**

Your algorithm isn't Dijkstra's algorithm. Worse, it doesn't calculate shortest paths. As a simple example, consider a graph with nodes $\\{s,a,b,t\\}$ and the following edges:

* $s\to a$ with weight 1.
* $s\to b$ with weight 2.
* $a\to t$ with weight 9.
* $b\to t$ with weight 1.

The shortest path from $s$ to $t$ is via $b$, but your algorithm will discover $t$ via $a$ and will therefore output a distance of 10 rather than the correct distance, which is only 3.

Finally, you mention that the space complexity is $O(E)$. In fact, since the heap and set contain *vertices* rather than *edges*, it is $O(V)$.
> 1 votes

# Answer
Necroposting, but, y'know. Firstly, yup, it is Dijkstra in all but detail.

I think the pseudocode won't work, though I think you can do the algo without decrease-key, so it is fixable.

Dijkstra did relaxation becasue it was the most obviously efficient approach, given he had mostly arrays and a few bits to work with. To this day that approach almost always beats anything else in the real-world.

Anyway, it looks like instead of relaxing, the vertex is re-added to the heap with the lower value. It then pops out just like you want. BUT, the original zombie copy of the vertex is still in there and will reappear and will get readded to the set later (which you might get away with if the set doesn't over-write) and is then recalculated (which again might be benign as it will duplicate vertices in the heap but with high weights creating yet more zombies).

So to fix it, you need to loop on extract min, throwing away anything already in the set thus avoiding zombie armageddon.
> 0 votes

# Answer
Yes, Dijkstra's algorithm without relaxation is possible. But the big-O complexity is the same. Dijkstra uses greedy strategy so there is the priority\_queue that guarantees the popped vertex is the closest vertex to the already-discovered island.

Without relaxation, you should allow duplicate nodes with different weights to be co-exist in the priority\_queue. This is OK because the top one always pops first which contains the shortest path. We can mark nodes as visited after they are just popped. We skip processing if they are already visited. This way the nodes will be marked only once and their neighbors processed only once.
> 0 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Why we need at most $2n$ examples to determine an axis aligned rectangle
In Ben-David & et al.'s *Understanding Machine Learning*, the authors wrote:

> Let $\mathcal{H}\_n$ be the class of axis aligned rectangles in $\mathbb{R}^n$ , namely, $$ \mathcal{H}\_n = \\{h(a\_1,\dots,a\_n, b\_1,\dots, b\_n) :\forall i,a\_i \le b\_i\\} $$ where $$ h(a\_1,\dots,a\_n, b\_1,\dots, b\_n)(x,y)= \begin{cases} 1\text{ if } \forall i, x\_i\in (a\_i, b\_i)\\ 0\text{ otherwise } \end{cases} $$

In the section for *Efficiently Learnable in the Realizable Case* just below the above paragraph, they set out an implementation of ERM rule for this hypothesis class as follows:

> for each $i \in \[n\]$, set $a\_i =\min\\{x\_i :(x,1)\in S\\}$ and $b\_i =\max\\{x\_i :(x,1)\in S\\}$. In words,we take $a\_i$ to be the minimal value of the $i$'th coordinate of a positive example in S and bi to be the maximal value of the $i$'th coordinate of a positive example in $S$

Later, in the section for *Not Efficiently Learnable in the Agnostic Case*, they wrote:

> recall the implementation of the ERM rule we presented for the realizable case, from which it follows that an axis aligned rectangle is determined by at most $2n$ examples.

I don't understand why we need up to $2n$ to determine the axis aligned rectangle. Would just one example is enough to determine a rectangle based on the learning rule specified above?

The online version of the book can be found here.

# Answer
> 0 votes
It's not really true the any sample of size *2n* (all with positive label) can be used to determine the rectangle. Take for example the following sample $S$:

$$ S=\\{(\mathbf{x}\_i, 1): \mathbf{x}\_{i} = \mathbf{x}\_{j}, \forall i, j\in\[2n\], i\ne j\\}. $$

This training set $S$ contains just one (positive) example sampled repeatedly.

Even for a sample with distinct (positive) examples, it's still not enough to construct a rectangle. Take $S$ as follows:

$$ S=\\{(\mathbf{x}\_i, 1): x\_{i, 1} \ne x\_{j, 1}\text{ and }x\_{i, h} = x\_{j, h}, \forall i, j\in\[2n\], i\ne j\text{ and }h\in\\{2,...,n\\}\\}, $$

where $x\_{i,j}$ denotes the $j$th coordinate of the $i$th example in the sample $S$.

The above training set $S$ contains examples whose coordinates are the same except the first one.

---
Tags: machine-learning, learning-theory
---


title: Why is English not a regular language?

text:
# Question
Title: Why is English not a regular language?
Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., with states going to a looping non-final state whenever there are no possible words to be made beginning with the letters you have already gone through. Then make every state that ends on a word final.

# Answer
The English language is regular if you consider it as a set of single words. However, English is more than a set of words in a dictionary. English grammar is the non-regular part. Given a paragraph, there is no DFA deciding whether it is a well-written paragraph in the English language. Of course, it can say whether each word is an English word or not, but it can not judge whole paragraphs.
> 55 votes

# Answer
Expansion of my comments to narek Bojikian's answer:

When people talk about natural languages such as English not being regular, they're usually talking on the level of grammar (syntax) rather than individual words. For instance, English has centre embeddings: you can build sentences of the form "the mouse escaped", "the mouse the cat chased escaped", "the mouse the cat the man owned chased escaped" that are grammatical and are arbitrarily long. These are similar to the language of matched parentheses "()", "(())" etc., and hence irregular for the same reasons.

However we can't conclude that English is irregular just from the fact that it has an irregular subset (for instance the language of all strings of parentheses does too, but that's clearly regular). The valid argument comes from the fact that all grammatical English strings of the form "(the \[noun\])\*\[verb\]\*" have matching numbers of nouns and verbs. The set of all strings of the form "(the \[noun\])\*\[verb\]\*" (call it $C$) is clearly regular, therefore if English were regular then the intersection of English and $C$ would be too. But the intersection is the irregular set of centre embeddings, hence English can't be regular.

One could argue that this argument isn't really correct: in practice the no-one ever uses centre embeddings with a depth of more than three, so the set of centre embeddings that actually exist is regular. This is a valid point, and is one of many reasons that the Chomsky hierarchy isn't always relevant to linguistics. But there are still a lot of situations where it is useful, for example saying that natural languages are context-free and then considering parsing them with pushdown automata suggests some possible models for how humans parse language.
> 17 votes

# Answer
It doesn't really matter whether English (either words, or complete sentences) is a regular or say context free language or not. What matters is that it is very, very hard to produce a state engine or a grammar of a reasonable size whose language is reasonably close to the English language.

But let’s say we are told that English sentences are not allowed to have more than a billion letters. So it is a regular language. Does that knowledge gain us anything? No, it doesn’t.
> 12 votes

# Answer
(Making my comment into an answer as requested by *Ben I*.) English is so nebulous that it is not a regular language for the trivial reason that it is not even a well-defined language. It is just like asking why mathematics is not a regular language.

This may seem like a non-answer, and to some extent it is, because every question regarding English depends on the definition of "English", and it is undeniable that nobody can ever define "English" 100% precisely. Sure, if you choose to define English as some language that is generated by a context-free grammar, then of course you can prove things about it. For example, if English permits arbitrarily deep center embedding, then you might be able to use the pumping lemma to show that it is not regular, but necessarily the proof will depend on the exact definition of English.

In any case, it occurs to me that you may have a misunderstanding about the term "word". In normal (non-technical) usage, an English word is a string of letters (sometimes including hyphens too). In theoretical CS, "word" simply means a string of symbols. If we treat English as a set of grammatically valid sentences, then each English sentence is made up of English words, spaces and punctuation, but these words are not the same as the words of a formal grammar that generates English (even if there is one).
> 8 votes

# Answer
Using the terms as they are used in formal computer science, it is indeed true that any language with a finite longest word is regular. Here a *language* is a set of words over an alphabet, and a *word* over an alphabet is a sequence of symbols from the alphabet.

So if the language "English" is the set of words over a 26-symbol alphabet whose membership is determined by e.g. having a definition in the Oxford English Dictionary, then English is a regular language.

However, in the context in which the question arose the language "English" was probably intended to be the set of words over an alphabet which also includes space and punctuation marks, with membership determined by something like "being an utterance which a native speaker might make". Formalising that membership would be a challenge in itself. Is "*Colourless green ideas sleep furiously.*" a word in English? What about "*'Twas brillig.*"? But the odds are that it would require some notion of backreference to ensure correct correspondence of gender, plurality, or even name in the presence of anaphor or cataphor.

I note, as an aside, that I am given to understand that Swiss German, considered at the level of the grammatical sentence, has a correspondence mechanism which makes it not even context-free.
> 6 votes

# Answer
English is not a regular language not because it's irregular, but because it's not a language.

(In the formal sense, that is.)

The common claim from CS/formal-logic folks thae English (or any other human language) is not regular is based on nestability of grammatical constructs. Same idea as "language of balanced-parentheses strings is not regular", clearly provable by the pumping lemma. The problem here is that arbitrarily-nested grammatical constructs are **not** members of the language, because beyond some (indefinite but clearly existant) limit they're no longer intelligible.

Rather, English (and other human languages) aren't regular languages because they're not languages. There is no rigorous definition of what is or is not a member of the language. For some strings of words, most users of the language are in agreement as to whether or not they're in the language, but for plenty of others, nobody agrees, and for many, even most individuals are not sure.
> 3 votes

# Answer
English, at the word level (no sentences, let alone grammar, punctuation or paragraphs), is regular provided we assume there are a finite number of words (no matter whether there are 1 million, 2 million, 10 million or even more, as long as it is finite). If nothing else, this is due to the fact that all finite languages are regular. It is fairly easy to construct an NFA with a start state and epsilon transition to the start state of every word. Each of these states would then have a single character to move it to a next state, and any other moves to a dead state. Of course this isn't the best possible construction, and there are ways to group together common suffixes with epsilon transitions from valid prefixes (eg. skiing is valid, kayaking is valid, doging is not), but that is all irrelevant. Also, it is possible to write a regular expression for English words. Simply union together all the words- eg. airplane + avocado + ... + ball + ... + zebra + ... It would be a hell of a long expression, but is valid nonetheless.

English at the sentence level (never mind syntax, punctuation, sentence order etc.) is not regular, and this is easy to show using the pumping lemma. Consider some story, novel, article etc. that is larger than the number of states in our supposed DFA. Even if there are a billion states, surely we can find some English text with more characters than that. Now, we must be able to find some subsection that can be repeated twice, thrice ... infinitely many times and the piece still remains in valid English. It is nearly impossible to find this (even if y is a space, two spaces are considered a typo). Of course there are obscure examples that are debatable (eg. The tree grew bigger and bigger, The tree grew bigger and bigger and bigger ... ). It is debatable here how many times repeating "and bigger" would be acceptable. Even if the answer is infinite, it still does not mean English is regular.

The pumping lemma doesn't say there merely exists some w longer than p that can be split into xyz, it says that EVERY single w longer than p must satisfy this condition. Surely I can find another piece written in valid English that is long enough, but does not contain any of the obscure debatable examples (like "and bigger"). Applying the pumping lemma here clearly shows English is not regular.
> 2 votes

# Answer
Interesting conversation.

I think that the grammar of English is not regular, because the grammar was defined as programming language are defined.

But natural spoken English (or any other language) is regular.

The example that breaks regularity is {a^n b^n | n \>= 0}, but I think that no human being is able to speak so well English that he/she can say a phrase similar to a^1000000 and b^1000000, and there does not exist any human being that can say if the person that say that it was correct of not.

So, I think that the regular language L = {a^nb^n | n\<1000000} union a^1000000 a\* b^1000000 b^\*, is a regular language that will cover any real English conversation in this context.

So, grammatical English is not regular. But natural spoken English is regular.

IMHO
> 0 votes

---
Tags: formal-languages, regular-languages, finite-automata
---


# Question
Title: Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?
There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. However primitive recursive functions are considered separately and I don't know any equivalence of that computational model with any other. I was wondering whether primitive recursive functions are equivalent to any other known computational model. I was thinking about Turing Machine with bounded tape size (linearly bounded), since primitive recursive functions have bounded $\mu$ operator. However I couldn't find any result that would say that, so is there any known computational model equivalent to primitive recursive functions?

# Answer
> 5 votes
LOOP is a simple programming language which exactly captures primitive recursive functions.

Primitive recursive functions also have other characterizations. For example, they are the functions which are provably total in $\rm I\Sigma\_1$ (a fragment of Peano arithmetic), and they are the functions computable by a Turing machine whose running time is in the Grzegorczyk hierarchy.

---
Tags: computability, computation-models, primitive-recursion
---


# Question
Title: An "edge-spanning-tree" of minimum height
Given any connected undirected graph, we can convert it into a tree by "detaching" some edges from one of their endpoints. For example, consider the graph with the following edges: $$ (1) ~~~~~~~~~~~~~ a-b, b-c, c-a, c-d, d-e $$ We can detach the edge b-c from the vertex c (adding a new vertex c' of degree 1), and get the graph: $$ (2) ~~~~~~~~~~~~~ a-b, b-c', c-a, c-d, d-e $$ which is a tree (a path of length 5). We can call it an "edge-spanning-tree", as it is a tree that spans all edges of the graph.

Among all edge-spanning-trees, I would like to find the one with minimum possible height (minimum among all possible roots). The height of graph (2) is 3, e.g. when the root is c. However, starting from the original graph (1), we can detach the edge b-c from the vertex b instead, to get the following tree: $$ (3) ~~~~~~~~~~~~~ a-b, b'-c, c-a, c-d, d-e $$ the height of this tree is 2 (when the root is c).

QUESTION: Is there a polynomial-time algorithm that finds an "edge-spanning-tree" of minimum height?

# Answer
> 2 votes
Here is an idea. The root of your desired tree should be one of the centers (a vertex with minimum eccentricity) of the graph $G$. You run BFS from each of the nodes in $G$ and observe the resulting BFS tree. We pick the tree $T$ that has the lowest height. There will be some missing edges that were present in $G$ but have not been selected in $T$. For all such edges, $(u,v) \notin T$, We augment an edge $(u,v')$ into $T$ if $u$ is closer to the root than $v$ in $T$; otherwise, we augment an edge $(u',v)$ into $T$. This may increase the height of $T$ by at most one (when both $u$ and $v$ are leaves in $T$).

In the case of the graph having multiple centers, we may try other BFS trees $T'$ rooted at other centers (all of which are of the same height as $T$), to see whether they remain at the same height even after these augmentations. Finally, report the optimal one.

---
Tags: graphs, trees, spanning-trees
---


# Question
Title: How to interpret Universal Quantifier in Alternating Turing Machines?
I am trying to read about Alternating Turing Machines (ATM) that have both existential and universal quantifiers for all their *internal* states. Given that these models are conceptual, I tend to imagine that there is some form of reflection in terms of an advantage provided to the deterministic Turing Machine to provide it the same power as an ATM. What advantage does this correspond for the universal quantifier?

For example, I understand that a **certificate** is provided to a deterministic Turing Machine to make it as powerful as a non-deterministic Turing Machine with an existential quantifier, but I fail to understand the correspondence for the universal quantifier.

It has been indicated that alternations of both quantifiers form some form of a trade-off between space and time. I understand that providing the certificate saves you time from searching all the examples, thus saving you some time at the cost of space occupied by the certificate. So naturally, the universal quantifier should provide you with the opposite. How does using a universal quantifier save you space at the cost of time? Won't checking for all certificates take both space *and* time?

# Answer
As you know, alternating Turing machines are nondeterministic, but have both existential and universal states. In an existential state one of the possible computations should accept, in a universal state all possible continuations should accept. In this way an ordinary nondeterministic TM corresponds to an alternating TM with only existential states.

In my intuition a certificate is a way to resolve nondeterminism by specifying the correct continuation of the computation in the certificate.

Universal quantification enables one to reuse both space and time. At a universal state the computation tree splits. As basically time is measured as the depth of the computation tree, practically both continuing computations are run in parallel.

One of the important results in complexity theory is the result of Savitch that nondeterministic space is equivalent to deterministic space. The intuitive reason is that space can be reused. Time ticks on, but we can erase the tape and test another computation in the same space. If there are many computations to check, we have to reserve space for the bookkeeping of computations too. Thus Savitch' result is $NSPACE( s(n) ) \subseteq SPACE( s^2(n) )$. Then $NPSPACE = PSPACE$, nondeterministic polynomial space equals deterministic polynomial space.

The same technique can be used with alternation, to move from parallel in space to parallel in time. Chandra and Stockmeyer show that $NSPACE( s(n) ) \subseteq ATIME( s^2(n) )$. Then $NSPACE = AP$ or (non)deterministic polynomials space equals alternating polynomial time.
> 1 votes

---
Tags: complexity-theory, turing-machines, co-np
---


# Question
Title: Time Complexity O-Notation for Kociemba, Korf, and Thistlethwaite's Algorithms? (Rubik cube)
I'm currently studying the 3x3x3 rubik-cube-solving algorithms developed by Kociemba, Korf, and Thistlethwaite and I'm interested in understanding their computational complexities.

Could someone please explain or provide the Big O notation for the time complexity of these algorithms?

# Answer
> 2 votes
As noted in the answer of codeR Big O notation makes no sense for 3x3x3 alone because of the constant input size. What might be interesting to discuss is the time complexity to find a solution with these algorithms in relationship to the length of the optimal (=shortest) solution to solve a Rubik's cube. So we divide the cube space in classes which need 0 .. 20 moves to be solved.

The empirical distribution for 1.000.000 random cubes is shown in this diagram. For the exact sizes up to 15 moves see for example here. No cube needs more than 20 moves since God's number is 20.

**Thistlethwaite's algorithm:**

Without going into details it works with 4 steps and precomputed tables wich give the solution moves for each step just by table lookup. So the solution time is more or less constant and does not depend on the length of the optimal solution. The maximum solution length is 52.

**Korf's algorithm:**

It uses IDA\* to optimally solve a Rubik's cube. It looks for solutions with increasing length until it succeeds and the algorithm returns the optimal solution, which is \<= 20. The heuristic function is implemented as pattern databases in memory. Korf himself describes the performance as $t\approx n/m$ where t is the running time, m is the amount of memory used and n is the size of the problem space. The size of the problem space for Rubik's cube (more exactly the number of positions which need to be checked) increases exponentially with a branching factor of about 13.3, so that it will take approximately 13 times as long to find the optimal solution with this method for a cube which has optimal length 18 compared to a cube which has optimal length 17. The maximum solution length is obviously 20.

**Kociemba's algorithm:**

It uses IDA\* to find optimal **and suboptimal** solutions in phase 1 to transfer the cube into a certain subgroup and then again uses IDA\* to completely solve the cube in this subgroup. A modern Python version of my algorithm holds pattern databases in memory with complete information so that it only takes linear time to find the optimal solution in phase 1 and phase 2 in relation to the length of the optimal solutions in phase 1 and phase 2. Since the optimal solution for phase 1 has a maximum length of 12 and for phase 2 of 18, the **first solution** has at most 30 moves.

But a central part of the algorithm is to generate **suboptimal solutions** in phase 1 which then are combined with the optimal solution of phase 2 to achieve shorter overall solutions. The number of suboptimal solutions in phase 1 also increases exponentially with the length of the suboptimal solutions (presumably also with a factor about 13). In principle you can run the algorithm until it finds a phase 1 suboptimal solution for which the phase 2 solution has length 0. In this case you have found the optimal solution.

But this is not the intention of the algorithm. Usually you just run it until the desired total length (phase 1 length + phase 2 length) is below a certain treshhold. So for random positions you will find solutions with \<=20 moves typically within fractions of a second. The difference to Korf's algorithm is that they are not proved to be optimal. For or a more detailed discussion of the runtime behaviour see the README of the Python implementation mentioned before.

# Answer
> 2 votes
Recall that the time complexity of an algorithm is expressed in terms of its input size. The growth rate of this complexity measure is usually expressed in terms of an asymptotic notation such as Big-oh. For a fixed-sized cube, any reasonable algorithm would take a constant amount of time to solve; however, the constant can be very large. All three of the mentioned algorithms are specific to solving the standard `3 x 3 x 3` Rubik's cube; thus, they may not work for any general cube of larger size.

Out of the three, Korf's algorithm gives the best upper bound, which is 18 face turns. If you are interested in the raw performance of the three heurictic approaches, it does not seem there is a clear winner and requires further research and/or experimental investigation.

Read more here and here.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: What is the relationship among the various algorithms?
I'm curious about whether there exists a hierarchical or layered concept within the broad categories of algorithms, where they can be further divided into subcategories based on their characteristics and problem-solving approaches. Is there a clear association or inheritance relationship between different algorithm categories or subcategories? For instance, are some algorithms based on the same fundamental principles but optimized for different application scenarios? How to define them?

I aim to understand the underlying patterns or classes of relationships that have emerged among these algorithms. In other words, I'm looking to explore the types or categories of relationships between algorithms that naturally evolved from their original intent to solve problems.

# Answer
> 1 votes
Here is a handy categorization from wikipedia and a list of few popular algorithmic topics.

---
Tags: algorithms
---


# Question
Title: Quasi polynomial algorithm for np complete problem
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm exists already?

I want to know why it becomes impossible to solve NP complete problems on regular machine. Is it because it will take longer time to solve? (Maybe in years) Or just because it's taking exponential time? So if we find quasi polynomial algorithm, then also it will take years to solve NP complete problem or will it take less time and have practical applications in real life even it's not polynomial time? Also does a quasi polynomial algorithm imply that P=NP?

# Answer
Look at the definition given. Assume you have a quasi-polynomial algorithm that takes $2^{(\log n)^{1.1}}$ nanoseconds. This is less than if $n^2$ nanoseconds $ n \le 2 ^ { 2 ^ {10}} = 2^{1024}$. That will be solvable for quite large x. But with large c the function grows much faster. With c = 2 the same expression becomes $n^ {\log n } $ which grows faster than $ n^{10}$ if n \>= 1,024. Every time n doubles, the exponent increases by 1.

So c = 1.1 would make typical cryptographical problems laughably easy. c = 2 would make some solvable, with a very very powerful computer. Probably could be handled by switching from 1024 to 4096 bits. You can do the maths for c = 3. I think current cryptography would be safe.

In the end, it is not NP-completeness that makes crypto safe. It’s the fact that there are no known algorithms that crack crypto in more than a negligible number of cases in an acceptable amount of time. I could easily design an NP-complete problem where 99% of cases are solved easily; that would be useless for crypto.
> 2 votes

# Answer
Recall that quasi-polynomial-time algorithms have a running time upperbounded by $2^{O((\log{n})^c)}$ for some constant $c\in\mathbb{N}$. It has a separate complexity class **QP**.

From wikipedia:

> The decision problems with quasi-polynomial time algorithms are natural candidates for being NP-intermediate, neither having polynomial time nor likely to be NP-hard.

Thus, finding a problem in **QP** that does not belong to **P** will prove **P $\ne$ NP**.

Typically, **NP-Complete** problems do not expect to have polynomial time algorithms. They typically have an exponential running time. For large input sizes, it will take significantly long time to terminate.
> 1 votes

---
Tags: time-complexity, np-complete, p-vs-np
---


# Question
Title: Prove "Vertex Cover OR Clique" is NP complete
**Instance**: An undirected graph $G$ and a positive integer $k$

**Question**: Does $G$ contain a vertex cover of size $\leq k$ *or* a clique of size $\geq k$?

Obviously, this problem is solved by polynomial reduction, but is it from Clique or Vertex Cover? And how?

I've tried to reduce from both problems, but seem to get stuck. If I reduce from Clique, for example, It seems I'd need to guarantee that there isn't a Vertex Cover, but it's not clear to me how to do that. It seems reducing from Vertex Cover is more promising, but I run into the same issue

# Answer
You can easily reduce from clique as follows.

First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is trivially solvable in polynomial time).

Given a graph $G$ on $n$ vertices and $3\leq k \leq n$, construct a graph $G'$ by taking the disjoint union of $G$ with a perfect matching on $2(n+1)$ additional vertices.

Now, $G$ has a clique of size $\geq k$ if and only if $G'$ has a clique of size $\geq k$. This is because if we find a clique of size $\geq k\geq 3$ in $G$ then it cannot lie in the matching part, as this has no cliques of size greater than $2$. Moreover, $G'$ has no vertex cover of size $\leq k$, as you need at least $n+1$ vertices to cover the matching. Thus, $G$ has a clique of size $k$ if and only if $G'$ has a clique of size $\geq k$ or a vertex cover of size $\leq k$ (this second condition always being false).
> 3 votes

---
Tags: np-complete, reductions, np, clique, vertex-cover
---


# Question
Title: Correctness proof of bubble sort(bogus proof)
I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction.

Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for induction step: remove one element out of $n+1$ elements array, which makes array with $n$ elements. According to hypothesis algorithm will sort this array. Now add back the element you removed before and run the algorithm for just one iteration of outer-loop which makes array sorted.

I know this proof is not valid for correctness, but i am not able to see the mistake. I would really appreciate if you could review it and tell me the mistake.

# Answer
> 0 votes
BubbleSort can be expressed in a few different ways, I'm assuming you're referring to something similar to wikipedias formulation.

The mistake in your proof is that you assume that sorting an $n + 1$ element list is the same as sorting an $n$ element list, adding one element and sorting again. But that isn't the case, the inner loop always iterates over all elements of the list⁺. So sorting a list of length $n$ and sorting the first $n$ elements of a list of length $n + 1$ is not the same procedure (for example, try sorting `[3; 1]` and `[3; 1; 2]` by hand).

The idea behind your argument can be adapted though, instead of using induction over the length of the list use it over the number of iterations of the outer loop, i.e. prove that:

> A list of length $m \> n$ is sorted up to the $n + 1$th element after $n$ iterations of BubbleSort's outer loop.

The correctness of BubbleSort is a direct result of the above.

---

(+) There are some formulation of BubbleSort in which the inner loop *doesn't* iterate over the whole list except for in the first iteration of the outer loop. For a list `A = [a_1; a_2; ...; a_n]`:

```
BubbleSort(A):
for j = n - 1 step -1 until 1 do
    for i = 1 step 1 until j do
        if A[i + 1] < A[i] then interchange A[i] and A[i + 1]

```

(taken from The Design and Analysis of Computer Algorithms, p.102)

But a similar argument as above can be made here.

# Answer
> 0 votes
What you have proved: You can sort an array with your “modified bubble sort” algorithm which goes like this: Sort the first n elements using “modified bubble sort”, then do one more bubble sort pass. This is a *slightly* different algorithm.

I figured out a small modification to the bubble sort code where your proof worked - then I looked closer and the my modified code was insertion sort!

---
Tags: algorithms, sorting, search-algorithms, correctness-proof
---


# Question
Title: Can this Classic Regular Expression be simplified?
I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx):

{(ΣΣ)\*00(ΣΣ)\*}Σ ∪ Σ{(ΣΣ)\*00(ΣΣ)\*}

It "feels" like it should be reducible to me but I can't see how. Is it reducible or am I just asking for trouble trying? The term in {} just generates even-length strings that contain, at least, the substring 00.

# Answer
$(\Sigma \Sigma)^\* (\Sigma 0 0 | 0 0 \Sigma) (\Sigma \Sigma)^\* $

You need an even number of letters on the left and an odd number on the right, or the other way round.
> 1 votes

---
Tags: complexity-theory, regular-languages, regular-expressions
---


# Question
Title: Can every greedy problem be solved using dynamic programming?
Can every problem with a greedy solution be solved using dynamic programming? Why or why not?

I'm not completely sure how to formally reason about this, my understanding about the structure of problems with a greedy/dp solution is quite handwavy.

I found conflicting answers for this online, so I'm not sure what to trust.

# Answer
Both greedy and dynamic programming are algorithm design techniques, typically used to solve optimization problems. The same problem can be solved in multiple ways using various techniques, including plain old brute-force. The real question to ask is whether using one technique over the other can lead to a more efficient solution or not.

There are two concepts, namely: optimal substructure

> a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

> Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.

and overlapping subproblems

> a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times

In order to make 'efficient' use of dynamic programming, your problem must exhibit both of these properties. Typically, dynamic programs take substantial space and/or time to obtain an optimal solution from their greedy counterpart, making the greedy solution more lucrative (at least in most cases). If you already have a greedy selection strategy, it might be pointless to explore multiple subproblems, as in the case of a dynamic program.
> 0 votes

---
Tags: algorithms, optimization, dynamic-programming, greedy-algorithms
---


# Question
Title: Resources on Tree Automata Regular Expressions
Is there a text that goes through some explicit examples of converting tree automata to tree regular expressions?

I'm working through Comon's "Tree Automata Techniques and Applications", and I'm trying to work out some examples of regular expressions from tree automata. I'm convinced that the procedure given in the text works, but when I try to apply it to an automaton as simple as "are there an odd number of nodes labeled 'a'?" the resulting expressions are quite complicated. I'd appreciate a reference to improve my intuition and confidence that I've applied the technique correctly.

# Answer
> 2 votes
Here is a master's thesis and an arXiv paper on the topic, which contains some examples.

---
Tags: reference-request, regular-expressions, tree-automata
---


# Question
Title: Prove/disprove that if $L_1, L_2\in RE$ then $L_1-\ L_2, L_1 - \bar{L_2}\in RE$
I need to prove\disprove that if $L\_1, L\_2\in RE$ then $L\_1-\ L\_2, L\_1 - \bar{L\_2}\in RE$.

Trying to prove those statements I thought about using the turing machines $M\_1, M\_2$ of $L\_1, L\_2$ respectively, but I can't simulate input on $M\_1$ and $M\_2$ since they might run forever.

How can I prove (or disprove) those two statements?

# Answer
For the statement which is false, you take your easiest example of a non-r.e. language (ie the complement of the Halting problem), and then show how it is expressible in the respective form.

For the statement which is true, you take semidecision procedures for $L\_1$, $L\_2$ and built one for the relevant language. If you do this properly, then the forever-running is not an issue. Or, if available to you, you invoke the closure of $\mathrm{RE}$ under intersection.
> 0 votes

# Answer
We are given $L\_1, L\_2$ that belong to $RE$, hence there are TMs $M\_1, M\_2$ that *recognize* the languages (not decide). To check for $x \in L\_1 - L\_2$ we need to recognize $x \in L\_1$ and $x \notin L\_2$. But due to the nature of $RE$ languages, the machine to recognize $x \notin L\_2$ may run forever.

Looking at your second problem, we have to recognize $x \notin \bar L\_2$, which is same as $x \in L\_2$. For a language in $RE$ this is doable. The language $L\_1 - \bar L\_2$ is the set of strings that belong to $L\_1$ but do not belong to $\bar L\_2$. The second condition can be written as strings that belong to $L\_2$. Using the closure property of $RE$ under intersection you can complete your answer.
> 0 votes

---
Tags: turing-machines
---


title: Algorithms for stacking gage blocks

text:
# Question
Title: Algorithms for stacking gage blocks
I'm looking for algorithms for stacking gage blocks.

For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this...

Mitutoyo's 56 block metric set

```
 1 0.5mm block
 9 blocks from  1.001mm to   1.009mm in steps of 0.001mm
 9 blocks from  1.01mm  to   1.09mm in steps of  0.01mm
 9 blocks from  1.1mm   to   1.9mm in steps of   0.1mm
24 blocks from  1.0mm   to  24.0mm in steps of   1.0mm
 4 blocks from 25.0mm   to 100.0mm in steps of  25.0mm

```

And the way machinists generally stack these is to start at the least significant digit and work your way left, for example...

```
Target size: 28.538mm
Add block:    1.008mm, 27.53mm remaining
Add block:    1.03mm,  26.5mm remaining
Add block:    1.5mm,   25.0mm remaining
Add block:   25.0mm,    0.0mm remaining

```

For any given set of N distinctly sized gage blocks there are 2^N stacks that can be made as the order of blocks in the stack isn't important. This number of combinations is certainly too high to brute force.

So given a set of gage blocks and a valid target size, the algorithm should be able to select a set of gage blocks that add up to the target size.

I would like to see what algorithms people can come up with to solve this problem, so far I've only come up with...

> Use A\* with stacks being the nodes, block additions being the edges and counting the number of correct consecutive digits from the right as the heuristic.

# Answer
> 2 votes
If you are looking for the sum of the blocks to be below the target size, you are talking about the 0/1 Knapsack problem. In your case, it seems that all profits are unit values.

Alternatively, if you are looking for the sum of the blocks to exactly add up to the target size, you are talking about the subset-sum problem.

Both of these are old classical problems, and plenty of efficient solutions have been studied in the literature.

---
Tags: algorithms, complexity-theory, dynamic-programming, graph-traversal
---


# Question
Title: How many games will a “MENACE” tic tac toe computer take to train
I recently read about the “computer” built out of matchboxes designed by Donald Michie that could teach itself how to play tic tac toe. Here is the Wikipedia article about it:

https://en.m.wikipedia.org/wiki/Matchbox\_Educable\_Noughts\_and\_Crosses\_Engine

I thought it looked interesting, so I decided to make a digital version in Python for fun and practice. It works well against random moves (I just ran it on the data from ≈10,000 games, and it won 4757 out of 5353) but it still looses often against me.

Here are some points that a perfect answer would address:

* How many games will it take for a “matchbox computer” that works exactly like the one Michie designed to start playing perfectly?
* Did the original computer with actual matchboxes ever reach perfect play?
* Will the computer ever reach perfect play if trained against only random moves?

This question is not asking for help with the code, but if someone was interested, my including the code could possibly be a help. Here is a link to a GitHub repository I created so I could share it:

https://github.com/ACertainArchangel/Recreation-Of-MENACE-Tic-Tac-Toe..git

Sorry, I know it's not very good and doesn't obey conventions; I've only been coding a couple of months :)

# Answer
Let me illustrate with a hand-wavy argument on a very simple game why convergence to optimal play might be very slow, and not even guaranteed, when training against a random opponent.

Consider the following game: Player A first picks a color, either red or blue. Then player B picks a number between $1$ and $100$. If player A picked blue, they always wins. Otherwise, player A wins except if player B picked $1$. The optimal strategy for player A is obviously to pick blue.

Now say that player A is the matchbox computer, and player B is a random opponent. Suppose in the first 5 games, player A picked red and player B didn't pick $1$ (this is not that unlikely). Player A won each time, being rewarded $3$ red beads for every victory. At this point (assuming the matchbox computer started with one bead of each color), we have $16$ red beads and $1$ blue bead.

With probability $\frac{16}{17}\cdot\frac{99}{100} \approx 0.93$, Player A picks red again and wins, thus gaining an extra $3$ red beads. If this happens, the probability of it happening again in the next turn will be even higher than that ($\approx 0.94$), and this will snowball.

Now you might still get lucky at some point and get a streak of losses with red getting rid of all the red beads, or pick blue enough times by pure chance to make the blue beads take over. I haven't tried to work out the probabilities, but empirically I get situations where, starting with one bead of each color, after $10\ 000\ 000$ games the red beads represented more than $99.95\\%$ of all beads. Meaning the matchbox computer learned the opposite of the optimal strategy!
> 2 votes

# Answer
To add to what Tassle said, I just tried training the AI against another copy of itself, and this produced slightly better results. I tried Increasing the number of beads taken from the matchbox on a loss (and making sure the total wouldn't fall below zero), which also helped make sure the computer wouldn't get "stuck". I am now happy with how it is working.

Swapping between AI and random for a lot of games to see if perhaps the AI would find ways to exploit weaknesses developed by random training, and then random having random training "shake things up" again made a very big difference in performance too. The program now only looses once in a blue moon).

Increasing the number of beads taken from the matchbox on a loss (and making sure the total wouldn't fall below zero) also helped make sure the computer wouldn't get "stuck". I am now happy with how it is working.
> 0 votes

---
Tags: machine-learning
---


# Question
Title: Are there any compression algorithms based on PI?
What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).

I've seen recently some prototype of πfs which assume that every file you've created (or anybody else) or you will create, it's already there so it's a matter of extracting it. There is also piFile which can convert your files to pi metadata.

There is already BBP type formula (as part of experimental mathematics) which allows us to compute *n*th binary digit of pi. So storing position of our start and length of the data, we can theoretically extract the data of our interest. There are some arguments against it that our metadata (e.g. the offset to our data) could be larger than the extracted data. The matrix symbols and π can be encoded in base-256 to make it more efficient (see the joke).

Based on above, my main question is:

* Are there any compression algorithms based on PI?

If not, does it make sense? Or were there any researches in that area?

Or maybe π is not the right one, so what about Euler's constant or Tau (τ)? Would it make any difference?

---

Image credits: Dinosaur Comics

---

See also:

# Answer
Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to find. This is not only because we have to go far into the expansion, but also since we expect to try $2^{128}$ different locations before finding a hit.

Second, while in some cases your scheme will result in a major compression, this will only happen when a certain string appears comparatively early in the expansion of $\pi$. There is no reason you would ever want to compress that sort of string. In contrast, other compression algorithms try to find structure in the data, and have guarantees that show that if such a structure exists, then they can always exploit it.

Changing $\pi$ with any other number wouldn't change the picture. The algorithm is too specific, compressing only strings we aren't really interested in; and very inefficient in the compression phase.
> 21 votes

# Answer
Based on Yuval's answer, with a slightly different explanation and an example to help illuminate the problem.

# Theory

Take a file $16$ bytes long ($128$ bits). The compression algorithm follows:

1. Determine where the binary expansion of $\pi$ matches the contents.
2. Store the offset and number of sequenced bits ($128$).

The offset for the file contents should be around the $2^{128}$th bit; however, it is time consuming to find the offset because it requires:

* a deep search for the bit pattern; and
* looking at $2^{128}$ different locations (on average).

Matches that occur early enough in $\pi$ to attain significant compression will not be varied. That is, it isn't possible to use $\pi$ to compress interesting, real-world data because real-word strings are unlikely to arise early.

See also, information entropy.

# Example

Let's compress a social security number (SSN): **938-933-556**. Calculate the number of bits to encode that value using $log\_2(938933556)$, which is ~$29.8$ and must be rounded to $30$ (as bits are indivisible).

In $\pi$, that SSN starts at offset $597,507,393$, which needs $log\_2(597507393)$ bits, or ~$29.2$ and must also be rounded to $30$. There might be an earlier offset, but it is unlikely to require significantly fewer bits.

Maybe we can chunk the numbers?

* **938**, offset $1,124$, 11 bits
* **933**, offset $1,216$, 11 bits
* **556**, offset $11,727$, 14 bits

That's $36$ bits, an even worse result. Perhaps a different chunking?

* **9,389,335**, offset $15,312,393$, 24 bits
* **6**, offset $8$, 3 bits

That's $27$ bits, which is better than $30$, but has problems. First, the addition of a non-uniform chunking requires *more information* to indicate where the chunks start and stop. Second, it is even more time intensive to find the optimal chunking to attain the fewest bits. Third, saving three bits barely qualifies as compression.

Different transcendental numbers will have the same statistical result, more or less. Even if you shave off a hair, say, two bits' worth, the constant that was used must be indicated. Three bits allows the algorithm to select from one of eight different numbers. As a consequence, the algorithm would be much slower due to searching $N$ sequences instead of one.
> 16 votes

# Answer
> Are there any compression algorithms based on PI?

yeah, https://github.com/divinity76/pi\_compression

> does it make sense?

nope, storing the offsets typically takes more disk space than you save, at least with the above implementation (3 notable things about it that could be improved though, it only considers the first 2^32 bytes of a binary representation of pi, and it uses an excessive amount of bits to store the number of matching bytes per offset, namely 8 bits while testing shows that 3 bits would be optimal, and it only considers full-byte-matches, so if there's a 15 bits match somewhere, it will only be considered as a 8 bit match.. also if the last 4 bits of a byte matches but not bit #3, and the first 4 bits of the next byte matches but not bit #5, it's not considered to be a match at all)

> Or were there any researches in that area?

uhm sure, that's why i wrote the above implementation, and the results seem to be that within the first 4GB of pi, you're likely to find 4 matching bytes of.. pretty much anything, which is very difficult, if not impossible, to gain any compression out of, i failed at least. (but my implementation is not optimal, as explained above) - also the compression is very slow, but my implementation is single-threaded, but the algorithm allows for multithreading if someone could be arsed writing the code, which would allow for scaling performance with the number of available cores.

decompression is very fast, though.
> 2 votes

# Answer
> Are there any compression algorithms based on PI?

this question seems to be motivated by the idea that there is some "popular science" *speculation* that $\pi$ or other math constants contain all possible sequences of digits, but it is unproven. a compression algorithm based on $\pi$ having arbitrary sequences of digits is not inconceivable but would hinge on the following property. ie "afaik" its an open problem/ question whether the following question is (un)decidable (and the same holds for other classic constants):

> input sequence $X$. output, Y/N, $\pi$ contains the sequence $X$

there are not *"mainstream"* compression algorithms based on $\pi$ but in (T)CS its difficult/ problematic to draw a strict boundary around *"mainstream"*. in contrast to popular usage of the term, referring to a set of "widely used" or "standard" algorithms, a "compression algorithm" in CS is a very broad concept. technically yes, "a compression algorithm based on $\pi$ exists", because it is easy to construct a *"contrived"* one (exercise to reader), but no, no standard algorithms are based on sequences of digits in mathematical constants.

even if any math constant was shown to have the remarkable property of "containing all strings", a simple argument is that the compression algorithm would spend "too much time" searching for the position of the string, and describing its location would often take a long(er) string of digits.

see also/ contrast/ try to reconcile with similar high-voted question how can it be decidable whether pi contains some sequence of digits. (cs.se) *(hint: the title can be regarded as somewhat misleading)*
> 0 votes

# Answer
The point is that using the PI to save a dictionary per compression source, right? Why not use a well-defined sequence of bytes as a common dictionary instead of PI and try that? I think that if this special sequence is well thought out ((by a genetic algorithm covering frequent sequences?) and is not just a permutation of all the possibilities, you get a very good compression result and a better result than PI compression. If we could generate this hypothetical set of bytes by a formula, we wouldn't even have to store this dictionary plain but could generate it at runtime. Who has an idea how this could be realized?
> -1 votes

---
Tags: algorithms, data-compression, mathematical-programming
---


title: Optimal Binary Search Trees Knuth

text:
# Question
Title: Optimal Binary Search Trees Knuth
Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R\_{0,n-1} \leq R\_{0,n} $ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a\_{0} ... a\_{n} $ .

I understood the idea of the proof using induction that for some $k \\, j\_{k}=i\_{k} $ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a\_{n}$. Can anyone please give me a hint or a solution to that.

# Answer
That proof in fact had an error, in exactly the step in the induction that your answer asks about. Knuth published an erratum about it the following year. See Item 2 in \[1\] (copied below). See also \[2\] for a tutorial with a different, correct proof.

\[1\] Knuth, D.E. Optimum binary search trees. Acta Informatica 1, 270 (1972) (see below).

\[2\] https://doi.org/10.1016/S0304-3975(96)00320-9

---
> 1 votes

# Answer
I am thinking if `jk = ik`, let's denote `jk=ik=m`, then we think of subsequences of `[0,m-1]` and `[m+1,n]`, treat `[m+1,n]` as a standalone tree. And according to the paper, `T` and `T'` will be of same weighted path length if `αn = α`. So let's make a tree of subsequence `[m+1,n]` with last item being `α`, with weighted path length sum being `Tk`. And then replace the right-subtree of `jk/ik` with `Tk` for both `T` and `T'`.

Let's denote the weighted path length sum of `[0, m-1]` of `T` and `T'` being `T0` and `T0'`. Because `jk = ik`, the levels of `T` and `T'` are both k. So`C(T) = T0 + k*Ak + Tk(starting from level k+1); C(T') = T1 + k*Ak + Tk(starting from level k+1)`; And `C(T)` should be equal to `C(T')`. So `T1 = T1'`

Replace right subtree of ik of T with right subtree of jk of T' will yield T'' with same weighted path length as T'.

PS: actually I don't quite know how it proves `j2<=i2, j3<=i3` using induction and left-right symmetry, anyone can help answer that?
> 0 votes

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


# Question
Title: Equality of lambda terms which do not have normal form
In the context of lambda calculus, how should one prove $\beta$-equality of terms that do not have normal form?

In particular, how to prove that these are different combinators: $$ Y = λf.(λx.f(xx))(λx.f(xx)) \\ Θ = (λxf.f(xxf))(λxf.f(xxf)) $$ These work the same if we reduce them, but Wikipedia states that they are different, and that there are in fact infinitely many combinators that work the same as these.

# Answer
> 1 votes
By extending the λ-calculus to allow for infinite λ-terms and infinite reductions. Then you may assert that both $Y f$ and $Θ f$ have $f(f(f(⋯)))$ as their normal form and, thus, that $$Y = λf·Yf = λf·f(f(f(⋯))) = λf·Θf = Θ.$$ Going further, in fact, defining $U = λxλy·y(xy)$, we also have $$UY = λf·UYf = λf·f(Yf) = λf·Yf = Y.$$ Similarly, $UΘ = Θ$.

Therefore, allowing for infinite λ-terms, you have $Y = U(U(U(⋯)))) = Θ$. Thus, it also follows that $Y U = Y$ and $Θ U = Θ$.

Lots of references exist, now, on the infinitary λ-calculus. Here are a few, in the field: Infinitary lambda calculus, A New Coinductive Confluence Proof For Infinitary Lambda Calculus \[PDF\], Infinitary Rewriting Coinductively, All the λ-Terms are Meaningful for the Infinitary Relational Model, just for starters. I'm getting close to implementing it in the combinator cruncher Combo I put up on GitHub, now that I have a better understanding of how to convert them to (likewise infinitary) combinators. With the syntax that I've been using (by hand) the normal forms would just be $$Yf = x:f x = f(f(f(⋯))),\quad Y = x: U x = U(U(U(⋯)))),$$ to express the respective infinite terms in finite form.

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


# Question
Title: What are the fixed-points of the Y combinator?
Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.

# Answer
$U = λxλy·y(xy)$ is the fixed point of $Y$ and $Y$ is the fixed point of $U$.

How, and in what sense, I describe here: Equality Of (Infinitary) Lambda Terms.
> 1 votes

---
Tags: recursion, lambda-calculus, combinatory-logic, fixed-point
---


# Question
Title: Characterization of lambda-terms that have union types
Many textbooks cover intersection types in the lambda-calculus. The typing rules for intersection can be defined as follows (on top of the simply typed lambda-calculus with subtyping):

$$ \dfrac{\Gamma \vdash M : T\_1 \quad \Gamma \vdash M : T\_2} {\Gamma \vdash M : T\_1 \wedge T\_2} (\wedge I) \qquad\qquad \dfrac{} {\Gamma \vdash M : \top} (\top I) $$

Intersection types have interesting properties with respect to normalization:

* A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
* A lambda-term admits a type not containing $\top$ iff it has a normal form.

What if instead of adding intersections, we add unions?

$$ \dfrac{\Gamma \vdash M : T\_1} {\Gamma \vdash M : T\_1 \vee T\_2} (\vee I\_1) \qquad\qquad \dfrac{\Gamma \vdash M : T\_2} {\Gamma \vdash M : T\_1 \vee T\_2} (\vee I\_2) $$

Does the lambda-calculus with simple types, subtyping and unions have any interesting similar property? How can the terms typable with union be characterized?

# Answer
In the first system what you call subtyping are these two rules:

$$\dfrac{Γ, x:T\_1 \vdash M:S}{Γ, x:T\_1 ∧ T\_2 \vdash M:S}(∧E\_1)\quad\dfrac{Γ, x:T\_2 \vdash M:S}{Γ, x:T\_1 ∧ T\_2 \vdash M:S}(∧E\_2)$$

They correspond to elimination rules for $∧$; without them the connective $∧$ is more or less useless.

In the second system (with connectives $∨$ and $→$, to which we could also add a $⊥$), the above subtyping rules are irrelevant, and I think the accompanying rules you had in mind are the following:

$$\dfrac{Γ, x: T\_1 \vdash M:S\quad Γ, x:T\_2 \vdash M:S}{Γ, x:T\_1 ∨ T\_2 \vdash M:S}(∨E)\quad\dfrac{}{Γ, x: {⊥} \vdash M:S}({⊥}E)$$

For what it's worth, this system allows to type $(λx. I)Ω:A→A$ (using the ${⊥}E$ rule), which cannot be typed with just simple types, which has a normal form, but is not strongly normalizing.

---

*Random thoughts: (maybe this is worth asking on TCS)*

This leads me to conjecture that the related properties are something like:

* a λ-term $M$ admits a type not containing $⊥$ iff $MN$ has a normal form for all $N$ which has a normal form. ($δ$ fails both tests, but the above λ-term pass them)
* a λ-term $M$ can be typed without using the ${⊥}E$ rule iff $MN$ is strongly normalizing for all strongly normalizing $N$.

*Exercise:* prove me wrong.

Also it seems to be a degenerated case, maybe we should consider adding this guy into the picture. As far as I remember, it would allow to obtain $A ∨ (A → {⊥})$?
> 12 votes

# Answer
I just want to explain why intersection types are well-suited to characterize classes of normalization (strong, head or weak), whereas other type systems can not. (simply-typed or system F).

The key difference is that you have to say: "if I can type $M\_2$ and $M\_1→M\_2$ then I can type $M\_1$". This is often not true in non-intersection types because a term can be duplicated:

$$ (\lambda x.Mxx)N → MNN$$

and then typing $MNN$ means that you can type both occurrences of $N$ but not with the same type, for example $$M:T\_1→T\_2→T\_3 \qquad N:T\_1 \qquad N:T\_2$$ With intersection types you can transform this into: $$M:T\_1\wedge T\_2→T\_1\wedge T\_2→T\_3 \qquad N:T\_1\wedge T\_2$$ and then the crucial step is now really easy: $$(\lambda x.Mxx):T\_1\wedge T\_2→T\_3 \qquad N:T\_1\wedge T\_2$$ so $(\lambda x.Mxx)N$ can by typed with intersection types.

Now about union types: suppose you can type $(\lambda x.xx)(\lambda y.y)$ with some union type, then you can also type $\lambda x.xx$ and then get for some types $S, T\_1, \dots$ $$x : T\_1\vee T\_2 \vee \dots \vee T\_n ⊢xx:S$$ But you still have to prove that for every $i$, $x:T\_i⊢xx:S$ which seems impossible even is $S$ is an union type.

This is why I don't think there is an easy characterization about normalization for union types.
> 17 votes

# Answer
The standard approach is to expand the Curry-Howard Correspondence to cover disjunctions by providing cover for the tautologies: $$ O: (a ⊃ c) ⊃ (b ⊃ c) ⊃ a ∨ b ⊃ c,\quad : a ⊃ a ∨ b,\quad : b ⊃ a ∨ b,$$ and define $\[f,g\] = Ofg$, where $f: a ⊃ c$ and $g: b ⊃ c$, with $\[f,g\](x) = fx$, where $x: a$, and $\[f,g\](y) = gy$, where $y: b$, and also postulate (as an expansion of the η-rule) that each $h: a ∨ b ⊃ c$ can be expressed as $h = \[h ∘ , h ∘ \]$.

For something that's purely internal and self-contained as a language, just to improvise a possible solution: you'd have to expand the language to include the notion of *partially defined* terms, of *disjoint union* $f + g$ for partial functions $f$ and $g$ that have non-intersecting domains, and for the undefined function $0$. Then, we include the partial functions $: a ⊃ a ∨ b$ and $: b ⊃ a ∨ b$, such that $(x) = x$, for $x: a$, $(y) = y$, for $y: b$, with $(y)$ and $(x)$ both being undefined; i.e. $$ ∘ = I: a ⊃ a,\quad ∘ = 0: b ⊃ a,\quad ∘ = 0: a ⊃ b,\quad ∘ = I: b ⊃ b,\\ ∘ + ∘ = I: a ∨ b ⊃ a ∨ b,$$ with $$\[f,g\] = f ∘ + g ∘ .$$

This is similar to the upsampling and downsampling functions used in wavelet analysis.
> 1 votes

---
Tags: lambda-calculus, type-theory, logic
---


# Question
Title: Are all instructions eventually converted to zero-operand instructions?
Recently, my demonstrator said that all instructions are eventually converted to zero-operand instructions just before they get executed. yet another demonstrator said that this "doesn't make any sense", and I don't know who to believe; none of them really gave any logical arguments.

So, I want to know is any of them right at all? I tried searching for the answer but I didn't find anything.

# Answer
I agree with everyone else who said that this makes no sense. In fact, the opposite is closer to the truth: on most medium to high end CPUs that you will use today (i.e. everything from a mobile phone up), instructions are typically converted into *three*-operand instructions.

For example, if the CPU presents a two-operand addition instruction to the programmer, the CPU can convert this into a three-operand instruction using register renaming. By giving different names to the source and destination register, the CPU effectively eliminates WAR hazards.

Having said that, the microarchitecture may have a slightly different idea of what an "operand" is than a programmer is used to. Even if a source operand is a register, it could be filled in with an immediate value straight away if the CPU already knows the value (i.e. it doesn't depend on any previous unexecuted instructions). The destination of an instruction may not be a "register" (either physical or architectural), but a reorder buffer (ROB) entry, which allows for speculative execution.
> 3 votes

# Answer
This will depend on the computer architecture. zero-operand computer architectures use the stack, so to add 2+2:

1. PUSH 2 (into the stack),
2. PUSH 2 (again),
3. ADD (call the instruction - note that no operators are passed by).
4. POP ( 4 out of the stack)

but most other computer architectures e.g. use registers, memory addresses and values as the parameters to an instruction (in addition to the stack). For example the same 2+2 in a CISC computer.

1. MOX AX,02 (AX=0)
2. ADD AX,02 (AX=4)

However, if you're thinking in terms of translating a high level programming language into executable code e.g. one routine calling a subroutine the list of parameters most likely be passed by via stack and the number of parameters be reduced to 0 as in the first example.
> 1 votes

# Answer
It doesn't make sense to me at all.

Usually instructions are split into more primitive instructions more suitable for processing (sometimes instructions are *combined* into primitive instructions), those primitive instructions are put into a queue, together with information about their operands and results, then when all operands are available, the instruction with its operands are sent to an execution unit, and finally the result is sent to its destination.

I'd like to hear your first demonstrator explain how zero-operand instructions are supposed to work. I suspect there is some massive misunderstanding somewhere.
> 1 votes

# Answer
Many (but not all!) programming language implementations compile your human-readable source to some intermediate code.

The standard Java Virtual Machine (JVM), the Common Language Runtime (CLR), and many other runtimes / virtual machines require every operation in that intermediate code be be a zero-operand operand instruction, operating only on the stack. (In other words, each one is a "stack machine" in the comparison of application virtualization software ).

So when you are writing programs in Java and running them in the standard way, it's true that your code is converted entirely to zero-operand operations. This is true *regardless* of what physical machine eventually executes that intermediate code.

However, as @Pseudonym and others have pointed out, most physical hardware that we use to actually run that code are "register machines", where typically "operation" instructions each have 2 sources and 1 destination. So that intermediate code is usually *further* converted to multiple-operand instructions, since such instructions are the only kind that can be directly executed on most physical hardware. If you write in some other language (in particular, assembly language), then often your code is converted directly to such 2-operand or 3-operand instructions, which are later directly executed.

It is technically true that (given the same hardware to build them out of) a "stack machine" -- a CPU designed to process zero-operand instructions -- will have a faster clock rate than a "register machine" -- a CPU designed to execute multiple-operand instructions. But clock rate isn't everything ( megahertz myth ). A single zero-operand instruction is "faster" than a single multiple-operand instruction. But as the "stack\_machine" article points out, stack machines require more instructions to implement any particular piece of functionality, cancelling out some or all of that advantage.
> 1 votes

---
Tags: computer-architecture
---


title: Two Vs Dual Port RAM

text:
# Question
Title: Two Vs Dual Port RAM
Regarding the difference between Two Vs Dual Port RAM Here is what I understand:

The first can read and write at the same time but can't read twice or read twice at the same time while the second can read and write, read twice or write twice.

**Is this correct?**

**Plus,** Is this connected to software or hardware, let's suppose I have 2\*8=16GB Ram how can I convert them from Two port to Dual port?

# Answer
> 2 votes
There are many varieties of "dual-port RAM". Even though "two-port RAM" literally means the same thing, any one particular "dual-port RAM" may have big differences from some other "dual-port RAM".

Perhaps the most famous type is dual-ported video RAM, popular in the 1980s and 1990s, which supported reading and writing (but only one at a time) from one port (connected to a CPU) while simultaneously (only) reading from the other port (sending video data to the screen). That type doesn't match either of the descriptions in the original question.

Perhaps the most common type in recently-developed hardware are dual-port RAMs inside FPGAs. Some FPGA manufacturers use the terminology "true dual-port" to indicate two independent sides that can read and write, read and read, or write and write -- as mentioned in the original question -- while "simple dual-port" indicates the RAM has one write-only port and one read-only port.

"Soft CPUs" often include a register file with two or more dedicated read-only ports and one or more dedicated write-only ports.

# Answer
> 1 votes
In Dual port RAM write and read operation can be performed independently from both ports from any location as long as there is no collision

Where as in Two port RAM port A is dedicated for read and port B is dedicated for write operation

---
Tags: computer-architecture, cpu, memory-hardware
---


# Question
Title: A program detecting whether it's running in a virtual machine
I heard hypervisors try to make this undetectable to the client .A good hypervisor will have zero latency and be transparent.

*Can a program detect whether it's running in a virtual machine by trying to create a VM underneath it (and failing)?*

Or is a VM more like a subroutine call, where the context is passed to it and unquestioned?

Or do hypervisors forbid VM nesting?

Or what?

# Answer
I suggest reading about "VM detection", e.g., https://reverseengineering.stackexchange.com/q/1686, https://stackoverflow.com/q/39533/781723. There is lots written on this topic.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?
Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, *collectively*, every group consists largely of "strangers"?

For example, John, Paul, George, and Ringo being assigned together means John has been grouped with Paul a minimum amount of times, and George has been assigned together with Ringo a minimum amount of times, etc. Same with John and George, John and Ringo, Paul and George, etc. Not only that, but the other 5 groups must consist of people who are largely "strangers" to each other.

Here's the big kicker. Let's also say that week after week, the people are not the same. Sometimes new people get introduced to this group (substitutions). Some weeks there can be less people or more people. Order doesn't matter. How would I tackle this problem?

For full context, I am trying to automatically assign people in groups of 4 for a 2v2 volleyball league that plays every week, and I can't really count on people to show up every week.

# Answer
A standard approach that is very general is to formulate this as an instance of integer linear programming, and apply an off-the-shelf ILP solver. The field of operations research deals with a lot of combinatorial optimization problems, such as arise in scheduling and logistics, and ILP solvers are one standard tool for this (there are other tools as well).
> 0 votes

---
Tags: algorithms, combinatorics, assignment-problem
---


title: Building a XOR gate out of NOR gates

text:
# Question
Title: Building a XOR gate out of NOR gates
Can someone explain for me how to build a XOR gate using 5 NOR gates? The thing I'm looking for is a proof similar to this:

$A^B\ =\ (!A)B\ +\ A(!B)$

$=\ !!((!A)B)\ +\ !!(A(!B))$

$=\ !(!!A\ +\ !B)\ +\ !(!A\ +\ !!B)$

$=\ !(A\ +\ !B)\ +\ !(!A\ +\ B)$

$=\ !((A\ +\ !B)(!A\ +\ B))$

$=\ !(A(!A)\ +\ AB\ +\ (!A)(!B)\ +\ B(!B))$

$=\ !(AB\ +\ (!A)(!B))$

$=\ !(AB)(!(!A)(!B))$

$=\ !(AB)(!!A\ +\ !!B)$

$=\ !(AB)(A+B)$

$=\ !(AB)A\ +\ !(AB)B$

$=\ !!(!(AB)A\ +\ !(AB)B)$

$=\ !((!(!(AB)A))(!(!(AB)B)))$

# Answer
The brute force approach: There are 16 functions with two arguments, and 65,536 sets of such functions. Initially with 0 gates you have two functions: A and B.

Calculate all sets that you can build with one nor gate. You can implement a nor a = not a with one gate, or not b, or a nor b. So you create three sets by adding one of these three functions to your existing set.

Calculate all sets that you can build with two nor gates, by adding x nor y with x, y being any of the three existing set members. Then all sets needing three, four or five gates. And hope the last gate contains your expression.

This approach also lets you solve questions like “how do I implement these three functions simultaneously with the minimum number of nor gates”.
> 3 votes

# Answer
a xor b = x nor y. We need x, y so that x or y = not (a xor b) = (a and b) or (!a and !b). So we try to represent x = (a and b) using nor, and y = (!a and !b), then a xor b = x nor y.

y is easy: !a and !b = ! (a and b) = a nor b.

!a = a nor a, !b = b nor b, so x = ((a nor a) nor (b nor b)), and that’s it.

a xor b = ((a nor a) nor (b nor b)) nor (a nor b).
> 3 votes

---
Tags: boolean-algebra
---


title: Why is incompleteness important?

text:
# Question
Title: Why is incompleteness important?
Or take Russel's paradox. Either the barber does or doesn't shave himself -- *that's all there is.* How you describe it is an artificial construct.

Godel's theorem is like dividing by zero and declaring arithmetic incomplete.

It seems to me that all it means is, humans can construct artificial incomplete formal systems. You might as well assert that TRUE = FALSE and be amazed at the "paradox."

Is there some utility in believing that arithmetic is incomplete under pathological infinite recursion?

# Answer
> 4 votes
Russell's paradox and incompleteness are two different things. I begin with your question regarding Russell's paradox.

Russell's paradox showed that a proposed set theory, proposed for the foundation of mathematics itself, contained a contradiction:

> Let $R = \\{x \mid x \notin x \\}$, then $R \in R$ if and only if $R \notin R$.

From a contradiction, anything follows.

The main take-away here, was that any axiomatization of set theory containing unrestricted comprehension, must lead to a contradiction.

---

The (first) incompleteness theorem of Gödel, says

> Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$.

It has great impacts on mathematical logic and philosophy.

It means that there are *things* in maths that are true, but that cannot be proved by any argument (inside that mathematical system).

---
Tags: recursion, number-theory
---