# Question
Title: Converting context-free grammar to Chomsky/Greibach Normal Form
Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). If so why is it required?

Also my Professor said that we should convert a CFG into CNF before converting it to GNF. Is that required or can we straight away convert a CFG into a GNF?

# Answer
> 3 votes
You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which generates the same language as the original grammar). A given algorithm might require you first to remove lambda productions, or first to convert to Chomsky normal form. If using a specific algorithm, you have to follow whatever the algorithm prescribes.

# Answer
> 1 votes
> Is it necessary to remove \[lambda/unit rules\] before converting \[a CFG to CNF or GNF\]?

No, but it is necessary to remove them *as a part of* the conversion, because the definition of CNF and GNF imply that they do not occur in a grammar on those normal forms.

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix
Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form:

$F: (f\_1 \land f\_2 \land \ldots \land fn)$

where $f\_x$ is of the form

$f\_x \implies ai + bj + ck + dN + e \text{ } \\{\<,\>,=,\neq\\} \text{ } 0$

$f\_x$ is true if a point satisfies the aforementioned function and false otherwise

where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that

$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$

For example:
If $N = 4$, and $S = \\{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\\}$, we can say that the functions $f\_1 \implies i-k=0$ and $f\_2 \implies j-k=0$ are one solution for this set.

Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.

# Answer
> 2 votes
Yes. You can. You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$.

**Small simplifications.** Note that $d$ is unnecessary. $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$). So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$. Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$. Finally, I will assume you are looking for *integer* values of $a,b,c,e$, with no limit on how large or small they are.

**Finding a $f$.** Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$. There are several cases, according to which relational operator $f$ uses:

* Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns. For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns. You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations. Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.

In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.
* Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$. Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$. Form a system of inequalities obtained by all the points in $S$. Solving this then gives us a valid combination of values for $a,b,c,e$. There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.

You can improve this to check whether there exists a *single* linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution. If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done. If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:

Introduce unknowns $x\_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x\_{i,j,k} \le 1$. Add constraints $ai+bj+ck+e \ge x\_{i,j,k}$ for each $(i,j,k) \in S'$. Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum\_{(i,j,k) \in S'} x\_{i,j,k}$. This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.

If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.
* Less than: For $f$ of the form $ai+bj+ck+e \< 0$, we can adjust the above approach by using linear inequalities of the form $ai+bj+ck+e \< 0$ (or $ai+bj+ck+e \le -1$ if we require $a,b,c,e$ to be integers) and carrying on as before.
* Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.

**Finding $F$.** So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$. But how do we find a full $F$?

I don't know of any efficient way to find the optimal $F$. However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.

In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$. Define $T = \\{(i,j,k) \notin S : F(i,j,k)=\text{True}\\}$. Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.

Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible? Well, I've already described how. For each relational operator $\bowtie \in \\{=,\ne,\<,\>\\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible. This gives you four candidates for $f$. For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.

In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.

---
Tags: machine-learning, combinatorics, matrices, statistics
---


# Question
Title: Question about the definition of strings that GNFA's accept
In Sipser's "Introduction to the Theory of Computation" it states "A GNFA accepts a string $w$ in $Σ^{\*}$ if $w = w\_1 w\_2 · · · w\_k$ , where each $w\_i$ is in $Σ^{\*}$".

However, wouldn't a more precise definition be "A GNFA accepts a string $w$ in $Σ^{\*}$ if $w = w\_1 w\_2 · · · w\_k$ , where each $w\_i$ is in $Σ$" ?

# Answer
If a **GNFA** $A$ reconizes $\Sigma^{\*}$, then $\epsilon \in \Sigma^{\*}$ must be accepted. However $\epsilon \not\in \Sigma $.
> 0 votes

---
Tags: automata, finite-automata
---


# Question
Title: Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$
I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other.

Personally, I think that the simplification is possible. $O(A \times B \times C)$ is a polynomial growth, and (I think) it can be rewritten as $O(A^3)$, $O(B^3)$, or $O(C^3)$. On the other hand, $A^B$ is a exponential growth. As a result, it is possible to omit the left part from the Big O notation.

In other to test my hypothesis, I develop a simple simulation to compare $A \times B \times C$ with $O(A^B)$, the value of $A$, $B$ and $C$ range from 1 to 1000. According to my simulation, there are only $3\\%$ chance that $A \times B \times C \geq A^B$. It is enough to omit $A \times B \times C$ from $O(A \times B \times C + A^B)$?

# Answer
No, it is not possible. The function $ABC$ is $O(ABC + A^B)$ but not $A^B$, since for no $M$ is it the case that $ABC \leq MA^B$ for large enough $A,B,C$; for any "large enough" $A,B$, this would imply that $C = O(1)$ is bounded, but $C$ need not be bounded.
> 4 votes

# Answer
*No* you can't. As you said the three variables are independent of each other. If I want to study the complexity keeping $A$ and $B$ constant then the first term has significance as I can't bound $C$ if $A$ and $B$ are constant.
> 3 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Is there a standard recently-used algorithm based on time and usage count?
Everyone is familiar with most recently used files lists in software and in OSs like Windows.

Some programs just sort by time. I've always been fairly annoyed at this. Others like Windows take usage count into consideration. Some move the item halfway to the top each time it is used, which seems to make sense.

Rather than me blindly guessing at what combination of calculations might be nicest for my end users, is there some well-known most helpful standard for end-user recently-used lists?

(My searches turn up information about MRU caching, but I can't tell how applicable any of that is; it's server efficiency facing vs user efficiency facing.)

# Answer
This concept is indeed known in data structures as *self-adjusting/-organizing lists*. Possible strategies include

* move the accessed element to the front,
* maintain a sorted list by (potentially degrading) counts, and
* move the accessed element one step towards the front.

Many more strategies are possible; which is most suitable depends a lot on the specific situation.
> 2 votes

# Answer
The recently used file list is a sort of cache for your user that saves them lookups. There are many different caching strategies. Wikipedia has an overview article about Cache algorithms.

However, since you're dealing with humans here, a good caching algorithm for a computer might be confusing to your users. For example, random replacement is very simple to implement and works decently well for processor caches, but I would hate it if a program used that for its recently used file list. So maybe you want to do A/B testing, or other kinds of Usability engineering to find out what works best for your audience.
> 0 votes

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: Computer vision: object detection with labels that are single coordinates
Are there papers in the literature that address the following object detection task ?

The task can be described as follows:

* Given a set of images, the labels are just coordinates (x,y) that represent the object locations that we wish to detect. A coordinate is not necessarily at the centre of the object and the object can be of any size.
* The task is to detect an object that is either a person, a boat, or a car. However, the labels do not state the category of the objects, the labels are simply coordinates that are close to the objects of interest.
* The images are taken every hour and they are snapshots of the same scene; therefore, background subtraction techniques might help.
* There are around 2000 images of the same scene and each image usually has 2 objects of interest.

I am wondering if such task has been approached before ?

Hog features and SVM have shown great success in detecting humans in images. But the relevant literature use training data where the objects of interest are labelled using a bounding box instead of a single coordinate.

The three main challenges are:

* Choosing the bounding box for the classifier is difficult since objects can be of any size.
* snapshots of the scene is taken every hour (camera can move slightly as well); so using background subtraction isn't straightforward.
* we don't have much labelled data.

It would be interesting to see how people dealt with these challenges.

Thanks!

# Answer
> 4 votes
The state of the art in such problems is done these days via deep neural networks. Among others, two popular and recent approaches for solving the problem of detection and localization of objects are the YOLO paper, and the faster-RCNN, which run a classifier over many variously sized regions in an image.

As humans, boats and cars are popular object classes, I'd first attempt to see what existing pre-trained networks can do for your problem, and then, if needed, try and re-train them using your data.

---
Tags: machine-learning, image-processing, computer-vision, data-mining
---


# Question
Title: Using persistence on a constant database
I'm quite new to understanding persistent data structures, so bear with me.

Consider some database with data of the form $(\text{id}, d\_1, d\_2)$. The last two could e.g. mean production data and sales date, respectively. The database is constant, i.e. we will not be adding or removing data points.

Let $n$ be the number of items in the database. I want to be able to do the following query:

> Query$(a,b,s)$: Return the number of objects that have $a\leq d\_1 \leq b$ and $d\_2 \leq s$.

I want to be able to perform the query in $\mathcal O(\log n)$ time, with the best possible space and preprocessing time complexities. My question is how could one construct a persistent data structure that solves this problem?

I think that I need to use timestamps that relate to the $d\_1$ and/or $d\_2$ in some way. However, I'm not quite sure how.

# Answer
> 3 votes
Yes, you can do this in $O(\log n)$ time. Use a sweep-line algorithm together with a persistent tree data structure.

Imagine the point $(d\_1,d\_2)$ as being on a grid, with $d\_1$ as the value of the $x$-coordinate and $d\_2$ as the value of the $y$-coordinate. Your sweep line is a horizontal line, namely, at time $t$, the sweep line is the line $d\_2=t$.

You will build a data structure that stores all the points $(d\_1,d\_t)$ such that $d\_2 \le t$. You can use a balanced binary search tree, keyed on the value of $d\_1$. This data structure will let you answer the query Query$(a,b,t)$ in $O(\log n)$ time.

Now you're going to gradually increase the value of $t$ (sweeping the line upward), and adjusting the data structure as you go. You'll save a copy of the data structure for each value of $t$ that occurs in the $d\_2$-database.

This sounds like it requires $O(n^2)$ space. However, there's a clever trick. Use a *persistent* data structure to store the trees. As you move the sweep line upward, you insert more items into the tree. A persistent data structure will let you pick any time $t$ and do a lookup into the state of the tree at time $t$. This lets you answer Query$(a,b,t)$ in time $O(\lg n)$.

# Answer
> 2 votes
If your data are constant, most data structures are persistent. (Not self-adjusting ones like splay trees or the union-find structure of Tarjan)

You can do "three-sided range queries" with a priority search tree in $O(k + \log n)$ time, where $k$ is the number of items returned.

---
Tags: data-structures, persistent-data-structure
---


# Question
Title: How does this unsigned subtraction work?
Modern computers don't have circuits dedicated for subtraction. They do it by using the method of complements.

All is well when the 2 operands are signed 2's complement numbers. The result of addition will be another 2's complement which, when interpreted as a 2's complement number, will give the correct result provided that there's no overflow.

Now consider a 4 bit number. The unsigned range is 0 \<-\> 15. Signed range is -8 \<-\> 7.

What happens when I do 15u - 14u? The first thought which comes is "Do the 2's complement of 14 and do 15 + (-14)". But then, -14 is not in the range of a 4 bit number.

But if I do it anyway (Flip all bits and add 1):

```
   1111
 + 0010
------------
1  0001  =  0001 (4 bits)

```

It works. But 0010 is not even a negative 2's complement number. It is just 2. However, 0010 is the additive inverse of 14 for 4 bits. Is it a coincidence?

Question: Why does it work? And is this even the actual way it's happening?

# Answer
> 3 votes
In your example, what you are really doing is $$ 15 - 14 \equiv 15 + (16 - 14) \pmod{16}. $$ To compute $16 - 14$, you first compute $15-14$ (flipping all bits), and then add $1$ to get $16 - 14$.

---
Tags: computer-architecture, arithmetic
---


# Question
Title: Is there a paradigm for composing "incremental update" functions in a pure dataflow style?
I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.

**Background**, just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's mistake is to forget to update a cached value after changing one of its upstream sources/precedents. But the dataflow or FRP programming paradigm is immune to such mistakes. If we have a number of pure functions, and connect them together in a directed dependency graph, then nodes can have their output value cached and re-used until any of the function's inputs change. This system architecture is described in the paper Caching In Dataflow-Based Environments and in an imperative language it's more or less analogous to memoization.

**Problem**: When one of the inputs to a function do change, we still have to execute the function as a whole, throwing away its cached output and re-calculating from scratch. In many cases, this seems wasteful to me. Consider a simple example that generates a "top 5 whatever" list. The input data is an unsorted list of whatever. It's passed as input to a function that outputs a sorted list. Which in turn is input to a function that takes the first 5 items only. In pseudocode:

```
input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

```

The complexity of the sort function is O(N log N). But consider that this flow is used in an application where the input only changes a little bit at a time, by adding 1 element. Rather than re-sorting from scratch every time, it would be faster, in fact O(N), to use a function which updates the old cached sorted list by inserting the new element in the correct position. This is just one example - many "from scratch" functions have such "incremental update" counterparts. Also, maybe the newly added element won't even appear in the final\_output because it's after the 5th position.

My intuition suggests it might be possible to somehow add such "incremental update" functions to a dataflow system, side by side with the existing "from scratch" functions. Of course, re-calculating everything from scratch must always give the same result as a doing bunch of incremental updates. The system should have the property that *if* each of the individual primitive FromScratch-Incremental pairs always give the same result, *then* the larger composite functions built from them should also automatically give the same result.

**Question**: Is it possible to have a system/architecture/paradigm/meta-algorithm which can support both FromScratch functions and their Incremental counterparts, cooperating for efficiency, and composed into large flows? If not, why? If someone has researched this paradigm already and published it, what is it called, and can I get a short summary of how it works?

# Answer
> 8 votes
This field has been invented many times, and goes under many names, such as:

(And possibly more.) Those are not the same, but related.

Paraphrasing Cai et al (1): There are two core ways of implementing online algorithms generically (i.e. without reference to any specific algorithmic problem):

* **Static incrementalisation.** Static approaches analyse a program at compile-time and produce an incremental version that efficiently updates the output of the original program according to changing inputs. Static approaches have the potential to be more efficient than dynamic approaches, because no bookkeeping at runtime is required. Also, the computed incremental versions can often be optimised using standard compiler techniques such as constant folding or inlining. This is the approach investigated in (1).
* **Dynamic incrementalisation.** Dynamic approaches create dynamic dependency graphs while the program runs and propagate changes along these graphs. The most well-know approach is Acar's self-adjusting computation. The key idea is simple: programs execute on the original input in an enhanced runtime environment that tracks the dependencies between values in a dynamic dependence graph; intermediate results are cached. (As you might imagine, this tends to use a lot of memory, and much research in this field is about how to limit memory usage.) Later, changes to the input propagate through dependency graphs from changed inputs to results, updating both intermediate and final results; this processing is often more efficient than recomputation. However, creating dynamic dependence graphs imposes a large constant-factor overhead during runtime, ranging from 2 to 30 in reported experiments.

In addition, one can always try and come up 'by hand' with an online version of a given algorithm. This can be difficult.

---

<sup> (1) Y. Cai, P. G. Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for Higher-Order Languages: Incrementalizing λ-Calculi by Static Differentiation. </sup>

# Answer
> 1 votes
You are probably looking for adaptive programming. See also Umut Acar's PhD thesis. I am not up-to-date with this area of work but it should get you started, you can chase up references.

---
Tags: terminology, reference-request, functional-programming, programming-paradigms
---


title: Simplified Maximum Diversity Problem

text:
# Question
Title: Simplified Maximum Diversity Problem
The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized.

I have a simpler problem, which I was hoping I could solve in a simpler manner. In my case I have a list of $n$ items each with a certain non-unique key. I want to chose $m$ items from my list so that the **maximal number of items per key is minimized**.

e.g., if my list is:

```
('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)

```

and we must choose $m=3$ items, an optimal solution would be a list containing one item for each key.

Is there an algorithm for doing this that is simpler than those for the Maximum Diversity Problem?

# Answer
Thinking about it a a bit more, I think I have a "one pass" algorithm for solving this.

Let there be $n$ items with $k$ keys, with $n\_i$ items for each key. We want to choose $m\_i\le n\_i$, such that $\sum m\_i = m$, and that $\max{m\_i}$ is minimized.

Clearly, if for all $n\_i$ we have $n\_i \> m/k$, we simply choose $m\_i = m/k$. Otherwise, we use the following algorithm:

1. Count the number of items for each key ($n\_i$) and sort them in ascending order.
2. While $n\_i \le m/k$ set $m\_i=n\_i$
3. For all $n\_i \> m/k$, choose $m\_i = \left\lceil \frac{m - \sum\_{j\<i} m\_j}{k-i+1}\right\rceil$

This algorithm should be $O(n)$ in the length of the list, assuming the number of different keys is negligible in comparison.
> 3 votes

# Answer
The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take **one** item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Comparing the sizes of two search spaces by comparing their numbers of possibilities
I am trying to solve an optimisation problem and come up with two Integer Linear Programming models. For each model, I am able to find a function that calculate the number of possibilities based on different variables, e.g. problem sizes.

I cannot directly conclude that one model has a smaller search space than the other. Instead, I develop an application that compares the actual numbers of possibilities between 2 models based on different values of the variables.

My application tries millions of different variables and shows that the number of possibilities of one model is less than the other 99% of the time. Is it enough to conclude that it is likely for one model to have the smaller search space, and to be solved faster than the other?

# Answer
There is no easy way to predict which ILP model will be faster to solve. Counting the number of variables is not a reliable predictor. Estimating the size of the "search space" (the number of feasible solutions) is not a reliable predictor. There is, in general, no fully reliable way to tell which model will be faster -- short of actually trying both.

Instead, my recommendation is that you try experiments. Try solving both models, and see which takes longer to solve. If your problem is parameterized in size, you can try solving for smaller sizes and see if a pattern emerges.
> 1 votes

---
Tags: complexity-theory, linear-programming, integer-programming
---


title: Trying to Explain Objects

text:
# Question
Title: Trying to Explain Objects
After a year hiatus from Computer Science courses in college, im back to hitting them hard for the next two years straight. In the next few weeks before classes start again I have been trying to refresh my memory on key concepts by writing and trying to explain them to people that have never gotten deeper into a computer than Word, or Excel, maybe even just Photoshop.

Right now i'm trying to explain Objects and Classes, using the cookie cutter is a class and a cookie is an object.

In trying to explain Objects I thought that starting with trying to describe a Cookie would be easy and I described it like so.

```
Dinosaur_Cookie_Name = "T-Rex"
Dinosaur_Cookie_Frosting_Colour = "Green"
Dinosaur_Cookie_Eaten = False

```

And then I was going to explain how these have no linking between them and that if you wanted to say that

```
my_cookie = Dinosaur_Cookie_Name

```

it doesn't necessarily mean that it's also green and uneaten.

So I was then going to explain that by making `my_cookie` a list, you could then iterate through the list to access properties and tada, a sort of rudimentary object. Afterwards would then be, tada here is what an object is.

That's where I froze. In the year since learning about Objects in my beginning C++ class I couldn't remember how I made the jump TO Objects. I remember a little talk about name spaces and pointers but thats about it.

So do objects store properties in an array? Would it be appropriate in teaching about Objects to have a middle step of a list, between non-associated variables and an object?

# Answer
> 1 votes
**Car**

My favourite explanation of objects/classes is centered at cars.

---

**Class**

Class is defined as a **schematic** of information you can "measure from" or "store in" a car instance. For example, every car has a color, production date, total distance passed, etc.

---

**Object**

Objects are "real" or "existant" things made upon a class (schematic). All the cars consist of properties such as color and distance traveled, but the actual values of these properties may vary.

---

**Implementation**

Object implementation may differ between languages and compilers, but I guess this might be a good way to do it:

Calculate space needed for all subobjects/properties (pointers/ints/strings/other objects) which reside in the object itself. On object creation, take up **precalculated memory**. Functions inside classes (methods) are no different than "normal" functions, it is just that compiler enforces them to be called **on object** or **inside of** fashion due to object-oriented programming philosophy.

When you try to get/set certain property of an objects, compiler actually translates it into **memory offset** from start of objects memory, so yes, you couldsay it acts like array with different data types in it.

---
Tags: programming-languages, object-oriented
---


# Question
Title: Why we cannot prove that a computable function is total?
We know that we cannot find an algorithm that would prove that a computable function "f" is total if it IS total. How come?

When a function is total, it must have a proof (derived from soundness and correctness of logic). And proof is a finite sequence of symbols, so why does simple enumeration through all the sequences (which ends in finite time) not provide us with a proof?

# Answer
You misunderstand soundness and completeness of logic. You think that it says:

> A statement is true if, and only if, it is provable.

But it really says:

> A statement is true *in every model* if, and only if, it is provable.

It *can happen* that there is a model in which a statement is true but not provable. What if you live in such a model? Then it could happen that in the model in which you live there is a total function $f$, but there is no proof that $f$ is total.

---

Here is a precise mathematical reason why your thinking does not work. I am going to show that, whatever formal system you are using (so long as it is a reasonable one), there is a total function which your formal system does not prove to be total.

You do proofs in some formal system $T$ (for instance, $T$ could be first-order logic and Zermelo-Fraenkel set theory) whose axioms are computably enumerable (or else you're a mystic guru). Let us also assume that $T$ contains arithmetic, and that $T$ is consistent (or else you're mad).

Define the following function `f`

```
def f(n):
    if n encodes a proof of 0 = 1 in formal system T:
        while True: pass
    else:
        return 0

```

Observe that `f` is total if, and only if, $T$ is consistent:

* if $T$ is consistent then it does not prove $0 = 1$, hence `f` never enters the infinite `while` loop.
* if `f` is total, then it never enters the infinite `while` loop, therefore no $n$ encodes a proof of $0 = 1$ in $T$, therefore there is no proof of $0 = 1$ in $T$, which means that $T$ is consistent.

Because $T$ is consistent, `f` is total.

But $T$ does not prove that `f` is total: if it did, then it would prove that, for every $n$, $n$ does not encode a proof of $0 = 1$, but this would imply that $T$ proves its own consistency, which it cannot by Gödel's incompleteness theorem.

**Supplemental:** Ideas about having multiple theories $T\_0, T\_1, T\_2, \ldots$ are quashed by (where `unpair` is a bijection $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$):

```
def g(n):
    (i, j) = unpair(n)
    if i encodes a proof of 0 = 1 in formal system T(j):
        while True: pass
    else:
        return 0

```

Now $g$ is total if and only if all $T\_i$'s are consistent, but no $T\_j$ can prove that they are all consistent (if it could, it would prove its own consistency as well).
> 11 votes

# Answer
> so why does simple enumeration through all the sequences (which ends in finite time) not provide us with a proof?

That idea could maybe give you a semi-decider, but certainly not a decider -- you don't know a size bound on the proof! That is, you can never say "no, it's not total" after finite time.

Note, though, that the idea has to be fundamentally flawed; the set of total functions is not enumerable.
> 1 votes

# Answer
"It must have a proof" - no, not necessarily. For example, write a program that for each even integer n ≥ 4 finds the smallest prime p such that n-p is also a prime, and doesn't halt if such a p does not exist. This is very, very likely to be a total function. But currently there is no prove known. And it is quite possible that no prove exists.

Someone remarked that this was a weak example and not convincing. OK, the fact is that with this easy to understand problems the worlds greatest mathematicians don't agree at all that a total function would have a proof of totality. So "it must have a proof" is a claim that you are more clever than the worlds greatest mathematicians.

And someone will be able to find a total function where the existence of a proof that it is total leads to a contradiction.
> 0 votes

---
Tags: computability, undecidability, decision-problem
---


# Question
Title: Deciding which logical proposition is stronger
I am studying propositional logic and I am trying to solve some exercise related to the following definition:

Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger than $\beta$ if and only if $(\alpha \implies \beta)$ is a tautology. Determine which of the two propositions is stronger in the following cases:

1) True, False

2) True, True

3) False, False

I am a bit confused with this problem. I've seen that for True we always assign the value $1$ and for False, the value $0$. So, (True $\implies$ False) has always value $0$ (actually, there is one possibility) and (False $\implies$ True) has always value $1$ (there is also one possibility). This means that (False $\implies$ True) is a tautology, so False is stronger than True.

I am not sure if what I've said above is correct and I am lost in 2) and 3), I would appreciate some help. Thanks in advance.

# Answer
> 6 votes
The notion of strength of a proposition comes from its power to constrain the model. For instance the proposition $P1 : x = 2$ is stronger than $P2 : x \geq 2$ in Arithmetic. And in propositional notation this can be written as $P1 \Rightarrow P2 $.

The stronger the proposition the harder it usually is to prove. On the other hand, if proven it provides more corollaries.

For instance for a signature with 2 propositional symbols $P$ and $Q$ we have the following partial diagram for the *Strength* relation.

Now to your examples. $\textrm{False}$ happens to be an extreme case. It can never be satisfied. If you are using propositions to constrain your search space for an answer, then $\textrm{False}$ says: "*Call off the search and start again*". The other extreme is the proposition $\textrm{True}$. It is trivial. It gives absolutely no information on where to look for the answer.

Now we shall use this intuition to tackle your questions:

1) True, False

Since $\textrm{True}$ is a trivial constraint, you would not be able to derive anything non-trivial out of it, this certainly means that you would not be able to derive the extreme constraint $\textrm{False}$.

> $\not\vdash \textrm{True} \Rightarrow \textrm{False}$

2) True, True

The propositions have exactly the same strength, they are equivalent

> $\vdash \textrm{True} \Rightarrow \textrm{True}$

3) False, False

The propositions have exactly the same strength, they are equivalent

> $\vdash \textrm{False} \Rightarrow \textrm{False}$

And an extra case

4) False, True

> $\vdash \textrm{False} \Rightarrow \textrm{True}$

**Note:** there is an issue with saying that proposition $P$ is stronger than $Q$ if $P \Rightarrow Q$ is a tautology since intuitively the relation of being stronger is strict. It would better align with the intuition if we were to say that ***proposition $P$ is stronger than $Q$ or of equal strength*** if and only if $P\Rightarrow Q$.

---
Tags: logic, propositional-logic
---


title: Bounded bin covering problem

text:
# Question
Title: Bounded bin covering problem
This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name.

I have a multiset $S$ of $n$ (not necessarily unique) integers in the range $\\{1,2,\dots,k-1\\}$.

The problem is to partition this multiset in submultisets such that each submultiset has a sum of *at least* $s$ and the number of submultisets is maximized.

For example $k=20 \wedge s=40 \wedge S= \\{14, 19, 12, 19, 3,15\\} \Rightarrow \\{\\{19, 19, 3\\}, \\{12, 14, 15\\}\\}$.

Is this a known problem? What is its complexity, considering $s, k$ are **bounded small integers**?

# Answer
When $k,s$ are upper-bounded by a constant, the problem can be solved in polynomial time.

Call a multiset $T$ *good* if its sum is at least $s$, and if removing any one element causes the sum to fall strictly below $s$, and if all elements are in the set $\\{1,2,\dots,k-1\\}$. How many good multisets are there? Well, since $k$ and $s$ are constants, the number of such multisets is also a constant. (A very crude upper bound is $k^s$, which is a constant.)

Let's write down an integer linear program that is equivalent to your problem. We'll have an integer variable $x\_T$ for each good multiset $M$, constrained so that $x\_T \ge 0$. The idea is that $x\_T$ will count the number of times $T$ appears in the partition that constitutes the solution to your problem. We obtain $k-1$ linear equations of the form

$$\sum\_T m\_T(i) x\_T = m\_S(i)$$

for each $i \in \\{1,2,\dots,k-1\\}$, where $m\_T(i)$ denotes the multiplicity of $i$ in $T$. Now our goal is to maximize $\sum\_T x\_T$, the number of multisets in the resulting partition.

Thus, we obtain an integer linear program in constant dimension: i.e., it has (at most) a constant number of variables and (at most) a constant number of linear inequalities. It is known that integer linear programming in constant dimension can solved in polynomial time. Therefore, your problem can be solved in polynomial time, too.

---

Of course, this doesn't necessarily mean the algorithm will be efficient in practice. The constants that are hidden by asymptotic analysis are potentially huge.

---

As a side note, if $k,s$ are part of the input (not fixed) and all integers are provided in binary, the problem is NP-hard. The special case where $s = \frac12 \sum\_{i \in S} i$ is equivalent to the partition problem, which is NP-complete so your problem is NP-hard as well, assuming $k$ is part of the input. So your promise that $k,s$ are upper-bounded by a constant makes a crucial difference to the complexity of your problem.
> 3 votes

---
Tags: complexity-theory, partitions
---


title: Why does a processor have 32 registers?

text:
# Question
Title: Why does a processor have 32 registers?
I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the RAM?

# Answer
> 92 votes
First, not all processor architectures stopped at 32 registers. Almost all the RISC architectures that have 32 registers exposed in the instruction set actually have 32 integer registers and 32 more floating point registers (so 64). (Floating point "add" uses different registers than integer "add".) The SPARC architecture has register windows. On the SPARC you can only access 32 integer registers at a time, but the registers act like a stack and you can push and pop new registers 16 at a time. The Itanium architecture from HP/Intel had 128 integer and 128 floating point registers exposed in the instruction set. Modern GPUs from NVidia, AMD, Intel, ARM and Imagination Technologies, all expose massive numbers of registers in their register files. (I know this to be true of the NVidia and Intel architectures, I am not very familiar with the AMD, ARM and Imagination instruction sets, but I think the register files are large there too.)

Second, most modern microprocessors implement register renaming to eliminate unnecessary serialization caused by needing to reuse resources, so the underlying physical register files can be larger (96, 128 or 192 registers on some machines.) This (and dynamic scheduling) eliminates some of the need for the compiler to generate so many unique register names, while still providing a larger register file to the scheduler.

There are two reasons why it might be difficult to further increase the number of registers exposed in the instruction set. First, you need to be able to specify the register identifiers in each instruction. 32 registers require a 5 bit register specifier, so 3-address instructions (common on RISC architectures) spend 15 of the 32 instruction bits just to specify the registers. If you increased that to 6 or 7 bits, then you would have less space to specify opcodes and constants. GPUs and Itanium have *much* larger instructions. Larger instructions come at a cost: you need to use more instruction memory, so your instruction cache behavior is less ideal.

The second reason is access time. The larger you make a memory the slower it is to access data from it. (Just in terms of basic physics: the data is stored in 2-dimensional space, so if you are storing $n$ bits, the average distance to a specific bit is $O(\sqrt{n})$.) A register file is just a small multi-ported memory, and one of the constraints on making it larger is that eventually you would need to start clocking your machine slower to accommodate the larger register file. Usually in terms of total performance this is a lose.

# Answer
> 18 votes
Just two more reasons for limiting the number of registers:

* Little gain to be expected: CPU such as current Intel/AMD x64 models have 32kByte and more of L1-D cache, and access to the L1 cache usually takes only one clock cycle (compared to about a hundred clock cycles for a complete single RAM access). So there is little to be gained from having more data in registers compared to having data in the L1 cache
* Additional computational costs: Having more registers creates an overhead that may actually make a computer slower:
    + In multitasking-environments, a task switch usually has to save the contents of all registers of the process that is left to memory, and has to load those of the process to be entered. The more registers you have, the longer this takes.
    + Similarly, in architectures without register windows, cascaded function calls use the same set of registers. So a function A calling a function B uses the same set of registers as B itself. Therefore, B has to save the contents of all registers it uses (which still hold A's values) and has to write them back before returning (in some calling conventions it is the job of A to save its register contents before calling B, but the overhead is similar). The more registers you have, the longer does this saving take, and thus the more expensive a function call becomes.

# Answer
> 4 votes
A lot of code has lots of memory accesses (30% is a typical figure). Out of that, typically about 2/3rds are read accesses and 1/3rds are write accesses. This is not due to running out of registers as much as accessing arrays, accessing object member variables etc.

This HAS to be done in memory (or data cache) due to how C/C++ is made (everything you can get a pointer needs to have an address to has to be potentially stored in memory). If the compiler can guess that you won't write to variables willy-nilly using crazy indirect pointer tricks it will put them in registers, and this works great for function variables but not for globally accessible ones (generally, everything that comes out of malloc()) because it's essentially impossible to guess how the global state will change.

Because of this, it's not common that the compiler will be able to do anything with more than about 16 general usage registers anyways. Which is why all popular architectues have about that many (ARM has 16).

MIPS and other RISCs tend to have 32 because it's not very hard to have that many registers - the cost is low enough so it's a bit of a "why not?". More than 32 is mostly useless and has the downside of making the register file longer to access (each doubling in the number of registers potentially adds an extra layer of multiplexers which adds a bit more delay...). It also makes instructions slightly longer on average - which means that when running the kind of programs that depend on instruction memory bandwidth, your extra registers are actually slowing you down!

If your cpu is in-order and doesn't do register renaming and you're trying to do lots of operations per cycle (more than 3), then in theory you need more registers as your numbers of ops per cycle goes up. This is why the Itanium has so many registers! But in practice, apart from numerical-floating-point or SIMD oriented code (which Itanium was really good at), most code will have lots of memory reads/writes and jumps which make this dream of more-than-3 ops per cycle impossible (especially in server-oriented software like databases, compilers, high-level language execution like javascript, emulation etc...). This is what sank Itanium.

It all comes down to the difference between computation and execution!

# Answer
> 2 votes
Who tells you that processor **always** have 32 registers? x86 has 8, ARM 32-bit and x86\_64 have 16, IA-64 has 128, and many more other numbers. You can have a look here. Even MIPS, PPC or any architectures that have 32 general purpose registers in the instruction set, the number is much larger than 32 since there are always still flag registers (if any), control registers... not including renamed registers and hardware registers

Everything has its price. The larger the number of registers, the more work you have when doing task switching, the more space you need in the instruction encoding. If you have less register, you don't have to store and restore much when calling and returning from functions or switching tasks with the trade off of lacking of registers in some compute-extensive code

Moreover, the larger the register file, the more expensive and complex it will be. SRAM is the fastest and most expensive RAM so it is only used in CPU cache. But it's still much cheaper and takes less area than a register file with the same capacity.

# Answer
> 2 votes
For example, a typical Intel processor has "officially" 16 integer and 16 vector registers. But in reality, there are many more: The processor uses "register renaming". If you have an instruction reg3 = reg1 + reg2 you would have a problem if another instruction using reg3 hadn't finished yet - you couldn't execute the new instruction in case it overwrites reg3 before it has been read by the previous instruction.

Therefore there are about 160 or so *real* registers. So the simple instruction above is changed to "regX = reg1 + reg2, and remember that regX contains reg3". Without rename registers, out of order execution would be absolutely dead in the water.

# Answer
> 1 votes
I am not an electrical engineer, but I think another possibility for the reason to limit the number of registers, is routing. There are a limited number of arithmetic units, and they must be able to take input from every register, and output to every register. This is especially true when you have pipelined programs that can execute many instructions per cycle.

A simple version of this would have $\mathcal O(n^2)$ complexity, making increasing the number of registers unscalable, or otherwise requiring a redesign of the routing to something a lot more complicated to route everything with a better complexity.

I got the idea for this answer from watching some of Ivan Godard's talks on the Mill CPU. Part of the innovation of the Mill CPU is that you cannot output to arbitrary registers - the outputs are all pushed onto a register stack or "belt", which thus reduces routing problems, because you always know where the output will go. Note they still have the routing problem for getting the input registers to the arithmetic units.

See The Mill CPU Architecture - the Belt (2 of 9) for the problem statement, and Mill's solution.

# Answer
> 1 votes
As for the MIPS ISA, Hennessy and Patterson, *Computer Organization and Design* 4th edition p. 176, answers this specific question directly:

> Smaller is faster. The desire for speed is the reason that MIPS has 32 registers rather than many more.

---
Tags: computer-architecture
---


title: Square sub-grid with maximum sum

text:
# Question
Title: Square sub-grid with maximum sum
Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must have side length less than $L$ (given integer).

$ 1\le N \le 100000$, $1 \le L \le 100000$ , $1 \le x\_i \le100000$, $1 \le y\_i \le 100000$, $1 \le \text{weight}\_i \le 10^9$, where $i$ is the $i^{th}$ point.

I have tried using prefix sum array and iterating over all the possible square sub-grids, but this is not efficient.

I need to know in which direction should I start thinking.

# Answer
Firstly you did not write the complete question, to complete it, if $S$ is the maximum sum of weights in any sub-grid of lenght $ \le L$, then we have to report $S$ and length of the sub-grid with smallest integral side where sum of weights inside it is $S$ ( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to you to figure out. In this answer my aim is to *calculate $S$*.

---

Now we come to some pre-requisites for solving the problems. Firstly you should be comfortable with segment tree implementation. Second you need familiarity with binary search. Lastly I also assume ( as you have mentioned ) you also have familiarity with computing the prefix/suffix sum arrays. Plus I assume the points are given in the array $arr$ .

---

Now I describe the algorithm.

1. It can be argued that one of the corner points of the square sub-grid we make should be a point from the set of points that is given to us. Thus for each point from $(x,y)$ from the set of points given to us, we consider the four possible squares, one with $(x,y)$ as bottom left corner, one with $(x,y)$ as top right corner, one with $(x,y)$ as bottom right corner and one with $(x,y)$ as bottom left corner.
2. I describe it for one case say when $(x,y)$ is bottom left corner of a square grid with size $L$ ( as to calculate $S$ we should take the side of the square sub-grid as long as possible which is $L$ ). That is our question reduces to finding the sum of weights of points in the *red* region in the figure below.
3. I have labelled the sum of weights of the other eight regions by using letters $a$-$h$. One way to calculate the sum of weights of the red region is to subtract the from total $a+b+c+d+e+f+g+h$.
4. I can calculate $b+a+h$ by using combination of binary search and prefix/suffix sum arrays. In a similar manner I can find the sums $b+c+d$,$d+e+f$ and $h+g+f$. But now the problem is that I have summed each of $b$,$h$,$d$ and $f$ twice. Thus I need to find the sum of weights $b$,$h$,$d$ and $f$ separately.
5. You can find the sum $h$ ( and similarly the three others ) using segment tree in $O(log(n)^2)$ where $n$ is the total number of points given. The trick is to build the segment tree on say the $x$ co-ordinate. And if there is a node in the segment tree denoting the range $i$-$j$ ( $1 \le i \le j\le n$ ) then that node should store the $y$ co-ordinates of all points of array $arr$ from index $i$ to $j$ in sorted order, plus a suffix sum array for the same sorted array ( this is the main point, comment if you can't understand ). In this way by combination of querying on segment tree and binary search ( thus the $O(log(n)^2)$ factor comes ) you can find the sum of weights $h$.
6. So in nutshell you repeat the procedure for each point from the given set and for each point you try all $4$ square-sub grids of length $L$ and then select the one having maximum sum of the red region overall. The complexity will come out to be $O(nlog(n)^2)$ which is sufficient to pass the online judge.
> 2 votes

---
Tags: algorithms, square-grid
---


# Question
Title: What will be the time complexity of this function (C++) and why?
The function:

```
double sum1(std::vector& v)
{
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

```

There are `n-1` sorts each one shorter by 1, so time taken by the function for `n` elements will be:

```
T(n) = C*n + n*log(n) + (n-1)*log(n-1) + ... + 2*log(2) + 1*log(1)

```

How to solve this polynomial? Or I missed something?

# Answer
How to solve the polynomial: Clearly it's less than n * n * log (n) = O (n^2 log n). And clearly it is more than (n/2) * (n/2) * log (n/2) = O (n^2 log n). So it's n^2 log n.

However, your assumption that the sort is O (n log n) is not justified. Each time except the first you are sorting an array that is already sorted with the exception of the first array element. Many sort implementations will sort that kind of array in O (n), so the total time may be just O (n^2).
> 2 votes

# Answer
Standard c++ std::sort implements **quicksort** algorithm, switching to mergesort if recursion is too deep.

---

Quicksort algorithm takes $\Omega(n\*log(n))$ time in the best case, so you could assume repeating it $O(n)$ times will give a $O(n^2\*log(n)$ time.

The thing which **just might break our lower bound** is the structure of your algorithm. If quicksort takes the last/first element (new element added to sorting on each iteration) it will break into **sorting the sorted array** on 1st recursive subcall, invoking its worst case performance of $O(n^2)$. This will bring your algorithms complexity up to $O(n^3)$.

Note that this fault is valid only if quicksort does always use first/last pivot. If randomization is doing the work of selecting a pivot, the runtime in the average and best case is $O(n^2\*log(n))$, and $O(n^3)$ in worst case (rare).

---

Let us assume that your std::sort uses insertion sort. Insertion sort performs best on already sorted algorithms, and just needs to insert the last element added into its place in $O(n)$. This would make the whole algorithm run in $O(n^2)$.

---

This example is a perfect explanation of why it is imporant to learn underlaying **aspects of sorting algorithms** before **relying on particular boxed function**.
> 2 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Is huffman-encoding with distinct frequencies of symbols unique?
Say I have following text: "abbcccddddeeeee". As you can see, each letter has a different frequency of occurence. When making a Huffman-Trie to encode this String, will this trie be unique?

I thought a bit on the problem and I can't come to a definite conclusion, but I think the trie will NOT be unique. Say the begin-situation:

```
a(1) b(2) c(3) d(4) e(5)

```

To make a trie, we take the lowest frequencies together and make a node above it with the sum of those frequencies. Because the frequencies are all ascending, there is only 1 way to take the lowest nodes. In this case, a and b. If we keep going on further, it wel never occur that we need to choose 2 subtries out of a larger collection, there will always be just 2. When seeing this, you could conclude the trie will be unique BUT. I see never stated in which order the two subtries need to be added. For example, to make the first new subtrie, we can put node a left OR right of node B. We can do this at each level and eventually, this will flip some bits in the end-result.

Am I correct?

# Answer
`2 3 4 5` is a counterexample:

`4 5 5` (combine 2 and 3 to make 5, and reorder)

Now there are 2 choices for `4` to partner with: either the original `5`, or the one formed by `2+3`.
> 6 votes

---
Tags: algorithms, algorithm-analysis, data-compression, huffman-coding
---


title: An integer linear program

text:
# Question
Title: An integer linear program
I have the following problem:

> Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.

I'll be very grateful for any tips about which method could be used to solve this.

# Answer
If you google for Integer Linear Programming, you'll find that the problem is in general NP-complete. However, your subproblem with just one restriction and two variables isn't difficult to solve.

Have a look at https://en.wikipedia.org/wiki/Cutting-plane\_method and especially Gomory's method: You first use the Simplex algorithm to find the optimal solution without considering that the solution should be integers. If by coincidence your optimal solution is integer, you solved the integer linear programming problem. Otherwise, you use Gomory's method to find another restriction which isn't fulfilled by the non-integer solution you found, but by every integer solution of the original problem. You solve the system with the new equation, and repeat until you have an integer solution.
> 2 votes

---
Tags: optimization, linear-programming, integer-programming
---


# Question
Title: Implement K-means clustering with Map-Reduce
Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around to do it using Map Reduce(I know what Map Reduce is). Can someone provide me an explanation/algorithm of how to do that? More specifically I am looking what Map and Reduce phases will look like for such an implementation? I was also asked how many Mappers and Reducers will I need?

# Answer
> 5 votes
You can run a loop over $j\in\\{1..k\\}$:

1. Create a map that maps each point $x\_i$ to itself if $x\_i$ is nearest to the mean $m\_j$, and to the zero vector otherwise: $$x\_i \rightarrow \begin{cases}(x\_i, 1) & d(x\_i, m\_j) \le d(x\_i, m\_l),\ l\neq j \\ (0,0) & \text{otherwise} \end{cases}$$
2. In the reduce stage, you would find the sums and counts: $$(x\_{i1}, c\_1), (x\_{i2}, c\_2)\rightarrow(x\_{i1}+x\_{i2}, c\_1+c\_2)$$ You then divide the resulting sum by the total count.

Thus, for each iteration in the k-means algorithm you will need $k$ maps and $k$ reduces.

---
Tags: algorithms, parallel-computing, clustering, mapreduce
---


# Question
Title: constructing a DFA and a regular expression for a given regular language
This is the question 1.12 from Introduction to the Theory of Computation 3rd Edition by Michael Sipser. The questions says,

> Let $D=\\{w\mid w$ contains an even number of $\texttt{a}$'s and an odd number of $\texttt{b}$'s and does not contain the substring $\texttt{ab}$}. Give a DFA with five states that recognizes $D$ and a regular expression that generates $D$.

I was able to construct a  by using the intersection operation on the three simpler parts of $D$. I think that the regular expression that would generate $D$ is `b(bb)*(aa)*` but I'm not sure about it.

Is my regular expression correct? If yes, then if I apply the subset construction algorithm on  diagram (eps denotes ε) and minimize the resultant DFA, I should get the minimal DFA that I constructed through intersection, right?

# Answer
I was able to solve this question using two possible routes.

The **1st route** involves constructing the DFA by using the intersection operation on the simpler parts of $D$, *i.e.*,

$\\{$even number of $a$'s$\\} \cap\\{$odd number of $b$'s$\\}\cap\\{$does not contain the substring $ab\\}$

After that, I was able to reduce the DFA into a RegEx using the *State Elimination Method* and *Arden's Lemma*. The regular expression can be achieved by using Arden's Lemma as follows.

$$1\to a2+b4$$

$$2\to a2+b2$$

$$3\to a5+b2+\varepsilon$$

$$4\to a5+b1+\varepsilon$$

$$5\to a3+b2$$

Note that $2\to a2+b2$ will resolve as $2\to \varnothing$ and not $2\to (a+b)^\*$.

The **2nd route** involves "knowing" that the regular expression is $b(bb)^\*(aa)^\*$ by analyzing the language $D$. This RegEx can be converted to an ε-NFA. After that, we can convert this ε-NFA to get a DFA which when minimized would give us this.
> 1 votes

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


# Question
Title: Prove that PP is closed under complement
I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain:

> By the definition of PP there is a polynomial-time probabilistic algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr} \[A(x) = 1\]\>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} \[A(x) = 1\]\leq \frac{1}{2}}$.
>
> Let $f(|x|)$ be the polynomial upper bound on the running time of A on input x. Thus A makes at most $f(|x|)$ random coin flips during its execution. In particular, $ x\in L\Rightarrow {\mathrm {Pr}}\[A(x) = 1\]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.

I understand that:

* By definition of PP, ${x\in L\Rightarrow \mathrm {Pr} \[A(x) = 1\]\>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
* The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.

But why is it so obvious that $ x\in L\Rightarrow {\mathrm {Pr}}\[A(x) = 1\]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?

That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?

# Answer
> 3 votes
$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that you accept can't be exactly 0.501. It's either 0 (you never accept), 1/4 (one coin flip combination leads to acceptance), 1/2 (two combinations make you accept), 3/4 or 1.

So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.

---
Tags: complexity-theory, closure-properties, complexity-classes, probabilistic-algorithms
---


# Question
Title: If we spoke in TM-computable English, what would it look like?
We know that any "effectively computable" process is computable by a Turing machine (Turing-Church thesis).

Although it seems that "effectively computable" is still open to discussion, the intuitive interpretation is that any process that is "mechanical enough" can be computed by a Turing machine.

Turing's initial objective was to axiomatise how humans do reasoning. Now what do you need to reason? Non-ambiguous definitions (axioms) and non-ambiguous rules. Then you are good to go. So in effect if TM successfully modelise how humans think, that's all they should need and hence natural languages should be quite a close candidate to become regular languages as long as we impose that words have just one meaning.

**My question is then, intuitively, is it enough for a language to be "non-ambiguous" to be computed by a Turing machine? Or is there more intuitive properties that the language need to respect?**

(I am currently trying to figure out if the laws voted in a parliament, although written in mundane English, have enough of these characteristics to be computed by an automaton).

# Answer
Under reasonable assumptions, there is a TM which can decide whether something is a valid piece of English legalese. We can safely assume that the length of a law is bounded by some finite number $k$, say the number of characters the fastest human reader can read in less than two hundred years. There is then only a finite number of possible strings that might or might not be valid laws. Hence there is a lookup table of finite size that contains for every string of length at most $k$ the correct answer.

It is not settled whether humans can in fact recognize languages that TM can't recognize, so it's unclear whether the length restriction is truly necessary. See for example this question, or this question.

This is of course a boring answer, because this TM is completely impractical to construct. In actual practice you probably want to restrict yourself to a subset of English that can be parsed by an LL(k) parser (real English is not context-free), or go for a language specifically designed to be easy to understand to both humans and computers. @LukasBarth mentioned Lojban in the comments, but there are a number of such languages (programming languages are another example).
> 1 votes

# Answer
Since there is no reason to believe there is a mysterious, non-computable process which magically allows humans to recognize English, the CT thesis can actually be appealed to say that it is theoretically possible to build a machine that recognizes English at least as accurately as a chosen human.

In the most boring case, you can simply simulate the human brain to decide whether a particular string is valid English or not.

However, take into account that valid English is a much more fluent notion than that of a formal language (English can change through time, etc). Thus it does not have a nice mathematical characterization. The cleanest I can think of is defining English as whatever this particular brain in this particular state accepts as English, which is circular. However, it is a formal characterization anyway.
> 1 votes

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


title: Proof Knuth S algortihm correctness

text:
# Question
Title: Proof Knuth S algortihm correctness
In the programming pearls book by Jon Bentley, there is a section about the problem of finding a random set of m integers from range 0 to n-1 integers. To do so they use Knuth's algorithm given by the following code (see also here). How can I proof that this code indeed chooses every set of m integers from the range 0 to n-1 with equal probability.

```
def select_random(n, m):
    to_pick = n
    remaining = m
    positions = []
    for position in range(n):
        big_int = generate_random_big_int()
        if big_int % remaining < to_pick:
            position.append(position)
            to_pick -= 1
        remaining -= 1
    return positions

```

# Answer
> 3 votes
I have finally succeeded in proving Knuth's algorithm S. Let's state it first:

Knuth's algorithm S takes a sample of $M$ elements from $N$ inputs, **N is not known until the end of inputing**. A uniform sample will be available after each input and it will remain uniform when you do all inputs.

Algorithm:

1. First $M$ numbers should definitely take part in your sample, so until $N\>M$, use all numbers in your sample.
2. Decide if $x\_{th}$ number will take part in your sample, and if it does, put it in place of a random element already in sample. Probability for the first statement should be $\frac{M}{x}$
3. Repeat 2 for all n items.

---

We now have to prove that this algorithm gives each element an equal chance of being in a random sample at each subsequent step, and at the end. If we can prove that it works for $n$ (considered as individual step), it will work for $N$ (total number), since the total number is just another step.

Basically it must fix up the probabilities without knowing how many numbers will be inputted.

---

Algorithm is correct if and only if the probability of each item to get into sample is the same, more precisely - equal to $M/N$. Let us consider how likely is for the number to **get** in the sample after n steps.

$P\_G(x)$ - chance of item $x$ getting in the sample after $n$ steps;

$P\_E(x)$ - chance of item getting in when it is **first introduced**;

$P\_R(x)$ - chance of item remaining in the sample, in other words **not getting kicked out** by the remaining items;

$P\_S(i)$ - chance of item **not getting kicked out** by one of the remaining items, $i\_{th}$.

---

$P\_G(x) = P\_E(x) * P\_R(x)$ since the item has to **get in and remain inside**

$P\_R(x) = \prod\_{i=x+1}^nP\_S(i)$ - the chance of item surviving all remaining turns is equal to a product of surviving each of the individual turns.

---

Chance of item surviving a turn is equal to $1 - nS$ (not surviving).
$Ns$ is equal to another item **both**:
1. getting into sample $\frac{M}{i}$
2. kicking exactly our item out $\frac{1}{M}$

$P\_S(i) = 1 - \frac{M}{i} * \frac{1}{M} = 1 - \frac{1}{i} = \frac{i-1}{i}$

---

It turns out that:

$P\_G(x)=\frac{M}{x} * \prod\_{i=x+1}^n(\frac{i-1}{i}) = M/N$
(If you notice that product is basically $\frac{n+1}{n}$, you can write it out and terms cancel out.)

Exactly what we wanted to prove.

---
Tags: algorithms, correctness-proof, randomness, sampling
---


title: AI: Heuristic function A* search

text:
# Question
Title: AI: Heuristic function A* search
I have an assignment in my university where I have to implement Uniform Cost Search and A\* Search.

We have an input which includes a map and queries.

The map is weighted, directed graph, represented by an adjacency matrix. The queries include Uniform Cost Search and A\* Search queries (Ex: `Uniform(or A*) + initial location + goal location`)

I cannot use heuristic functions based on physical distance because we have no knowledge and extra information about this graph except distances between vertices.

Is there any way to find a heuristic function in this case ?

(Is it possible to use prior results from Uniform Cost Search in the queries to extract information from the graph?)

# Answer
> 0 votes
You can use the depth as the heuristic function I guess. The start node is at depth 0, the ones adjacent to it will be at depth 1 and so on! As the function will explore nodes, the heuristic function value will gradually increase with depth and that will make the function to choose next node with more caution, so that overall cost (distance to next node + heuristic value) is least affected.

Edit: You can use powers of 2 where the exponent term will be the depth. So the start node has heuristic value 2^0 = 1, the nodes adjacent to it have heuristic value 2^1 = 2 and so on.

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


# Question
Title: Does NP = coNP imply the collapse of PH to level 1?
It was already asked here whether NP=coNP implies P=NP. I'd like to approach that question from the perspective of the Polynomial-Time Hierarchy.

Here is a theorem from Oded Goldreich's "Computational Complexity" (Proposition 3.10):

> For every $k \ge 1$, if $\Sigma\_k = \Pi\_k$ then $\Sigma\_k = \Sigma\_{k+1}$, which in turn implies $PH = \Sigma\_k$.

Now, since $\Sigma\_1=NP$ and $\Pi\_1 = coNP$, doesn't it imply that $PH = \Sigma\_1$, which ultimately implies $P = NP$?

# Answer
> 6 votes
No. $PH=NP$ doesn't imply $P=NP$, because $PH$ is not the same class as $P$.

Roughly speaking, $PH$ includes $P$, $NP$, $coNP$, and more: $PH$ includes $\Sigma\_i$ and $\Pi\_i$ for all $i$. Formally, $PH$ is defined as

$$PH = \Sigma\_0 \cup \Pi\_0 \cup \Sigma\_1 \cup \Pi\_1 \cup \Sigma\_2 \cup \Pi\_2 \cup \cdots.$$

If $NP=coNP$, then we have $\Sigma\_1=\Pi\_1$, and by Proposition 3.10, we have $\Sigma\_1=\Sigma\_2=\Sigma\_3 =\cdots=NP$ and $\Pi\_1=\Pi\_2=\Pi\_3=\cdots=coNP=NP$, so

$$\begin{align\*} PH &= \Sigma\_0 \cup \Pi\_0 \cup \Sigma\_1 \cup \Pi\_1 \cup \Sigma\_2 \cup \Pi\_2 \cup \cdots\\ &= P \cup P \cup NP \cup NP \cup NP \cup NP \cup \cdots\\ &= NP. \end{align\*}$$

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Should you use Genetic algorithm for an extremly large unstructured search space?
My search space is discrete and in the order of $10^{1360}$, with a probably very complex fitness surface. Is it hopeless to attempt to use GA for such a problem? One fitness evaluation could take 1-3 minutes per candidate solution.

# Answer
No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.

There is no good theory to know whether GA will work or not. Ultimately, all you can do is try it and see.

As a side note: Generally speaking, for most problems, other approaches tend to do better than GA. This is not a theorem; it's just experience / a rule of thumb that seems to often hold.
> 9 votes

---
Tags: algorithms, search-problem, genetic-algorithms
---


# Question
Title: Where in the toolchain does formal specification come in?
Where is the formal spec located? Like this?

Are tests made from formal or informal spec? I saw a project where they where generated from a the formal spec and that never made sense to me.

Is the verification step manual or can it be automated?

If it is manual, we now have 3 things to maintain and keep in sync. The problem of a possible mismatch between informal spec and code has just been moved between the informal and the formal spec. What did we gain?

If the verification step can be automated completely then why write any code at all? Just let it be generated from the spec automatically. If we fold those two steps into one the situation is the same as before; we have a high level description of our problem which a compiler turns into a low level representation that can be executed by a machine. What did we gain?

# Answer
> 4 votes
Tests can be written based on either a formal spec or an informal spec.

Verification always requires a formal specification. Formal verification might be manual or automated, or some combination of the two; it depends what techniques you use. Typically, it's hard to do completely automatic verification -- it's more usual that verification systems automate part of the verification task, but require some assistance from the programmer (e.g., to specify invariants or prove lemmas that are hard for the automated system to prove). See https://en.wikipedia.org/wiki/Formal\_verification for an overview; there are also textbooks that give an overview of formal verification. I suggest reading some standard references on formal verification: they will probably answer a lot of questions you might have.

There's nothing that says you have to have an informal spec, a formal spec, and a program. You could have just a formal spec and a program.

It is often helpful to have specifications at multiple levels of abstraction/granularity, with theorems relating them. Higher-level specs may be easier to understand and specify properties about the whole system or properties we ultimately care about, but may be difficult to prove directly; lower-level specs may be more detailed and harder to work with or understand, but may have a more direct mapping to the program and might facilitate proof/verification.

Higher-level specs might be formal, or in some cases they might be less formal.

---
Tags: formal-methods, software-engineering, software-verification
---


# Question
Title: Finding minimal and complete test sets for circuits
I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples.

I believe the length of these Majella tuples to be ((2^n) * n) + 1 where n is the width of the input in bits.

for example (with all 0 starting patterns):

n = 1:

0 1 0

n = 2:

00 10 11 01 11 10 00 01 00

n = 3:

000 100 110 010 110 111 011 001 101 001 011 111 101 111 110 100 101 100 000 010 011 010 000 001 000

I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (actual code in a prev. revision of this question).

```
FUNCTION gen
  IF height of stack == ((2^bit_width) * bit_width)
    PRINT ZERO_PATTERN
    RETURN TRUE
  IF the change between the value at the top of stack and value does occur between other values on the stack
    RETURN FALSE

  PUSH value to stack
  WHILE shift < bit_width
    IF RECURSE with value as (value XOR (1 << shift)) returns TRUE
      PRINT value
      RETURN TRUE
    shift = shift + 1
  RETURN FALSE

SET stack to an empty list
SET bit_width to n

CALL gen with value as 0

```

some properties:

I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it.

In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same.

Unfortunately this is where my knowledge runs out.

Is there a more efficient way of producing a valid solution given n as an input?

Can it be (easily) proven that there are solutions for all values of n?

edit:

I think it can be viewed as a graph:

```
   n = 2                   n = 3

                             000
    00                      / | \
   /  \                    /  |  \
  01  10                100  010  001
   \  /                  | \/   \/ |
    11                   | /\   /\ |
                        110  101  011
                           \  |  /
                            \ | /
                             111

```

The sequence is required to traverse each edge in both directions, but in neither direction more than once.

# Answer
> 3 votes
Yes. One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively. It's easy to see you can't do any better than this, so this is optimal.

**Definition.** I'll say that a sequence $x\_0,x\_1,\dots,x\_m$ of $n$-bit values is a $n$-bit Majella sequence if $x\_0=x\_m$, and for each $y \in \\{0,1\\}^n$ and each value $e \in \\{0,1\\}^n$ with a single bit set, the pair $y,y\oplus e$ appears (consecutively) somewhere in the sequence.

**Recursive construction.** Let $w\_0,w\_1,\dots,w\_m$ be a $n-1$-bit Majella sequence (for $n-1$-bit values). Consider the following sequence:

$$0w\_0, 0w\_1,\dots, 0w\_{m-1}, 0w\_m, 1w\_m, 1w\_{m-1}, \dots, 1w\_1, 1w\_0, 0w\_0,$$

where $0w$ represents the concatenation of $0$ and $w$. This sequence is not yet a Majella sequence, but we can modify it to be one. In particular, for each value $w \in \\{0,1\\}^{n-1} \setminus \\{w\_0\\}$, replace the first occurrence of $0w$ in the sequence with $0w,1w,0w$ (increasing the length of the sequence by 2).

After this modification, the result is a $n$-bit Majella sequence.

This construction is inspired by the standard recursive construction of a Gray code, but tweaked slightly to satisfy your particular requirements.

**Length of the recursive construction.** Let $L(n)$ be the length of the resulting sequence (i.e., the value of $m+1$). It satisfies the recurrence relation

$$L(n) = 2L(n-1) + 2^n - 1$$

with $L(1) = 3$. This solves to

$$L(n) = n \cdot 2^n + 1.$$

**Algorithms.** I don't know if there are any efficient, low-space algorithms for enumerating through such a sequence, like there are for Gray codes.

---
Tags: optimization, circuits, software-testing
---


# Question
Title: What are the pros and cons of RANSAC versus Hough Transform?
A friend needs to find the pool balls in an image of a pool table. Would a Hough transform be a good idea? Why/why not? Would RANSAC be better?

The question comes from this study guide (http://www.cc.gatech.edu/~afb/classes/CS4495-Spring2015-OMS/), is not homework, and I am not currently taking this class.

What I know: RANSAC is least-squares plus a system with voting. We pick the least squares solution that has the least outliers. Hough transform is about finding parametric shapes. You can transform something into Hough space. For a circle you might want to know the radius. If you know more information about your circle (the pool ball) you'll not have as much space to search.

I think it makes sense to use Hough transforms in the case of finding pool balls so I am wondering how and why you'd even use RANSAC.

Edit: I think you could use RANSAC if you had another image to match to that you knew had pool balls in it. The images would be matched against each other, and the features that came out would be the pool balls. But again, it seems like RANSAC isn't a good idea because it could only fit one model to the whole image.

# Answer
The Hough transform would be a reasonable approach for this. Another reasonable approach would be to find connected regions of similar hue, and for each, test if it is approximately pool-ball-shaped.

RANSAC doesn't seem like a good tool for this purpose. RANSAC is commonly used to find, e.g., a line that approximately goes through a bunch of points (but possibly with a few outliers that might not fit the line). Here, the pool balls are spheres, not lines.

RANSAC is typically used for other tasks: e.g., for aligning two images. However, here image alignment probably isn't a good way to find pool balls on a pool table.
> 1 votes

---
Tags: machine-learning, image-processing, pattern-recognition
---


# Question
Title: Are turing machines and formal languages the same mathematical object?
Turing's objective while building his concept was to formalise how humans do abstract reasoning.

Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.

So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?

# Answer
> 3 votes
Not quite. A Turing machine is described by this mathematical object:

$$(Q,\Sigma,\delta,\mathcal H, q\_0, b)$$

Where

* $Q$ is a finite set of states
* $\Sigma$ is an *alphabet*, a finite set of symbols
* $\delta : Q \times \Sigma \rightarrow Q \times \Sigma \times\\{\Leftarrow, \Rightarrow\\}$ is a transition function
* $\mathcal H \subseteq Q$ is the set of *halting* states
* $q\_0 \in Q$ is the initial state
* $b \in \Sigma$ is the "blank" symbol

The machine takes some input string, $x \in \Sigma\*$, and uses the transition function to iteratively update individual symbols in that string until $\delta$ returns a state belonging to $\mathcal H$. At that point we say the machine has *halted* \- which it may or may not ever do.

Compared to all that, formal languages are much more simple objects. A language is just a subset of the set of all strings over some alphabet. In other words, $\mathcal L \subseteq \Sigma^\*$, where $\*$ is the Kleene star operator.

The connection is that Turing machines can be used to *define* formal languages. For example:

$$ \mathcal L = \\{x \in \Sigma^\* | \mathcal M \text{ halts when given } \langle x \rangle \text{ as input }\\} $$

Defines the formal language $\mathcal L$ in terms of the Turing machine $\mathcal M$. For a language, $\mathcal L$, if there exists a Turing machine that halts if and only if its input belongs to $\mathcal L$, then the language is called *Turing-recognizable*. Some languages cannot be defined by any Turing machine, which means they are *not-computable* \- no finite process can decide whether an arbitrary string belongs to the language or not.

Formal languages are not the same as Turing machines, but the Turing recognizability does have an interesting place in the study of formal languages. In the Chomsky hierarchy, a Type-0 language is a language that can be enumerated by any formal grammar, and this turns out to be equivalent to being recognizable by a Turing machine! Formal grammars and Turing machines are just two of many models of computation that are all equally powerful!

It's generally believed that every model of computation makes the same distinction between computable and non-computable languages - this notion is called the Church-Turing thesis.

EDIT: My terminology was off when I initially wrote this. A Turing decidable language can be decided by a machine that always halts, and gives a definitive yes or no as to whether its input belongs to the language. When we only require that the machine accepts member's, but can't necessarily reject non-members, the associated language is called Turing *recognizable*, or, more commonly, recursively enumerable. Turing recognizable languages are equivalent to the languages that can be generated by unrestricted grammars.

Some languages are not even recursively enumerable - for example, the set of all Turing machines that don't halt is totally unrecognizable. There's a language corresponding to this set that couldn't be generated by any grammar at all, but that still might be called a "formal language." By this definition, there's no complete mapping from Turing machines to formal languages, and *definitely* no isomorphism between the two.

# Answer
> 11 votes
No, they are not the same thing. A language is a set of words over some finite alphabet. A Turing machine is a 7-tuple as defined in the Wikipedia.

For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.

This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.

---
Tags: formal-languages, turing-machines
---


# Question
Title: Machine Learning to predict the Halting Problem
I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt.

By predict, I mean the standard notion in ML: minimize the error on some validation set. For simplicity, let's assume that the ML is a binary classifier, (although AFAIK the actual paper may have framed it as a regression problem).

The notion is then not 'solving' the Halting Problem (which we know is impossible), but rather using ML to agree with an Oracle that knows the answer on the training (and validation) set.

However, I haven't been able to find anything so far.

Does anyone know of a reference?

# Answer
After some digging around, I finally came across the original paper.

Regarding applications of a (necessarily fallible) predictor of halting - one possibility is to use it as a heuristic in some wider heuristic process, for example in the generation of Turing-complete programs for Genetic Programming.
> 8 votes

---
Tags: machine-learning, halting-problem
---


# Question
Title: What is this fraction-like "discrete mathematics"–style notation used for formal rules?
In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules":

What is this notation called? How do I read it?

For example:

* the `DOC` rule doesn't have anything in its "numerator" — why not?
* the `EXEC` and `GET` rules appear to have two separate terms above the line, what does that mean?
* the `VAR` rule stands out a bit as well, since while many other rules use some sort of arrow (which I would take to mean "implies") up top this one only seems to be saying that x is an element of something.
* almost everything is peppered with an initial `Ap,` which the text describes as "the state of replica p is described by Ap, a finite partial function" — how would a savvy reader of this notation tend to "see" that part of every rule?

This site did suggest a related question that has some very similar-looking notation, over on the question What is the significance of ⟨B, s⟩ -\> ⟨B', s'⟩ as the initial rule in this question about small-step semantics? — this is tagged as Operational semantics, and that does seem to be a strong lead. Is that indeed the framework under which I should be interpreting these figures? Could you easily summarize this in "crash course" form so that, even if I can't verify the correctness of their proofs, I could at least get a bit more understanding of what they are saying in this section?

# Answer
> 25 votes
This is a standard notation for an inference rule. The premises are put above a horizontal line, and the conclusion is put below the line. Thus, it ends up looking like a "fraction", but with one or more logical propositions above the line and a single proposition below the line. If you see a label (e.g., "LET" or "VAR" in your example) next to it, that's just a human-readable name to identify the particular rule.

You might also see this referred to as natural deduction or Gentzen-style natural deduction.

This is a common notation in the programming languages literature. You'll see it all over the place. It's very convenient for the kinds of conclusions and recursive-structured proofs that arise in that field.

You'll see this notation used to express axioms/rules. You can think of each axiom as a template with "meta-variables" (e.g., *expr*); you can replace each meta-variable with some syntax from the programming language (e.g., any expression that is valid in the programming language), and you'll get an instance of the rule. The inference rule promises that if all of the propositions are above the line are true (for some instance of the template, where you consistently replace each metavariable with the same value throughout the rule), then the proposition below the line will be true, too.

# Answer
> 7 votes
Here is a **very** informal explanation that might help people unfamiliar with formal notations to get a foot in the door. It does not replace a formal definition!

The *Ap* is the state of your system or your running program. "State" can mean a lot of things but in this case it seems to include a list of all defined local variables and their values. Why is *Ap* a function? Because that's a convenient way to express variable assignments: *Ap(x)* gives the value of variable *x*.

Now, let's take the rule EXEC as an example. It defines the semantics of executing a command *cmd1* followed by a command *cmd2*, i.e., what happens with the state *Ap* of the system when executing *cmd1* followed by *cmd2*.

* Above the line: These are the premises. What they say: "Let *cmd1* be a command. If you execute the command *cmd1* when your system is in state *Ap*, your system will end up in a new state *Ap'*."
* Below the line: Here the rule describes what it means to execute two commands *cmd1* and *cmd2* sequentially. What it says: "Assuming your system is in state *Ap*, executing *cmd1* and then *cmd2* means to execute *cmd2* when your system is in state *Ap'*" (remember that *Ap'* is the state that you get after executing *cmd1*, as defined in the premises).

The other rules describe the semantics of the individual commands and expressions. For example, the VAR rule describes what it means to "execute" a variable: If *x* is a local variable (above the line), then what does it mean to evaluate/execute the variable *x*? It's written below the line: When your program is in state *Ap*, evaluating *x* gives you the value of *x*, i.e. *Ap(x)*.

I hope that helps.

---
Tags: semantics, notation, formal-methods, operational-semantics
---


# Question
Title: Algorithm and proof for combining a list of node connections into groups of nodes efficiently
My goal is to algorithmically take a list of relations between nodes (in other words, a list of undirected edges between nodes of a graph) and label each group of nodes such that all nodes that have a path between them have the same label (I believe the term for this is a "*connected component*") and nodes that do not have a path between them have different labels. Put another way, each connected component has a unique label.

---

NOTE: I haven't done all that much in the way of discrete math proofs since college, so hopefully you can bear with me and correct my terminology/methods if necessary.

To clarify, the data is in the form of a list of pairs of connected nodes.

For example:

```
n_1, n_3
n_3, n_5
n_5, n_7
n_5, n_9
n_2, n_4
n_4, n_6

```

In this \<contrived\> example, the odd-numbered nodes all belong to the same group, and the even-numbered nodes belong to another group.

I believe the way to do this is to process each item in the list according to the following rules:

* Maintain an ordered list (call it "encounteredNodes") of all encountered nodes and the group label they have been assigned to
* Maintain an integer variable (call it "nextLabel") that is incremented and returned each time a new unique label is needed
* For each item in the list, determine if either node has been encountered yet.
    + If neither node has been encountered, get a new unique label from nextLabel and add both the nodes to encounteredNodes with this new uniqueLabel
    + If one node has been encountered but not the other, assign the label of the previously-encountered node to that of the unencountered node.
    + If both nodes have been previously encountered, take the lesser label of the two and use it to replace the label of all nodes in encounteredLabels that have the greater label of the two.

After one pass of this "for loop" through all the nodes, the algorithm is complete and the nodes have been grouped according to the goal. I believe the proof can be shown in this way:

**Lemma 1:** None of the operations can result in 2 previously encountered nodes that already have the same label being assigned to different labels. Because of this, already encountered nodes never "split off" from their group of nodes with the same labels, and once two nodes have the same label, they will never have differing labels (though they may change together to the same new label) for the remainder of the algorithm.

Assume there are two nodes that have a path between them via the list of edges, yet after the algorithm finishes, they have different labels (call them $L\_1$ and $L\_2$. If that's the case, then either...

1. They each contain a node (and these two nodes are directly connected), or...
2. there is a "chain" formed of groups of nodes where each group has the same label and the chain can be traversed to get from $L\_1$ to $L\_2$.

However neither of these scenarios can occur based on the algorithm. In the case of 1, there would have to have been a pair of connected nodes in the list where one node belongs to $L\_1$ and one node belongs to $L\_2$. However, after the algorithm processed this connection, both nodes would have the same label, and because of Lemma 1, they would have the same label until the end of the algorithm. In the case of 2, the neighbouring links in the chain could not exist because of the first case. Thus. This is a proof by contradiction.

Is this all sound? Also, I was never that great at algorithm runtime calculations, but I think it would be $O(n \log{n})$ because iterating the list of connections is linear time, but each iteration requires a search of ordered lists. Is this correct?

# Answer
You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges.

The performance of the algorithm you described is much worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:

$v\_{2k},v\_{2k+1}$

$\vdots$

$v\_2, v\_3$

$v\_0, v\_1$

$v\_{2k}, v\_{2k-1}$

$\vdots$

$v\_3, v\_4$

$v\_2, v\_1$

The introduction of the edge $v\_{2k}, v\_{2k-1}$ requires relabeling $v\_{2k}$ and $v\_{2k+1}$, introducing $v\_{2k-2}, v\_{2k-3}$ requires relabeling $v\_{2k-2}, v\_{2k-1}, v\_{2k}$ and $v\_{2k+1}$. Finally, introducing $v\_2,v\_1$ requires relabeling $v\_2,\ldots,v\_{2k+1}$. This ends up being quadratic in $n+m$.

The idea behind your algorithm is somewhat valid though, and you can implement it much more efficiently using the Union-Find data structure which, if you will, can "defer" the relabeling.
> 2 votes

# Answer
Your bound is right, but there is faster.

This question looks to be implementing the Disjoint-set algorithm. The fastest algorithm for doing this is actually virtually linear. It uses a different data structure that flattens the groups out more efficiently so that you don't have to update as much when merging groups.

I wont repeat the algorithm here, but I will point out that it's actual time bound is $O(\alpha(n))$ where $\alpha(x) = A(x, x)$ and $A$ is the inverse Ackermann function. I mention it because the Ackermann function is a particularly fun sequence to look at. It grows *really really really really* fast.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, runtime-analysis, algorithm-design
---


# Question
Title: Is there a name for the problem of turning a bipartite graph into two graphs?
Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.

# Answer
You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.
> 5 votes

# Answer
It would just be an example of a graph partitioning problem. Here is a link to a paper on partitioning bipartite graphs: https://arxiv.org/pdf/cs/0108018.pdf
> 0 votes

---
Tags: algorithms, graphs, terminology, social-networks, network-analysis
---