# Question
Title: Finding a kernel for d-Bounded degree deletion
In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum vertex degree of the graph to at most $d$.

The question is to how to find a polynomial kernel (in $k$ and $d$) for this problem.

I seem to be able to get the only reduction rule that if any vertex has degree $ \> k+d$, it has to be there in the deletion set (if the answer to instance is yes). Because if it isn't, then at least $k+1$ of its neighbors have to be in deletion set. I can't seem to move beyond this point.

The exercise is from this book (exercise $2.9$).

I am also aware that we can remove edges between vertices with degree $\< d$, and find solution in the modified graph (hint from the book). But I am not sure how it will be useful, in getting a bound over number of vertices/edges in $k$ and $d$.

I would appreciate only hints if possible (something maybe beyond the book hints).

PS: for $d=0$ this reduces to vertex cover problem.

# Answer
**Reduction Rule 1.** Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($\le d$ as $d \ge 0$). And if $I$ is a yes instance so is $I^{'}$, as $G-V$ is a sub-graph of $G$, and $k$ and $d$ remain same across the two instances.

**Reduction Rule 2.** If a vertex $v$ has degree $\ge k+d+1$ then it has to be kept in the deletion set. Otherwise $k+1$ of its neighbours have to be kept in the deletion set. Which cannot be done, as maximum size of deletion set is $k$. Thus after this reduction all vertices will have degree $\le k+d$.

**Reduction Rule 3** If there are two vertices $v$ and $w$, such that degree of both of them is $\le d$. Then the edge $vw$ can be removed converting the instance from $I = (G, k,d)$ to $I^{'} = (G-\\{vw\\}, k,d)$. If $I$ is a yes instance so is $I^{'}$ as $G-\\{vw\\}$ is a sub-graph of $G$, with $k$ and $d$ remaining same across the instances. And if $I^{'}$ is a yes instance so is $I$, as adding back $vw$ can make the degree of $v$ and $w$ at most $d$ (as they initially had degree $\le d$).

Rule $1$ might be applied after applying Rule $3$ as well.

Now considering a graph where vertices with degree $\le d$ don't share an edge, no vertex is isolated and and all vertices have degree $\le k+d$ (ie. none of the above rules applied). Let $A$ be the set of vertices with degree $\le d$ and let $B$ be the set of vertices with degree $\> d$. We can argue that $|B| \le k(k+d) +k$, otherwise the output is no. Because if $|B| \> k(k+d) +k$, then as most $k$ elements will be chose from $B$ for the deletion set, and $ \> k(k+d)$ elements will be left (in $B$). And as each of them has degree $\> d$, they each have at least one edge going into the deletion set. But the deletion set can only accommodate $k(k+d)$ edges. Also as each vertex in $A$ has at least one neighbor (and all of them in $B$), the maximum number of vertices in $A$, will be bounded as $|A| \le |B|(k+d) \le (k(k+d)+k)(k+d) = k(k+d)(k+d+1)$. So $|A| + |B| \le k(k+d) + k(k+d)(k+d+1) = k(k+d)(k+d+2)$.
> 4 votes

---
Tags: complexity-theory, parameterized-complexity, vertex-cover
---


# Question
Title: How does the undecidability of Extensional Martin-Löf Type Theory apply to real type-checking compilers?
It is claimed in many sources (for example, here) that adding a rule like "if `Id(X,Y)` then `X` *really equals* `Y`" to a type theory is "problematic" because then its type-checking becomes undecidable. I have read Martin Hoffman's proof ("Extensional concepts in intensional type theory", Section 3.2.2), as well as this SE question, but I still don't see how this creates a problem for a "down-to-earth" programming language.

I understand that *deciding* whether `x:A` has type `B` can get difficult, because there might exist a proof of `Id(A,B)`. But the purpose of any "normal" type-checker is to *verify*, not to *decide*, so how is it problematic?

As I see it, nothing prevents the compiler from functioning like this: whenever the user tries to use a value of type `X` where a `Y` belongs, if the user has previously provided a proof that `Id(X,Y)`, then we allow it, as if X and Y were syntactically identical. But if such a proof hasn't been provided, we treat it as an error, because the user "hasn't made his case".

My question is: what difficulties, if any, can arise from treating identity types like that?

# Answer
> 1 votes
You can't expect to find a ready-to-use proof of Id(a,b) when you need one. For instance, you have proofs of Id(a,c) and Id(c,b), but not of Id(a,b). You would need some intelligence to find automatically new proofs of equality, and avoid always having to ask the user to do the job manually. But there is no perfect algorithm to implement such an intelligence: whatever you implement, it will always have limitations.

There are however solutions to this difficulty, see for instance the Andromeda project.

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


# Question
Title: What's wrong with the following shuffle algorithm?
Suppose I have an array `A` of size `n`, with the initial state of:

```
A[0] == 1, A[1] = 2, ... A[n-1] = n

```

I know that one way to get a uniformly-distributed permutation of that array is to use Fisher-Yates Algorithm, but I am more interested in what's flawed with the following naive approach:

```
for i = 0 to n-1:
   rand_i = random(0, n-1, UNIFORM_DIST)
   swap(A[i], A[rand_i])

```

When I tried to use that with `n = 3`, it seems like some permutations are more likely to be drawn than others.
Here's the output of running the above algorithm 10,000,000 times, and then averaging on the results (shown in percentage of likelihood):

```
#> swap.out --iteartions 10000000
00: (1,2,3): 14.8237
01: (1,3,2): 18.5105
02: (2,1,3): 18.504
03: (2,3,1): 18.5216
04: (3,1,2): 14.7975
05: (3,2,1): 14.8427

```

To rule out the possibility that the Pseudo-Random-Generator is not uniform, I compared that with an algorithm that builds db of all permutations and then, using the same PRG - chooses one permutation:

```
#> choose_permutation.out --iterations 10000000
00: (1,2,3): 16.6847
01: (1,3,2): 16.6649
02: (2,1,3): 16.6731
03: (2,3,1): 16.6706
04: (3,1,2): 16.6516
05: (3,2,1): 16.655

```

This pattern is consistent; permutations 1,2,3 always come up with a higher likelihood than 0,4,5.
With `n = 4`:

```
#> swap.out --iteartions 10000000
00: (1,2,3,4): 3.90774
01: (1,2,4,3): 3.90958
02: (1,3,2,4): 3.91321
03: (1,3,4,2): 5.46167
04: (1,4,2,3): 4.29965
05: (1,4,3,2): 3.51932
06: (2,1,3,4): 3.89793
07: (2,1,4,3): 5.83975
08: (2,3,1,4): 5.45905
09: (2,3,4,1): 5.47537
10: (2,4,1,3): 4.30715
11: (2,4,3,1): 4.3
12: (3,1,2,4): 4.29691
13: (3,1,4,2): 4.3075
14: (3,2,1,4): 3.51411
15: (3,2,4,1): 4.29534
16: (3,4,1,2): 4.30452
17: (3,4,2,1): 3.90896
18: (4,1,2,3): 3.12621
19: (4,1,3,2): 3.50413
20: (4,2,1,3): 3.52526
21: (4,2,3,1): 3.12843
22: (4,3,1,2): 3.89564
23: (4,3,2,1): 3.90257

```

And comparing to randomly choosing from db of permutations:

```
#> choose_permutation.out --iterations 10000000
00: (1,2,3,4): 4.16284
01: (1,2,4,3): 4.16721
02: (1,3,2,4): 4.15893
03: (1,3,4,2): 4.17306
04: (1,4,2,3): 4.15853
05: (1,4,3,2): 4.16169
06: (2,1,3,4): 4.16584
07: (2,1,4,3): 4.17245
08: (2,3,1,4): 4.17309
09: (2,3,4,1): 4.15519
10: (2,4,1,3): 4.17007
11: (2,4,3,1): 4.17163
12: (3,1,2,4): 4.16276
13: (3,1,4,2): 4.17367
14: (3,2,1,4): 4.17147
15: (3,2,4,1): 4.16955
16: (3,4,1,2): 4.16576
17: (3,4,2,1): 4.1659
18: (4,1,2,3): 4.16653
19: (4,1,3,2): 4.16749
20: (4,2,1,3): 4.17225
21: (4,2,3,1): 4.1668
22: (4,3,1,2): 4.16797
23: (4,3,2,1): 4.15932

```

What's flawed with that method and why are those specific permutations come up more often?

# Answer
This approach cannot work, for the following simple reason. The probability to obtain any permutation is of the form $A/n^n$, for *integer* $A$. However, we need it to be $1/n!$, so we need $A = n^n/n!$. Unfortunately, for $n \geq 3$ this is not an integer.

---

One can still ask why we might expect this algorithm to work, and where is the gap between our intuition and reality.

After the $i$'th step of the algorithm, $A\[i\]$ is a uniformly random element. So if we randomize $A\[0\]$, then $A\[1\]$, then $A\[2\]$, and so on until $A\[n-1\]$, won't we get a random permutation?

While it is true that $A\[n-1\]$ will be completely random, this is not the case for other entries. Indeed, let us try to analyze the distribution of $A\[0\]$ as the algorithm progresses.

After the first iteration, $A\[0\]$ is uniformly random.

After the second iteration, $A\[1\]$ is uniformly random, but this comes at a cost: we might have swapped $A\[0\]$ and $A\[1\]$. This means that $A\[0\]$ will have a slight preference towards $1$ (the original value of $A\[1\]$) and $0$ (the value of $A\[1\]$ in case it was swapped with $A\[0\]$).

Quantitatively, after the second iteration, if $i \> 1$ then $$ \Pr\[A\[0\] = i\] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) = \frac{1}{n} - \frac{1}{n^2}, $$ since this happens when $A\[0\]$ was swapped with $A\[i\]$, and $A\[1\]$ was *not* swapped with $A\[0\]$. Similarly, $$ \Pr\[A\[0\] = 0\] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n}, $$ accounting for the additionally possibility in which $A\[1\]$ is swapped with $A\[0\]$ in the second round. Finally, $$ \Pr\[A\[0\] = 1\] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \left(1 - \frac{1}{n}\right) \cdot \frac{1}{n} = \frac{2}{n} - \frac{2}{n^2}, $$ accounting for the possibility that $A\[0\]$ was not swapped with $A\[1\]$, but $A\[1\]$ was swapped with $A\[0\]$.

Similar phenomena persist throughout the algorithm.
> 4 votes

---
Tags: permutations
---


# Question
Title: Examples of random deployment in wireless sensors networks
I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used before? What could be a very concrete context in which it could be used? Thanks in advance.

# Answer
> 1 votes
One scenario that I've heard discussed is the idea that an airplane flies over a remote area and drops wireless sensors. They fall somewhat randomly, and then need to establish a network amongst themselves.

---
Tags: applied-theory, applications
---


# Question
Title: 0-1 Knapsack problem with item discounts
I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included below.

## Simple Statement of the Problem

Suppose you have values and weights for items, such that groups of $2$ and $3$ of items in your set may produce values that are less than they would be if chosen individually (think 50% off coupons, or something similar). In this sense, we wish to find the best combination of items that allows us to carry the most weight in our knapsack, given a value constraint. How can we modify the dynamic programming method to come up with a new solution? Is a metaheuristic approach the best way? is this problem already well studied?

## A mathematical statement is given below, to the best of my ability.

Let $V\_1 = \\{v\_1, v\_2, ..., v\_N\\}$ be the values of the single items, $V\_2 = \\{ r\_{(1,2)}, v\_{(1,3)}, ... \\}$ as set of size $M$ of the values of the groups of two items , and $V\_3 = \\{s\_{(1,2,3)}, s\_{(1,2,4)} ... \\}$ be as set of size $L$ of the values of the groups of three items, along with corresponding weights (with similar notation for elements) $W\_1, W\_2, W\_3$.

We seek to find $\textbf{x} = (x\_i, x\_{i,j}, x\_{i,j,k})$ where $x\_i, x\_{i,j}, x\_{i,j,k} = \\{0,1\\}$ that is a vector of length $N + M + L$ so that

$$max\left(\sum\_{w \in W\_1} wx\_i + \sum\_{w \in W\_2} wx\_{i,j} + \sum\_{w \in W\_3}wx\_{i,j,k} \right)$$ subject to $$\sum\_{v \in V\_1} vx\_i + \sum\_{v \in V\_2} vx\_{i,j} + \sum\_{v \in V\_3}vx\_{i,j,k} \leq C$$

Where $C$ is the value constraint. Here, the index $(i,j)$ and $(i,j,k)$ simply correspond to the indices of their corresponding items. This also implies that an item chosen in a group of $2$ or $3$ can no longer be chosen elsewhere, so we impose the following conditions:

If $x\_{i,j,k} = 1$ then $x\_i = 0$, $x\_j = 0$, $x\_k = 0$, $x\_{i,j} = 0$, $x\_{i,k} = 0$, and $x\_{j,k} = 0$.

If $x\_{i,j} = 1$ then $x\_i = 0$, $x\_k = 0$, and any triplet containing item with index $i$ and $j$ is zero.

If $x\_i = 1$, then any group containing item with index $i$ is zero.

## Some discussion

An item in the above problem can only be discounted in a group of two, however there may be groups of 3 that produce overlap between two groups of two, hence the need to include them. This means an obvious greedy algorithm appears by ordering the greatest weights per value of triplets, choosing form there and moving on to doubles, then singles until not possible.

I want to believe a modification to the dynamic programming algorithm is possible by simply adding more rows that represent the groups of items, but I'm not sure how we would handle the "this group has been chosen, so all subsets in the group must not be chosen." condition. In my real world problem there were 150 items, which makes it seem like the dynamic programming method was not possible (there were many possible groups of 2 and 3 if you consider how big 150 choose 3 is..). In fact, the number of rows for my case would be, at first glance, $150$ $+$ ${150}\choose{2} $ \+ ${150}\choose{3}$ $= 562,625$ rows! Combining this with the columns representing the values which could be many, a sparse matrix option might need to be used to optimize finding a solution.

## A Quick Example

Let $4$ items have values $v\_1 = 4$, $v\_2 = 7$, $v\_3 = 3$, and $v\_4 = 9$ Such that the values of the following groups have discounts: $(v\_1, v\_2) = 8$, $(v\_2, v\_4) = 14$, and $(v\_1, v\_2, v\_4) = 15$. It is worth noting any item combinations not listed with a discount are simply the sum of their values, and do not need to be written out. Suppose further that $C = 17$.

Their weights are $w\_1 = 2$, $w\_2 = 5$, $w\_3 = 5$, and $w\_4 = 3$. Then we wish to find $\bf{x}$ so that

$$max(2x\_1 + 5x\_2 + 5x\_3 + 3x\_4 + 7x\_{(1,2)} + 8x\_{(2,4)} + 10x\_{(1,2,4)})$$ subject to $$4x\_1 + 7x\_2 + 3x\_3 + 9x\_4 + 8x\_{(1,2)} + 14x\_{(2,4)} + 15x\_{(1,2,4)} \leq 17$$

Where, if any item chosen is contained in another item's group, that $x$ value must be zero, to avoid overlap. It appears to me that the items with indices $\\{(1,2), 3 \\}$ is the solution with weight 12 with value 11.

# Answer
> 1 votes
The problem is NP-hard, by a reduction from 3-dimensional matching. For each triplet $(x,y,z)$ in the 3-dimensional matching problem, we have items $x\_1$, $y\_2$, $z\_3$ and set the group of 3 items $(x\_1,y\_2,z\_3)$ to have value $1$ and weight 0. Each individual item has value $0$ and weight $+\infty$. Now the solution to your knapsack problem yields a solution to the original 3-dimensional matching problem. 3-dimensional matching is strongly NP-hard, so there is no pseudo-polynomial-time algorithm for it (unless P = NP).

If you don't allow triplets and only allow pairs, I don't know whether the problem can be solved in pseudo-polynomial time. It looks like a hybrid between a knapsack problem and maximum matching. Form a graph with one vertex per item. Each pair corresponds to an edge in this graph. Add a special vertex $s$; each individual item corresponds to an edge between that item and $s$. Now you can annotate each edge with a value and weight, and the goal is to find a matching whose total weight does not exceed the capacity, and whose total value is maximized. I don't know if there is a pseudo-polynomial-time algorithm for this problem. It certainly can't be solved in polynomial time (unless P = NP), as it is at least as hard as the usual knapsack problem, which is NP-hard.

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


title: Simplify $O(\min(m, n))$?

text:
# Question
Title: Simplify $O(\min(m, n))$?
I know that $O(\max(m, n)) = O(m + n)$, but is there a similar simplification for $O(\min(m, n))$? It could be $O(n) \cap O(m)$ but it does not simplify the notation that much…

# Answer
Based on definition for non negative functions $$O(f)=\\{g: \exists C\>0, \exists N \in \mathbb{N}, \forall n\>N, g(n) \leqslant Cf(n)\\}$$ I prefer to consider your question as about $O(\min(f,g))$.

Now, if from one hand $O(f) \cap O(g) \subset O(\min(f,g))$: $\phi \leqslant C\_1 \cdot f$ and $\phi \leqslant C\_2 \cdot g$ we obtain $\phi \leqslant C \cdot \min(f,g)$. Reverse can be show in same way, so we can be sure that $$O(f) \cap O(g) = O(\min(f,g))$$
> 3 votes

---
Tags: big-o-notation
---


# Question
Title: Convert finite automata to regular expression
I am trying find the regular expression that describes the finite automata in the image below.

Given the following finite automata

which of the following regular expressions describes the same language as the automaton.

* (ab)+c\*d+
* a+b+c\*d+
* a(ba)\*bc\*dd\*
* \[ab\]+c\*d+
* a(ba)\*bc+d?d+
* (ab)+c+d\*

I tried converting it to a regular expression and I got (ab)\*ac\*dd\*, which is not among any of the options. Could someone help me select the correct answers?

# Answer
> 0 votes
You have an error in your regular expression. The correct one is $(ab)^\*ab c^\*dd^\*$ (notice that after reading $(ab)^\*$ you are in state $A$ and that the edge from $B$ to $C$ is labelled $b$).

This can be rewritten as $(ab)^+ c^\*d^+$ since $(ab)^\*ab = (ab)^+$ and $dd^\* = d^+$.

Another equivalent expressions is $a(ba)^\*bc^\*dd^\*$ since $(ab)^+ = a(ba)^\*b$.

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


# Question
Title: How to define a similarity between two graphs?
Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G\_1 = (V, E\_1)$, $G\_2 = (V, E\_2)$. $\newcommand\mG{\mathbb G}$(Let's denote the set of all graphs over the vertices $V$ with $\mG$, so $G\_1, G\_2 \in \mG$).

Now I'd like to measure how similar (up to isomorphism) those graphs are, so ideally we'd have a metric

$$d: \mathbb G \times \mathbb G \to \mathbb R\_{\geq 0}.$$

This should satisfy all the usual axioms of a metric

1. $d(G, H) = 0 \iff G \simeq H$ (Here we consider isomorphy as equality.)
2. $d(G, H) = d(H, G)$
3. $d(G, H) + d(H, I) \geq d(G, I)$

Is there a "useful" example of such a metric?

I know this is a little bit vague, but what I mean by that is that it should not be the trivial metric, and somehow relate to what we intuitively think would make sense: For example it would be nice if the distance if you remove one edge is smaller than if you remove two or more edges, or (I'm not sure if it actually makes sense, so it certainly is not necessary) that the distance between the empty graph and the complete graph is maximal.

For the sake of simplicty you can assume that $V$ is finite.

# Answer
One such metric which is very useful is the **graph edit distance**. In a nutshell, you are allowed a certain number of operations, each with a cost, such as *edge insertion* or *edge deletion* (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost of a transformation from one to the other (the costs need to be symmetrical for this to be a distance, e.g. the cost of deleting is equal to the cost of adding, and are usually taken to be unitary).

There are applications outside of pure graph theory such as pattern recognition or in bioinformatics (generalisations of string edit distance useful for DNA analysis).

Note that usually we don't consider "edit distance up to isomorphism" as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.
> 15 votes

# Answer
A very natural metric for graphs on the vertex set $\[n\]$ is $$ d(G,H) = \min\_{\sigma \in S\_n} |G \Delta H^\sigma|, $$ where $|G \Delta H|$ is the size of the symmetric difference between the edge sets of $G$ and $H$, and $H^\sigma$ is the graph obtained from $H$ by renaming the vertices according to the permutation $\sigma$.

I believe it satisfies all your properties.
> 12 votes

---
Tags: graphs, graph-isomorphism
---


# Question
Title: If the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?
From Wikipedia:

> A 32-bit register can store 2^32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common representations, the range is 0 through 4,294,967,295 (2^32 − 1) for representation as an (unsigned) binary number, and −2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1) for representation as two's complement.

---

So if the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

---

From a similar standpoint, if the integer representation used is "−2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1)", so does this mean that the register cannot handle numbers greater than 2,147,483,647?

# Answer
The contents of a register don't have any inherent semantics.

Some instructions might assume certain semantics. For example, the x86 ADD instruction assumes that the registers represent integers, either unsigned or signed using two's complement. There are signed and unsigned versions in the x86 architecture for the multiplication instructions. Another unlikely place in which sign makes a difference is promotion instruction, in which a smaller register is assigned to a larger register – you want either zero extension (in the unsigned case) or sign extension (in the signed case, assuming two's complement).

What this all means is that certain the instruct set favors some interpretations by having instructions that assume them, but beyond that, the interpretation of the data stored in a register is completely up to the user. Moreover, in x86 at least, the same register can be used for both signed and unsigned operations. The register doesn't "know" which type of data it stores – it is completely up to the programmer. (One could imagine different architectures with different conventions.)
> 3 votes

---
Tags: cpu, bit-manipulation
---


# Question
Title: Reductions among two problems related to walks of length $k$
Consider the following two problems:

A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$.

B. Given a directed graph, two vertices $s,t$ and a parameter $k$, determine if the graph contains a path from $s$ to $t$ (not necessarily simple) of length $k$.

How can I reduce problem B to problem A?

I know that I can make a DFS tree at height $k$ with repeating vertices, however it solves the problem directly rather than by reduction.

# Answer
> 1 votes
Since $k$ is a constant you can solve $B$ in polynomial-time by exploring all $O(n^{k-1})$ paths of length $k$ starting from $s$ and ending in $t$, as you point out.

At this point the reduction is trivial: If the answer to an instance $\langle G, s, t\rangle$ of $B$ is "yes" then the corresponding instance of $A$ is $G$. If the answer to the instance $\langle G, s, t \rangle$ is "no", then the instance of $A$ is the empty graph.

---
Tags: graphs, reductions
---


# Question
Title: Addition of 3 bits using Full Adder when the initial carry bit is 0
**How do I add 3 bits using full adder and basic gates, when the initial carry bit is 0??**

I have tried using two full adders where two terminals of the first adder gets the first two inputs then the output of this adder goes to of the inputs of the second adder and the third input is given to the second input terminal of the second adder. The carry out from the first adder goes to the carry input of the second adder.

**I've added a picture** of the circuit which was created by using **Logisim**(software for designing digital logic circuit).

But it doesn't give the right answer.

normally in binary system, for **addition of three bit sum is 1 and carry output bit is 1.**

> **1+1+1 = 1 & carry bit = 1**

But as you can see in the picture of **the circuit I designed** below, output of my circuit for **adding three binary digit, sum is 0 and carry output bit is 1.** which is **not the right answer**

> **1+1+1, is sum = 0 & carry = 1**

The reason of this is clear to me. But I can't design the exact circuit. How do I design the circuit that can add 3 bit when initial carry is 0?

# Answer
> 1 votes
That component is a full adder, and this is how you wire it up:

If you set the carry in to zero, you get a *half adder*. You can construct a full adder from two half adders:

# Answer
> 0 votes
A *full adder* adds three bits and outputs a sum and a carry. If you want to add three bits, you just connect them to the inputs x, y, and carry of the full adder.

If for some reason there is a requirement that the carry input of the first full adder must be zero, then you leave that first full adder totally unconnected and connect to the three inputs of the second full adder.

---
Tags: digital-circuits
---


# Question
Title: Correctness proof of a greedy approximation algorithm
How do I prove the correctness of this algorithm?

# Answer
> 0 votes
Desicion of Algorithms : $ T\_{1},T\_{2},....,T\_{i}$ , cost $ C = C\_{1},C\_2,....,C\_i$

$ \frac{Algo}{Opt} = \frac{C\_1 + C\_2 + ... + C\_i}{(C\_1/n\_1)\*n}$

and $ 4C\_1 \geq C\_k ,\forall 1 \leq k \leq m$

$ \implies \frac{C\_1 + C\_2 + ... + C\_i}{(C\_1/n\_1) * n} \leq \frac{4iC\_1}{(C\_1/n\_1)\*n} = \frac{4in\_1}{n}$

consider $ \frac{C\_1}{n\_1} \leq \frac{C\_k}{n\_k} \leq \frac{4C\_1}{n\_k} \implies n\_k \leq 4n\_1 $

$ \implies n\_1 + n\_2 + ... + n\_{i-1} \leq n \implies 4(i - 1)n\_1 \leq n \implies \frac{4in1}{n} \leq \frac{4n\_1 + n}{n}$

$\frac{Algo}{Opt} \leq \frac{4in\_1}{n} \leq \frac{4n\_1 + n}{n} \leq \frac{4n\_1 + n\_1}{n\_1} \leq 5 $

---
Tags: algorithms, greedy-algorithms
---


title: Why is universality of CFG undecidable?

text:
# Question
Title: Why is universality of CFG undecidable?
Let $\text{ALL-CFG} = \\{\left\<G\right\> \mid G\text{ is a CFG and } L(G) = \Sigma^\*\\}$.

I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not appropriate.

Let $C$ be a CFG. Then $\bar{C}$ is a CFG by closure under complement. Since the emptiness of CFG is decidable, we can use it to decide whether $\bar{C}$ is empty and therefore whether $C$ is universal.

This problem has confused me a lot. Really appreciate your help. Thanks!!!

# Answer
> 1 votes
The context-free languages are not closed under complement. For example, $\overline{\\{a^nb^nc^n : n \geq 0\\}}$ is context-free, but its complement isn't.

---
Tags: computability, undecidability
---


# Question
Title: Functional Abbreviation for Inst Expression in Turing's 1936 Paper
In Turing's 1936 paper On Computable Numbers Page 30-31, and its Correction Page 1-2 :

For a Turing Machine $M$, $Inst(q\_i S\_j S\_k L q\_l ) $ means that if $M$ scans symbol $S\_j $ under $m-configuration$ $q\_i$, then the symbol on the square under scanner (with symbol $S\_j $ ) is to be replaced by symbol $S\_k$, and the scanner/header moves one unit $Left$, and its new $m-configuration$ becomes $q\_l$.

> At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.

> The interpretations of the propositional functions involved are as follows :
>
> ${R\_S}\_j(x,y)$ is to be interpreted as "In the complete configuration $x$ (of $M$) the symbol on the square $y$ is $S\_j$.
>
> $I(x,y)$ is to be interpreted as "In the complete configuration $x$ (of $M$) the square $y$ is scanned".
>
> ${K\_q}\_m(x)$ is to be interpreted as "In the complete configuration $x$ (of $M$) the m-configuration is $q\_m$".
>
> $F(x,y)$ is to be interpreted as "$y$ is the immediate successor of $x$".

Then, for establishing equivalence between Turing Machine and restricted Hilbert functional calculus, it is written:

> $Inst(q\_i S\_j S\_k L q\_l ) $ is to be an abbreviation for:
>
> $(x,y,x',y')$ { ($ {R\_S}\_j(x,y) \\,\\&\\, I(x,y)\\,\\&\\, {K\_q}\_i(x) \\,\\&\\, F(x,x') \\,\\&\\, F(y',y)) \to $ $( I(x',y') \\,\\&\\, {R\_S}\_k(x',y) \\,\\&\\, {K\_q}\_l(x') \\,\\&\\, F(y',z) ∨ \[( {R\_S}\_0(x,z) \to {R\_S}\_0(x',z)) \\,\\&\\, ({R\_S}\_1(x,z) \to {R\_S}\_1(x',z)) \\,\\&\\, ... \\,\\&\\, ({R\_S}\_M(x,z) \to {R\_S}\_M(x',z))\])$
>
> } $ S\_0, S\_1, ..., S\_M $ being the symbols $M$ can print.

---

I am unable to convince myself of the exact correctness of the above formula w.r.t. to the meaning of $Inst(q\_i S\_j S\_k L q\_l ) $. More specifically, why do we have the following expression included? What is he trying to *"cover"* by including it?

> $ ... \\,\\&\\, F(y',z) ∨ \[({R\_S}\_0(x,z) \to {R\_S}\_0(x',z)) \\,\\&\\, ({R\_S}\_1(x,z) \to {R\_S}\_1(x',z)) \\,\\&\\, ... \\,\\&\\, ({R\_S}\_M(x,z) \to {R\_S}\_M(x',z))\] $

# Answer
The first part of the disjunction is for stating that the next "state/m-configuration" of the machine is the one established in $Inst(q\_i, S\_j, S\_k, L, q\_l)$ (in case z takes as value the next cell of y', i.e., y), the second part of the disjunct is used to say that the part of the tape not scanned by the machine preserves its value.
> 1 votes

---
Tags: turing-machines, computability, first-order-logic
---


# Question
Title: Is there a polynomial sized arithmetic formula for iterated matrix multiplication?
I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow up with some more details.

In particular, they describe a scheme for iterated matrix multiplication (for the purposes of this post, multiplying $n$, $n \times n$ matrices) in log space, poly "catalytic space", and polynomial time. The argument to the best of my understanding can be sketched as follows.

1. Theorem 4 (second article) says any arithmetic formula (i.e. arithmetic circuit w/ fanout 1) of depth $d$ can be computed with a program of size $4^d$ (and all the previously mentioned space guarantees). Here, "program" is in the context of register machines, and the size is the number of instructions and equals the runtime.
2. Brent et al. 1973 proved that any arithmetic formula of size $s$ can be "balanced" to have depth $O(\log s)$, so combining with (1) it has a program of size $poly(s)$
3. For some reason, I cannot find this last, *implied* claim in either of the articles: there is a arithmetic formula of size $s = poly(n)$ for iterated matrix multiplication. This would imply the claim made by the papers -- that IMM can be done in polynomial time with the other space bounds, but for some reason I can't find the claim explicitly written out, which suggests I am missing something.

The smallest formula I can think of for iterated matrix multiplication is "divide and conquer" on the number of matrices, and results in size $n^{O(\log n)}$, and I don't see any way to improve on this.

The first linked article says "iterated matrix product can be computed transparently by polynomial size programs", which would seem to follow by putting together 1,2, and 3, but it references an old thesis I can't find anywhere.

So, it's either the case that I've totally misread the argument, or there should exist a polynomial sized arithmetic formula for iterated matrix multiplication. Does anyone know of one?

# Answer
> 2 votes
After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size formula. The idea seems pretty straightforward too:

Everything stated previously applies to all rings, so if the elements of the matrix were $Z\_2$, then we could consider the ring of $n \times n$ matrices over $Z\_2$. There's clearly a $\log n$ depth formula for the product of $n$ ring elements, so we can apply theorem 4.

The only additional considerations are

1. Theorem 4 says the program will need only 3 working registers, but since each register holds an entire matrix, these registers will take up $O(n^2)$ space. This turns out to be completely fine for us, since we have polynomial catalytic space to work with.
2. In order to actually translate the program back onto our (catalytic) turing machine, we need to rewrite matrix instructions to instructions on the underlying ring ($Z\_2$ for example). Luckily, this is trivial since each instruction in the form $r\_i \leftarrow r\_i \pm x \ast y$ becomes $n^3$ primitive instructions: $r\_i^{uv} \leftarrow r\_i^{uv} \pm x^{uw}y^{wv}$ for $u,v,w = 1 \ldots n$ and no extra space of any sort is used.

This seems to be roughly in agreement with the $O(n^9)$ time complexity given by the second reference from the OP -- the program size of $4^d$ from Theorem 4 combined with the $\log\_2 n$ depth of the straightforward matrix multiplication formula makes an $O(n^2)$ sized program, each matrix instruction which is further broken down into $O(n^3)$ "primitive" instructions, and each instruction might take up to $O(n^3)$ time to execute on a turing machine due to the size of the inputs.

---
Tags: space-complexity, circuits, matrix-multiplication
---


title: How to detect outliers using DBSCAN?

text:
# Question
Title: How to detect outliers using DBSCAN?
I am working on a Fraudulent Cash Transaction Detection System using DBSCAN and I want to know what is the proper way to identify outliers?

Thank you

## ##Edite##

I had a problem how to represent the outer points extracted by the DBSCAN algorithm in Python visualization techniques, and found the solution here: https://www.youtube.com/watch?v=eq1zKgCFwkk

Enjoy your time

# Answer
> 1 votes
There are two parameters to DBSCAN: minPts, and ε.

You have an outlier point if there are fewer than minPts points within ε of it (using the appropriate distance metric). If this isn't the case, it's a sufficiently dense region that there is a cluster here.

---
Tags: data-mining, clustering
---


# Question
Title: Does $f(n) = O(g(n))$ imply $f(h(n)) = O(g(h(n)))$?
Can we prove the following, or find a counterexample?

> $$f(n) = O(g(n)) \Longrightarrow f(h(n)) = O(g(h(n)))$$

I should figure out whether $\log(n^{\log n}) = O(a^{\log n})$, and this will be facilitated if the above holds.

# Answer
Let's assume for simplicity that $f(n),g(n)$ both take positive integer values. Then $f(n) = O(g(n))$ iff there exists $C\>0$ such that $f(n) \leq Cg(n)$ for all $n$. This implies that for any $h\colon \mathbb{N} \to \mathbb{N}$, $f(h(n)) \leq Cg(h(n))$ holds for all $n$, and so $f(h(n)) = O(g(h(n)))$.

In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim\_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C\>0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim\_{n\to\infty} h(n) = \infty$. In particular, there exists $M\>0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.
> 2 votes

# Answer
Definitely no. $f(n) = O(g(n))$ is correct by $f(n) = n$ and $g(n) = n^2$. As $f(n) \neq g(n)$, hence, $f(h(n)) \neq g(h(n))$ for $h(n) = n$. By the way, we can find infinitely counterexamples for the statement.
> 0 votes

# Answer
From $f(n)=O\big(g(n)\big)$ we cannot conclude equality between $f$ and $g$. Most simple examples seems is when $f \in O(1)$, which means boundedness of $f$, but, obviously not every bounded function equals $1$.

On other hand, when $h:\mathbb{N} \to \mathbb{N}$ takes infinite values from $\mathbb{N}$, then we can conclude $f(h(n))=O\big(g(h(n))\big)$ .
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Arithmetic on signed 12-bit octal number stored in sign magnitude form
> What is 4365 − 3412 when these values represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal. Show your work.

Octal to binary:

* 4365: 100 011 110 101
* 3412: 011 100 001 010

By recognising the role of the sign bit, we can represent positive and negative 64-bit numbers in terms of the bit value times a power of 2. The binary number x, where x*i* means the ith bit, represents the number:

> (x11 * -2^11) + (x10 * 2^10) + (x9 * 2^9) + ... + (x1 * 2^1) + (x0 * 2^0)

I have used the formula given above to convert the value of octal 4365 in decimal:

> (1 * -2^11) + (1 * 2^7) + 2^6 + 2^5 + 2^4 + 2^2 + 2^0 = -2048 + 245 = -1803

Similarly, the value of octal 3412 in decimal is 1802.

Having obtained the two values in decimal, I subtract (-1803 - 1802), obtaining the result -3605.

Binary representation of 3605 is 111 000 010 101.

Converting it back to octal gives 7025.

---

This answer is wrong. It should be octal 7777 or decimal -3777.

The concept is not clear to me. Where am I going wrong?

# Answer
$100 011 110 101$ if is taken as SM in 12bit is $-245$ decimal and $011 100 001 010$ is $1802$ decimal, so we obtain $-245-1802=-2047$. $2047$ in binary is $11111111111$ with $11$ bits so for minus we add one more $1$ to left = $111111111111$. It is octal 7777.
> 1 votes

---
Tags: computer-architecture, arithmetic, number-formats, base-conversion
---


# Question
Title: I want to learn more about computer science. Where should I start?
Hello computer scientists,

I am a mathematician. I have taken some undergraduate courses in C++, Python, assembly language, boolean algebra, logic, graph theory, etc. I would like to learn more about computer science because I think it's cool. Could you give me some advice as to where to start? Thanks!

# Answer
This sounds like a better fit for say academia.stackexchange, as this is mostly subjective, so bear in mind this is mostly "just my opinion".

---

My advice would be to start with Algorithms, at a high level: learning about the big algorithmic paradigms (greedy, dynamic, linear programming...), runtime analysis (all the landau notations and derivatives, amortised analysis...), and go through the sorting algorithms at least. A good resource for that could be \[1\]. This part should be seen as "fun problem solving" I reckon.

In parallel, I would study the foundations of computer science and computability (easier if you've studied Logic before):

* Starting with finite automata/rational languages, and grammars
* Building your way up to Turing Machines (with equivalency to recursive functions and lambda calculus)
* Finally getting to the distinction between computable and undecidable

Along the way you should have got a small introduction to complexity theory, which should enable you to understand what the classes P and NP are, as well as what an NP-complete problem is.

---

\[1\] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.
> 1 votes

---
Tags: programming-languages, operating-systems
---


# Question
Title: Sampling from specific random distribution on sets
I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $\[0, n)$ (without replacement) such that the elements within each set fit in a subrange of length $w$. That is, an outcome set $S$ must have properties:

1. $S \subset \mathbb{N\_0} \\; \wedge\\; |S| = k$
2. $0\leq \min(S) \leq \max(S) \< n$
3. $\max(S) - \min(S) \< w$

You can assume that $k \leq w/2 \< w \ll n$.

Now there are many possible distributions possible over these sets. But I'm interested in those that have as property

$$\forall x:P\[x \in S\] = \frac{k}{n}\\;,$$

that is each integer in $\[0, n)$ has an equal chance of being in a set when sampled (or as close as possible). Beyond the above requirements, it'd be ideal if the distribution is an maximum entropy one, but this isn't as important, and something close would be fine too. As a minimum bar I do think every valid set should have a non-zero chance of occurring.

### Is there a practical way of sampling from a random distribution that matches the above requirements?

I've tried various methods, rejection sampling, first picking the smallest/largest elements, but so far everything has been really biased. The only method that works that I can think of is explicitly listing all valid sets $S\_i$, assigning a probability variable $p\_i$ to each, and solving the linear system $$\sum\_i p\_i = 1 \quad\bigwedge\quad \forall\_x:\frac{k}{n} - \delta \leq \sum\_{x \in S\_i} p\_i \leq \frac{k}{n} + \delta,$$ minimizing $\delta$ first, $\epsilon $ second where $\epsilon = \max\_i p\_i - \min\_i p\_i$. However this is very much a 'brute force' approach, and is not feasible for larger $n, k, w$.

# Answer
I have a suggestion for an algorithm that might get close to what you want:

1. Pick $m$ from the distribution $\mu$ (which I will describe below).
2. Choose $S$ uniformly at random from all sets containing exactly $k-1$ integers in $\[m+1,\dots,\min(m+w,n))$.
3. Add $m$ to $S$. Output $S$.

So, how do we pick the distribution $\mu$ to make this algorithm pretty good? I'll describe how, using linear programming.

Let $\mu\_i$ denote the probability of $i$ according to the distribution $\mu$. Then, we have

$$\begin{align\*} \Pr\[x \in S\] &= \sum\_m \Pr\[x \in S \mid m\] \Pr\[m\]\\ &= \mu\_x + \sum\_{m=x-w+1}^{x-1} {k-1 \over \min(w-1,n-m-1)} \cdot \mu\_m. \end{align\*}$$ Notice that this is linear in the $\mu\_i$'s. Now, let's treat the $\mu\_i$'s as variables to be solved for. Introduce the linear inequalities

$$\left| \Pr\[x \in S\] - {k \over n}\right| \le t,$$

where $t$ is another variable. Also add the equality $\mu\_1 + \dots + \mu\_{n-k}=1$ and $\mu\_{n-k+1}=\cdots=\mu\_{n-1}=0$ and the inequalities $\mu\_i \> 0$ for all $i$. We'll try to minimize $t$ subject to all of these inequalities. These are linear inequalities in the variables $\mu\_0,\dots,\mu\_{n-w},t$, so you can find a solution in polynomial time using linear programming. That gives you a distribution $\mu$ to use in the algorithm above.

This comes close to meeting your requirements. It ensures the set $S$ output by the algorithm meets your conditions 1, 2, and 3. It gets close to having $\Pr\[x \in S\] = k/n$; this is not exactly true, but it will be approximately true; and you can measure how large the error is when you solve the linear program, by inspecting the value of $t$. Also, due to the inequality $\mu\_i \> 0$, every possible set has a non-zero probability of occurring. Of course, this is only a heuristic, and it probably is not the maximum-entropy distribution, so you'll have to decide whether it is good enough for your needs.

You mention that you are dealing with a very large value of $n$. Given that, an additional heuristic would be to assume that $\mu\_i$ is constant for all $i \in \[3w,n-4w)$. Intuitively, the endpoints are the problem cases, and there is a loose symmetry among the middle values that makes it feel reasonable that they'll end up having about the same probability. So, we can enforce the constraint $\mu\_{3w} = \mu\_{3w+1} = \cdots = \mu\_{n-4w-1}$, by replacing $\mu\_i$ with $\mu\_{3w}$ for all $i \in \[3w,n-4w)$. Now there are only about $6w$ variables, namely, $\mu\_1,\dots,\mu\_{3w},\mu\_{n-4w},\dots,\mu\_{n-w}$ and $t$. Note that it is easy to express $\Pr\[x \in S\]$ as a linear sum of the $\mu\_i$ variables; this sum can be computed in $O(w)$ time. So, we end up with a linear program in about $6w$ variables, so you can apply a LP solver, and the resulting system will have $O(w)$ variables and inequalities instead of $O(n)$ variables and inequalities, so the LP solver should be a lot faster.
> 1 votes

---
Tags: randomness, sampling
---


# Question
Title: Is reservoir sampling unnecessary if you know the length of the stream of integers?
I think I understand Reservoir Sampling. If you have a large stream of integers then it allows you to get a sample of size k from that stream without putting it all in memory.

My question is what if you know beforehand the length of the stream? Say the length of the stream is n. In this case I would assume that a much simpler way to get a sample of k would be to just generate k random indices between 0 and n beforehand then as you iterate through the stream just select the integers corresponding to the indices you sampled beforehand. What would be the downside of this? Slower maybe?

# Answer
> 1 votes
There is no particular downside. It's a perfectly valid approach.

---
Tags: sampling
---


# Question
Title: Example of two undecidable languages that cannot be mapping reduced to each other
I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. One of my thought is to let $A$ be the halting problem, let $B$ be some non-Turing-recognizable language, then it is clear that $B$ cannot reduce to $A$, but I don't know which $B$ can I pick to show that $A$ cannot reduce to $B$

# Answer
There is no known *natural* example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.

Below, $\Phi\_e$ is the $e$th oracle machine according to some standard enumeration *(in older texts this is often written "$\\{e\\}$," which ... yeah)*.

---

The simplest approach *(indeed, the easiest I know)* is via **mutual diagonalization**: we build inductively a pair of increasing sequences of finite binary strings $$\sigma\_0\prec\sigma\_1\prec\sigma\_2\prec ...\quad\mbox{and}\quad \tau\_0\prec\tau\_1\prec\tau\_2\prec ...$$ such that for each $i$ there **do not exist** infinite binary sequences $f,g$ extending $\sigma\_i,\tau\_i$ respectively such that $\Phi\_i^f=g$ or $\Phi\_i^g=f$.

* Proving that such sequences in fact exist is a good exercise.

Taking $$a=\bigcup\sigma\_i,\quad b=\bigcup\tau\_i$$ we then have that $a$ and $b$ are Turing-incomparable. *(Thinking about this construction a bit, we can in fact ensure that $a,b$ are Turing-reducible to the halting problem.)*

---

A better result is that there are **computably enumerable** sets which are Turing incomparable (the *Friedberg-Muchnik theorem*). This is much harder to prove, however; it was the first example of a priority argument.

Yuval Filmus commented that a pair of "random" languages should probably work. There are multiple senses in which this is true - in particular, the set of pairs of infinite binary sequences which are Turing incomparable is both **comeager** and **of full measure** in the space of all pairs of infinite binary strings (with the usual topology and measure). The former observation is basically just the mutual diagonalization argument above, slightly tweaked; the latter is a bit harder to prove. *(In general, in computability theory measure is more complicated than category.)*

* In fact, the proofs of the observations in the previous paragraph actually yield stronger results without significant changes: namely, we get that for every noncomputable infinite binary sequence $f$ the set of infinite binary sequences Turing-incomparable with $f$ is both comeager and of full measure in the space of all infinite binary sequences.
> 6 votes

# Answer
A really simple example is $A\_\mathrm{TM}$ (i.e. the language of $\langle M, w \rangle$ where TM $M$ accepts $w$) and its complement $\overline{A\_\mathrm{TM}}$.

$A\_\mathrm{TM}$ is recognizable but not decidable, while $\overline{A\_\mathrm{TM}}$ is not even recognizable (if it *were*, then $A\_\mathrm{TM}$ would be decidable!).

Clearly, $A\_\mathrm{TM}$ is not mapping reducible (i.e. not many-one reducible) to its complement, since if it were, then its complement would be recognizable.
> 0 votes

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


# Question
Title: Why do we proof the halting problem with turing machines?
It can be shown that Turing machines, μ-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing machines.

Isn't it much easier to argue that the function `halts` below cannot exist in e.g. python since then I would be able to write the following program which is a contradiction.

```
def halts(source):
  ...

if __name__ == "__main__":
  this_file = open(__file__)
  if halts(this_file.read()):
    while True:
      pass
  else:
    return 1

```

Why is this proof not as good as the TM diagonal argument?

Edit: I read https://cs.stackexchange.com/a/94235/119946

> OK, fine. This proves that the halting problem can't be solved for code written in any programming language that has a get\_source\_code\_of\_current\_function() API. However, my favorite programming language doesn't have such an API. So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows? Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

I mean by that argument I can say the TM proofs only shows that the halting problem cannot be decided by Turing machines, but does not show anything about python. Isn't the crucial part, that (as I wrote) TM and modern programming languages can compute/decide the same problems? If one can decide the halting problem, then all other can do so as well and vice versa.

# Answer
> 2 votes
The goal we really want is a **total** impossibility result:

> There is no reasonable model of computation which can solve its own halting problem.

Church's thesis says that all the usual models (Turing machines, $\mu$-recursion, Python, etc.) are appropriately equivalent and so a proof in any one system should be convincing. However, initially at least we might not have **total** faith in the thesis; more generally, maybe we just want to avoid leaning on it too much as a matter of principle. In either case, what we then want is a proof of the unsolvability of the halting problem in the sense of some model of computation **so basic** that that same argument obviously lifts to any other model. For example, since files aren't a thing that all computation models interact with, we probably don't want to use them.

Turing machines are a sweet spot in this sense: they only deal with very simple objects (functions on natural numbers) which every model of computation will have, and they're intuitive to work with.

# Answer
> 3 votes
You could totally do that, but there are some consequences it's worth being aware of.

---

TM proofs only show difficulty of the halting problem for TMs, but here's a crucial thing that you might be overlooking: it is easy to implement a simulator of a TM in any language of one's choice. That can probably be done in a few dozen lines of code and it is conceptually straightforward. This lets us very easily see that the halting problem is also hard in those other languages, too.

The same is not true for Python. You can't write a Python interpreter in a few dozen lines of code.

---

Let me try it another way.

Some languages don't have a `__file__` global variable or anything with similar semantics. That makes it unclear whether your result applies to other languages.

Sure, we could try to write down a reduction. In some other language, we could build a Python interpreter that supports `__file__`. But that's not a trivial exercise! We might need to implement a filesystem, library functions that interact with the filesystem, a parser for Python code, an interpreter for Python code, and so on. Nothing you can code up in a few hours, and it's not trivial to construct such a reduction.

---

Now, sure, your argument does work, so it's just a matter of taste which you prefer. I am showing you some reasons why someone might prefer the TM proof. If you prefer the Python proof, that's fine. That's your choice. I just want you to be aware of the implications of your choice, and for you to understand all of the steps of reasoning that you have to go through, if you want to use it to draw conclusions about other programming languages. Arguably your choice makes some parts of the reasoning easier, and some parts (the application to other programming languages) harder.

---
Tags: turing-machines, halting-problem
---


# Question
Title: Which topics of mathematics should I need to learn to be a good app developer?
I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I want to continue in the field of programming. I have grasped the knowledge of basic programing concepts like variables, data types, conditional statements and loops etc. I guess the next stages are data structures and algorithms. Here the lack of math skills will make it difficult for me understand the concepts. I want to know which topics of mathematics I need to learn to be able to program for mobile app development. Can anyone help me, please?

# Answer
> 1 votes
An employer needs *one* person who is good at maths. Unless you go deep into scientific software, 90% of all programming jobs rarely require any mathematical skills at all.

You will sometimes find problems in programming contests that have clever solutions if you have mathematical skills, but often very similar problems have no such clever solutions.

# Answer
> 0 votes
I assume you are familiar with algebra. You should be comfortable with the concept of functions. You should be able to recognize and categorize basic functions (e.g., linear, polynomial, logarithmic, exponential). If you are not familiar with exponents and logarithms, I'd study those too. This is because the logarithmic function is frequently encountered when discussing algorithms and their complexities. Hope this helps.

# Answer
> 0 votes
For data structures and algorithms, basic algebra, exponential and logarithmic functions, and a basic course or book on discrete mathematics like one by Kenneth Rosen, should get you warmed up.

---
Tags: discrete-mathematics, linear-programming, mathematical-programming, mathematical-foundations, software-engineering
---


# Question
Title: Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?
I was looking for the limitations of a CFG. I think there is some limitation given there are only **finitely** many states of a PDA (or non-terminals in a CFG).

I suspect that languages like $\text{L} = \\{10,10100,101001000, \dots\\}$ can not be generated by a CFG. I can not see that intuitively (heuristics will help me). I have seen PDAs to be finite state automata in some places, and infinite in the rest.

Can someone tell me the limitations of a CFG / PDA (if any) and whether or not $\text{L}$ can be generated by a PDA/CFG? Additionally, are PDAs infinite state automata?

# Answer
> 1 votes
Since each context-free language can be described by a grammar, there are only countably many context-free languages (over a fixed alphabet). Therefore, "most" languages are not context-free. Examples of particular languages which are not context-free abound. Your language $\\{ 1010^210^3\cdots 10^n : n \geq 1 \\}$ is one such example. It can be proved to be non-context-free using the pumping lemma, for example.

Push-down automata have finitely many states, but an infinite stack. Although the stack is infinite, it can only be accessed in very specific ways, and this severely limits the power of the automaton. If we replace the stack with a queue, or add a second stack, then the automaton becomes much more powerful – equivalent to a Turing machine. But even such automata can only accept countably many languages. In particular, they cannot accept uncomputable languages such as that of the halting problem, as shown by Turing.

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


# Question
Title: How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?
This page on Wiki states that $\\{a^nb^nc^nd^n \ | \ n \> 0\\}$ can not be generated by a CFG. This does not make sense to me as $\\{$**S** $\to$ **ABCD**, **A** $\to$ a**A** | a, **B** $\to$ b**B** | b, **C** $\to$ c**C** | c, **D** $\to$ **D**d | d$\\}$ seems to be the desired CFG. By the Pumping lemma for CFG, I understand that it is not context-free but that seems very much contradictory.

Can someone clarify this? I got this doubt while I wondering if CFGs can generate all languages.

# Answer
Your grammar generates the language $\\{a^ib^jc^kd^\ell \mid i,j,k,l \geq 1\\}$, which is larger than $\\{a^nb^nc^nd^n \mid n \geq 1\\}$. For example, your grammar generates $abcdd$, which is not of the form $a^nb^nc^nd^n$.

That said, you can generate $\\{a^nb^nc^nd^n \mid n \geq 1\\}$ using a *context-sensitive* grammar. Moreover, unrestricted grammar can generate all recursively enumerable languages.
> 2 votes

---
Tags: context-free, formal-grammars, pumping-lemma, context-sensitive
---


title: A property of Kolmogorov random strings

text:
# Question
Title: A property of Kolmogorov random strings
I am working on the following problem:

> Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\\{0,1\\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ satisfies the following property:
>
> By interpreting $x$ as $x\_1\cdots x\_n$, with $|x\_i|=k$, for any $z\in\\{0,1\\}^k$ there is an index $i$ for which $x\_i=z$.

To show this, I want to suppose that if there exists a string $x$ of length $kn$ so that, after writing $x=x\_1\cdots x\_n$, not all $k$-bit binary strings appear in $x\_1\cdots x\_n$. Then ideally I want to show that $x$ can be described in less than $kn$ bits, which means $x$ have Kolmogorov complexity less than $kn$, which establishes the contradiction I want.

Any hints on how to do this?

For completeness, the Kolmogorov complexity of a string $x$ is defined as the length of the shortest *description* of $x$. And by the *description* of a string $x$, I refer to a pair $(M,w)$, where $M$ is a Turing Machine and $w$ is some string, so that $M$ halts on $w$ as input, leaving behind $x$ on the tape. I encode the pair $(M,w)$ as $0^{|M|}1Mw$. Then, for any string $x$, if $M$ is a Turing Machine that halts immediately upon execution, then $(M,x)$ is a description for $x$, of length $2|M|+|x|+1$. Hence the Kolmogorov complexity of $x$ does not exceed $2|M|+|x|+1$.

# Answer
Suppose that $x = x\_1 \cdots x\_n$, where $|x\_i| = k$, and there exists some $z \in \\{0,1\\}^k$ such that $x\_i \neq z$ for all $i$. We can encode $x$ by first listing $z$, and then encoding each $x\_i$ using $\log\_2 (2^k-1)$ fractional bits. The program also needs to know $n$. This shows that $$ K(x) \leq \log\_2 (2^k-1) \cdot n + C\_k + O(\log n), $$ where $C\_k$ is a constant that depends only on $k$. In particular, if $n$ is large enough that the upper bound will be less than $nk$.
> 1 votes

---
Tags: turing-machines, kolmogorov-complexity
---


# Question
Title: how to verify permutation generated in constant amortized time?
Here is an algorithm that generates the next permutation in lexicographic order, changing the given permutation in-place:

1. Find the largest index k such that a\[k\] \< a\[k+1\]. If no such index exists, exit (the permutation is the last permutation).
2. Find the largest index l such that a\[k\] \< a\[l\].
3. Swap a\[k\] with a\[l\].
4. Reverse the sequence from a\[k+1\] up to and including the final element a\[n\].

Is the next permutation generated in constant amortized time and if yes, how to verify it?

# Answer
For a number $m$, let $\alpha(m) = \max \\{ k : k! | m \\}$. This sequence starts at $\infty,1,2,1,2,1,3,\ldots$. I claim that in iteration $t$ of the algorithm (where $1 \leq t \leq n!-1$), we have $n-1-k = \alpha(t)$. The average value of $\alpha(m)$ is roughly $$ \left(1 - \frac{1}{2}\right) 1 + \left(\frac{1}{2} - \frac{1}{6}\right) 2 + \left(\frac{1}{6} - \frac{1}{24}\right) 3 + \cdots = \\ 1 + \frac{1}{2} + \frac{1}{6} + \cdots = e-1. $$ Since the running time of each step of the algorithm is proportional to $n-1-k$, we get that the algorithm runs in constant amortized time.

It remains to prove the claim $n-1-k = \alpha(t)$, which I leave to the OP.
> 1 votes

# Answer
Already posted:

* finding $l$ costs $n-k$
* swap costs $3$
* reversing costs $2(n-k)$

Thus, having found $k$ we do $3(n-k+1)$ steps.

In order to find $k$, we need to do $n-k$ comparisons which costs $2(n-k)$. Observe that after reversing, the tail of our permutation is increasing, so we only need to fix the first $k$ elements at most. This gives us that each $k$ is looked up at most $\frac{n!}{(n-k)!}$ times. Now we can get an upper bound on the total cost: \begin{align\*} \sum\_{k=1}^{n-1} \frac{n!}{(n-k)!} \cdot 3(n-k+1) &\leq 3\sum\_{k=1}^{n-1} \frac{n!}{(n-k)!} \cdot (n-k+1) \\ &\leq 3\cdot\sum\_{k=1}^{n-1} \frac{n!}{(n-k-1)!} \cdot \frac{n-k+1}{n-k} \\ &\leq 3\cdot\sum\_{k=2}^{n-1} \frac{n!}{(n-k)!} \cdot 2 \\ &\leq 6 \cdot n!\cdot\sum\_{k=2}^{n-1} \frac{1}{(n-k)!} \\ &\< 6 \cdot n!\cdot e \end{align\*}

Thus, we obtain $O(n!)$ after all. Since there are $n!$ permutations, the amortized time to produce the next one is constant.
> 1 votes

---
Tags: algorithms, permutations, amortized-analysis
---


# Question
Title: What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a
I'm given the following python function:

```
def recurser(i, j):
    x = 0
    if j == 0:
        return 1
    if i == 0:
        return 1
    x += recurser(i, j - 1)
    x += recurser(i - 1, j)
    x += 1
    return x

```

And I'm Asked to find x for any i = j = n where n can be any positive integer. however the recursion can do the job but the question says no recursion is allowed so that I have to solve the following recursive function:

* F(n,n) = F(n-1,n) + F(n, n-1) + 1
* F(0,a) = 1 for every positive a
* F(a, 0) = 1 for every positive a

Is there any solution for it?

# Answer
Your function produces the sequence A109128, that is $$ \mathit{recurser}(i,j) = 2\binom{i+j}{i} - 1. $$ You can prove this by induction.

How I found out: I computed the first few values, and searched the OEIS.
> 1 votes

---
Tags: computability, recursion, counting
---


# Question
Title: how does Kleene-Post show two languages that are not Turing reducible to each other?
I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.

I've seen it in many places: for example a very brief summary here (where it is used to answer a *different* question about **mapping** reducibility), and also in page 2 here and also page 40 of here. There's also a prior thread on Kleene-Post, but that asks something very specific about one component of Kleene-Post, not how the entire proof works.

Very roughly speaking, it seems to be something about constructing a pair of sequences of languages (or sequence of *sets* of languages, I'm not too sure) such that for each "step" in the sequence, there's at least one oracle TM (i.e. a TM that is able to query some oracle) for which an oracle for one "side" cannot be used to decide the other "side". Once these sequences are done, we take the intersection of every element in the sequence, and by construction all the languages in this intersection will fail to be mutually Turing reducible by every single possible oracle TM.

While I believe the general argument follows the above, I don't understand the details at all, since the proofs I've linked to use terminology (e.g. recursive, characteristic function, etc.) that differs significantly from those used by Sipser, the textbook I'm following (e.g. Turing recognizable, Turing decidable). There's also a few other proofs I've seen which I have not linked, and in those proofs I found the notation and exposition still difficult to understand.

My question is: how does the Kleene-Post proof work? What are the details of the construction, presented carefully in a way that is unambiguous and easily understood, preferably using terminology from Sipser as opposed to equivalent but different terminology?

# Answer
Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T\_0,T\_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T\_i^O(x)$ the output of the execution of $T\_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T\_i$ (Turing-)reduces $A$ to $B$ if $T\_i^B(x)$ halts for all $x$, and returns the truth value of "$x \in A$". We assume for simplicity that the output of $T\_i^B(x)$ can always be interpreted as a truth value.

We will construct two sequences $A\_0,A\_1,\ldots$ and $B\_0,B\_1,\ldots$ of "partial sets", that is, mappings from $\Sigma^\*$ to $\\{0,1,\bot\\}$. Initially, $A\_0$ and $B\_0$ map all strings in $\Sigma^\*$ to $\bot$. Moreover, $A\_{i+1}$ is an *extension* of $A\_i$, that is, if $A\_i(x)\neq \bot$ then $A\_{i+1}(x) = A\_i(x)$. Furthermore, each $A\_i$ or $B\_i$ is *defined* (not equal to $\bot$) for only finitely many words in $\Sigma^\*$.

We will eventually take $A$ to be a set *extending* all $A\_i$, that is, if $A\_i(x) = 0$ for some $i$ then $i \notin A$; if $A\_i(x) = 1$ for some $i$ then $i \in A$; and otherwise the status of $i$ doesn't matter (for definiteness, let $i \notin A$). The extension property guarantees that $A$ is well-defined. We define $B$ similarly.

We construct $A\_{2i+1},B\_{2i+1}$ from $A\_{2i},B\_{2i}$ in a way which rules out $T\_i$ being a reduction from $A$ to $B$. By assumption, there exists $x \in \Sigma^\*$ such that $A\_{2i}(x) = \bot$. Consider what happens when we try to run $T\_i$ on input $x$ with oracle $B\_{2i}$. If $T\_i$ tries to apply the oracle on a word $y$ on which $B\_{2i}$ is defined, then it gets $B\_{2i}(y)$. If $B\_{2i}(y) = \bot$, then we simulate *both branches* in parallel (each of them could further split down the road). One of the following must happen:

1. There is a branch on which computation halts.
2. All branches result in non-halting computations.

The second case is easy – $T\_i$ cannot be a reduction from $A$ to $B$, since it doesn't halt on input $x$, whatever happens in later stages of the construction. So we take $A\_{2i+1} = A\_{2i}$ and $B\_{2i+1} = B\_{2i}$.

In the first case, we actually have to do something. Pick a halting branch. The branch corresponds to a choice of definite values for some strings in $\Sigma^\*$ on which $B\_{2i}$ is undefined. We form $B\_{2i+1}$ from $B\_{2i}$ by keeping all values already defined in $B\_{2i}$, and defining the additional strings occurring in the halting branch according to the branch. We form $A\_{2i+1}$ from $A\_{2i}$ by keeping all values already defined in $A\_{2i}$, and defining $A\_{2i+1}$ on $x$ in the opposite way to what $T\_i$ answers in the halting branch: if $T\_i$ outputs Yes then $A\_{2i+1}(x) = 0$, and if $T\_i$ outputs No then $A\_{2i+1}(x) = 1$. This ensures that $T\_i$ does not reduce $A$ to $B$, since it outputs the wrong value on $x$.

We construct $A\_{2i+2},B\_{2i+2}$ from $A\_{2i+1},B\_{2i+1}$ in a similar way, switching the roles of $A$ and $B$, ruling out $T\_i$ being a reduction from $B$ to $A$.

Since the final $A$ and $B$ "encompass" all $A\_i,B\_i$, by construction no $T\_i$ reduces $A$ to $B$ or $B$ to $A$, and so there is no Turing reduction from $A$ to $B$ or from $B$ to $A$.

---

The dichotomy above (some branch halts / all branches never halt) is not computable, in the sense that given $A\_{2i},B\_{2i},T\_i$ we cannot determine which of the two options occurs. But it is possible using an oracle to the halting problem, since we can construct a Turing machine which tries out all branches in parallel, and immediately halts if one of them halts. Furthermore, by "going down the tree" we can find a halting branch if such exists. This shows that we can compute the sequences $A\_i,B\_i$ using an oracle to the halting problem.

Now suppose that when choosing a string $x$, then we always choose the first such string on which $A\_{2i}$ (or $B\_{2i+1}$) is undefined, according to some fixed ordering. This guarantees that any string will be eventually defined by some $A\_i$ and by some $B\_j$. Since the sequences $A\_i,B\_j$ are computable using an oracle to the halting problem, this shows that the sets $A,B$ are computable using an oracle to the halting problem.

---

Here is an alternative proof. Let $\mu$ be an arbitrary measure on languages such that $\mu(L) = 0$ for any specific language $L$ (we say that $\mu$ has no *atoms*). For example, $\mu$ could correspond to the experiment in which each word is put in the language with probability $1/2$ independently.

Let $\mathbf{A},\mathbf{B} \sim \mu$. The probability that $T\_i$ reduces $\mathbf{A}$ to $\mathbf{B}$ is 0, since fixing the outcome of $\mathbf{B}$ to be $B$, there is at most one language $L$ which $T\_i$ reduces to $B$, and by assumption $\mu(L) = 0$. Since there are only countably many machines $T\_i$, it follows that the probability that $\mathbf{A}$ reduces to $\mathbf{B}$ is zero. Similarly, the probability that $\mathbf{B}$ reduces to $\mathbf{A}$ is 0. We conclude that almost surely (that is, with probability 1), $\mathbf{A}$ doesn't reduce to $\mathbf{B}$ and $\mathbf{B}$ doesn't reduce to $\mathbf{A}$. In particular, there exist realizations $A,B$ such that $A$ doesn't reduce to $B$ and $B$ doesn't reduce to $A$.
> 4 votes

# Answer
(For the below, I referred extensively to this github repo as well as private communication with @aozgaa)

Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position $w$ in an ILB $A$ means that the $w$th string in $\Sigma^\star$ is a member of the language $A$.

Let $X$ and $Y$ be finite-length bitstrings (FLB). Let $P$ be an oracle TM, and $P^A$ means $P$ with an $A$ oracle "plugged in".

Let $Z(X)$ be the set of all ILBs with prefix $X$.

**Claim 1:**

There exists an FLB $X^\prime$ with $X$ as a prefix such that for any $A$ in $Z(X^\prime)$, $P^A$ satisfies at least one of the following: either 1. it cannot decide any language in $Z(Y0)$ or 2. it cannot decide any language in $Z(Y1)$.

**Proof:**

Consider all $A$ in $Z(X)$. Suppose there exists no $A$ for which $P^A$ halts on input $1 + |Y|$. Then, the claim is already true for $X^\prime = X$, since $P^A$ cannot be a decider for *any* language if there exists an input for which it never halts.

Otherwise, let $A^\prime$ be some $A$ for which $P^A$ halted. Look at the computation history of $P^{A^\prime}$, which may have calls to the $A^\prime$ oracle as a subroutine. The inputs $w$ to that subroutine may be any string, not necessarily the input $1 + |Y|$ itself.

Since $P^{A^\prime}$ halted, let $w^\prime$ be the highest input encountered by the $A^\prime$ oracle during the computation history. This means that $P^{A^\prime}$ does not care about any bits of $A^\prime$ after the $w^\prime$th. Thus, choose $X^\prime$ to be the first $w^\prime$ bits in $A^\prime$ (if the $A^\prime$ oracle is never actually called and there are no $w$, then just choose $X^\prime = X$), and thus for any $A$ in $Z(X^\prime)$, $P^A$ will halt on input $1 + |Y|$ with the same result as $P^{A^\prime}$.

Now consider the result itself: if it is "accept", then for any $A$ in $Z(X^\prime)$, $P^A$ will give the opposite result as (and thus cannot decide) any language in $Z(Y0)$. Conversely, if the result is "reject", then for any $A$ in $Z(X^\prime)$, $P^A$ will give the opposite result as any language in $Z(Y1)$. Either way, this $X^\prime$ satisfies the claim.

**Main result:**

There exist two infinite-length bitstrings $A$ and $B$ for which every possible oracle TM $P$ satisfies the following: $P^A$ does not decide $B$ and $P^B$ does not decide $A$.

**Proof:**

Begin with $X$ and $Y$ both the empty bitstring. Let $P\_0$ be the lexicographically (or any other ordering, it doesn't matter) earliest of all possible oracle TMs. Using claim 1, extend $X$ and $Y$ to $X^\prime$ and either $Y^\prime = 0$ or $Y^\prime = 1$ such that for any $A$ in $Z(X^\prime)$, $P\_0^A$ cannot decide any language in $Z(Y^\prime)$. Next, reuse claim 1 on $Y^\prime$ and $X^\prime$ (i.e. in the opposite order from before) and find $Y^{\prime \prime}$ and $X^{\prime \prime}$ such that for any $B$ in $Z(Y^{\prime \prime})$, $P\_0^B$ cannot decide any language in $Z(X^{\prime \prime})$.

Note that $Z(X^{\prime \prime}) \subseteq Z(X^\prime)$ and $Z(Y^{\prime \prime}) \subseteq Z(Y^\prime)$, so the condition from earlier still holds: for any $A$ in $Z(X^{\prime \prime})$, $P\_0^A$ cannot decide any language in $Z(Y^{\prime \prime})$

Now rename these new prefixes $X^{\prime \prime}$ and $Y^{\prime \prime}$ back into $X$ and $Y$, and starting with these new $X$ and $Y$ (that may now be non-empty), repeat the above for all the other oracle TMs $P\_1$, $P\_2$ and so on in (lexicographical or whatever) order, and continually extend the prefixes $X$ and $Y$. By construction, all of decidability properties of $P\_i$ from past iterations are preserved since by extending prefixes, we never leave the $Z(X)$ and $Z(Y)$ from past iterations.

Hence, this diagonalization argument can proceed indefinitely and construct arbitrarily long prefixes $X$ and $Y$ such that for any $P$ in the first $n$ oracle TMs (with $n$ arbitrarily large) and any $A$ in $Z(X)$ and $B$ in $Z(Y)$, we have $P^A$ does not decide $B$ and $P^B$ does not decide $A$.
> 3 votes

---
Tags: turing-machines, computability, reductions, undecidability, oracle-machines
---


title: Is the halting problem pointless?

text:
# Question
Title: Is the halting problem pointless?
Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot exist a program which can itself examine any arbitrary program and tell the user whether the program being examined will halt.

However, the thought experiment involves programs that were, frankly, designed to act in a way no sane programmer would ever want. Programs that are intentionally designed to halt without producing any useful output, programs that are designed to run indefinitely without halting. As addressed in the answers to the question *Is there a subset of programs that avoid the halting problem*, the halting problem doesn't apply to *all* programs. In the extreme case, the following programs would be trivial to analyze:

```
// Program 1:

while true {}

// Program 2:

print("I really can't tell with this one")

```

Rather, the halting problem merely indicates that there will always be *some* programs that can't be analyzed for halting. Those that *can* be analyzed fall into a certain class of programs that is reasonably well-researched and well-understood, and seems to align quite neatly with the class of *useful* programs. As for the original proof, while the logic holds, the programs used therein are poor indicators of code a human would actually write, and beg a certain question:

*Is it possible that the halting problem only applies to useless programs?*

# Answer
> 6 votes
The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible **in general**:

* Deciding whether two programs are the same (including, whether a program always outputs "true"). This is true even for even many simple definitions of "program".
* Deciding whether a mathematical fact is true or false
* Determining the longest time a program could run
* Checking whether a particular line of code like an error condition, is possible to reach

Of course, much like NP-complete problems, it may still be worthwhile to work on heuristic versions or special cases. But knowing that it's impossible in general, saves us a lot of time trying to come up with a perfect version--after all, we usually want a perfect version if we can get one. And knowing that a problem is impossible in general, is a good hint that it may be hard in specific cases you're likely to run into (checking if two programs are identical for example, is actually really hard in practice).

I think it's fairly reasonable to assume that for any program a human would write, the answer is "yes, it halts"--otherwise it's a bug! So the class of "programs a human would write on purpose" is not really that interesting to look at.

A more interesting question is, "what sorts of things in real programming, lead to problems analyzing whether the program halts?". For example:

* Almost all opcodes (ex. addition) complete
* Bounded loops complete (if the inner loop completes)
* Function calls with no recursion complete (if the body of each function does)
* Arbitrary while loops are hard to analyze
* Global variables may be hard to analyze
* Recursive function calls are hard to analyze

It's quite possible to invent a language (Charity, Epigram, and LOOP are academic/niche langauges, but you can also just imagine making a list of all these features and banning them from Java) where all programs halt. The challenge then becomes, can you express what you want to do in this language?

Edit: For an example of a practical program that is hard to analyze, here is bubble sort in python:

```
swapped = True
while swapped:
    swapped = False
    for i in range(0, len(list)-1):
        if list[i] > list[i+i]:
            list[i], list[i+i] = list[i+1], list[i]
            swapped = True

```

As a human, we can tell that this program halts for all inputs. It's much harder to get a computer to realize the same thing.

# Answer
> 0 votes
cf. Hilbert 10th problem and its resolution: determining whether a polynomial has integer roots is equivalent to the halting problem. That'd be an example of a very useful program which has no decidable halting problem, just consider a program that reads a polynomial and returns whether it has integer roots (note that in this setting, where the polynomial is not fixed, the problem is even one level of hardness beyond the halting problem, cf. the arithmetical hierarchy)

---
Tags: algorithm-analysis, computability, halting-problem
---


# Question
Title: What to do following a reduce in LR(1) parsing?
I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C-\>d, now what will the current state be? It seems like it could be both State 0 or State 3 (since state 3 loops back on itself on the lookahead c), i.e the GOTO of C from either state 0 or state 3. I am confused on states like 3 that loop into themselves.

The grammar is this:
$$S' \rightarrow S $$ $$S \rightarrow CC $$ $$S \rightarrow cC $$ $$C \rightarrow d $$

Question 1 : When the machine is at state 3. On encountering d as a lookahead, what is the action, and the new state?

Question 2 : At a more fundamental level, what do you do following a reduce in any kind of LR parsing. You can't stay in that state itself, and have to go somewhere else right? How do you make that choice?

Edit: I made a small mistake in the grammar productions. I had originally included the grammar C -\> c which was a mistake, and was removed.

# Answer
It may help to think in terms of lookahead *sets*, rather than lookahead *symbols*. So the item set in state 4 is actually:

$$\left\[ C \rightarrow d \cdot, \left\\{ c, d \right\\} \right\]$$

According to the definition of a $LR(1)$ automaton, what you should do is look at the lookahead symbol. If it's $c$ or $d$, then reduce by $C \rightarrow d$, otherwise it's a parse error.

This is correct behaviour, and you would get full marks for this answer. However, it's not how $LR$ parser generators work in practice!

A grammar which is $LR(1)$ but not $LR(0)$ has a $LR(0)$ automaton which is *correct*. The problem is that it's *nondeterministic*. And, indeed, there are variants (e.g. $GLR$) which allow for nondeterministic automata.

What that means is that in practical applications, you don't need to consult the lookahead set if you don't need to in order to make a parsing decision.

In your case, state 4 does not need lookahead to disambiguate it. If you didn't bother looking at the lookahead set, and just reduced anyway, the parse error would be caught as soon as you tried to shift the next symbol, because there isn't a transition for it. Try parsing the string *d$* to see what I mean.

Real-world grammars tend to produce $LR$ automata with a lot of these states where the only possible action is to reduce by a single production. So real-world parser generators tend to optimise them by not storing their lookahead sets. We call these $LR(0)$ reduce states.

In true $LR(k)$ parsing, you will often find $LR(0)$ reduce states which differ only in their lookahead sets:

$$\begin{eqnarray\*} q\_1: & \\,\\, & \left\[ A \rightarrow \alpha \cdot, \phi \right\]\\ q\_2: & & \left\[ A \rightarrow \alpha \cdot, \psi \right\] \end{eqnarray\*}$$

(Exercise: Why can this never happen in a $LALR(k)$ automaton?)

You can merge these states and the resulting automaton will still be correct, and will still be deterministic if the original automaton was deterministic.
> 0 votes

---
Tags: context-free, lr-k
---


# Question
Title: Network Flow - Bipartite Matching: Doctors Without Weekends Problem
**Problem**

You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next *n* days, the hospital has determined the number of doctors they want on hand; thus, on day *i*, they have a requirement that exactly *$p\_i$* doctors be present.

There are *k* doctors, and each is asked to provide a list of days on which he or she is willing to work. Thus doctor *j* provides a set *$L\_j$* of days on which he or she is willing to work.

The system produced by the consulting firm should take these lists and try to return to each doctor *j* a list *$L\_j'$* with the following properties:

(A) *$L\_j'$* is a subset of *$L\_j$* , so that doctor *j* only works on days he or she finds acceptable.

(B) If we consider the whole set of lists *$L\_1'$* ..... *$L\_k'$*, it causes exactly *$p\_i$* doctors to be present on day *i*, for *i* = 1, 2 .....*n*.

1. Describe a polynomial-time algorithm that implements this system.

Specifically, give a polynomial-time algorithm that takes the numbers *$p\_1$*, .... *$p\_n$*, and the lists *$L\_1$* ..... *$L\_k$*, and does one of the following two things.

* Return lists *$L\_1'$* ..... *$L\_k'$*, satisfying properties (A) and (B); or
    * Report (correctly) that there is no set of lists *$L\_1'$* ..... *$L\_k'$* that satisfies both properties (A) and (B).
2. The hospital finds that the doctors tend to submit lists that are much too restrictive, and so it often happens that the system reports (correctly, but unfortunately) that no acceptable set of lists *$L\_1'$* ..... *$L\_k'$* exists.

Thus the hospital relaxes the requirements as follows. They add a new parameter *c* \> 0, and the system now should try to return to each doctor *j* a list *$L\_j'$* with the following properties.

(A\*) *$L\_j'$* contains at most *c* days that do not appear on the list *$L\_j$*.

(B) (Same as before) If we consider the whole set of lists *$L\_1'$* ..... *$L\_k'$*, it causes exactly *$p\_i$* doctors to be present on day *i*, for *i* = 1, 2 ..... *n*.

Describe a polynomial-time algorithm that implements this revised system. It should take the numbers *$p\_1$* ..... *$p\_n$* the lists *$L\_1$* ..... *$L\_k$*, and the parameter *c* \> 0, and do one of the following two things.

* Return lists *$L\_1'$* ..... *$L\_k'$* satisfying properties (A\*) and (B); or
* Report (correctly) that there is no set of lists *$L\_1'$* ..... *$L\_k'$* satisfies both properties (A\*) and (B).

**My Thoughts**

Thank you for any guidance. This is an online class and unfortunately by the time I begin this there is little opportunity for teacher/student interaction... and I only post after looking on Google.

I appears to be a pretty straight forward bipartite matching network flow problem. My issue really arises from in either case that a schedule cannot be found.

To setup the graph place an edge from the source to each doctor with a flow \[capacity\] of 0\[*n*\]. This indicates that each doctor can participate in the Doctors W/O Weekends Program up to all the *n* days scheduling is needed for.

Adjacent to this setup will be all days in another column connected to the sink, with flow \[capacity\] of 0 \[*$p\_i$*\].

The edges from doctors to days are spelled out in the respective set of available days submitted by each doctor. All are set to 0 \[1\].

Once max flow / Ford-Fulkerson (or whatever name the algorithm goes by) is run we will have a potential schedule.

**Difficulty**

For me it seems that the optimal schedule can be achieved... sometimes. Just not all the time, for both cases. I'm struggling to determine how neither case is correct... to say there is "no set of lists"...

The mathematical definition of a subset seems to indicate any set where all elements are contained within another set is a subset. It did not say the size had to be smaller (i.e. set A == B).

The only thing I can see is that the problem does not state *$p\_i$* \<= *k* is a requirement.

If *$p\_i$* \> *k* on any link to the sink then a schedule can never be found.

Is there something else I'm missing?

# Answer
Based on your solution setup, the only thing that you need to check is whether the maxflow solution is a perfect matching or not.
> 0 votes

---
Tags: algorithms, network-flow, bipartite-matching
---


# Question
Title: Min path cover for a three-layer graph with all paths traversing all layers
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. Further, there is a feasibility matrix between colors and tastes and also one between tastes and smells. Hence, this can be thought of as a tri-partite graph; but there are edge constraints only between successive layers and not between every combination of layers; so it is a special case of a tri-partite graph (in a general tri-partite graph, there would also be edges between colors and smells). My objective is to cover all possible colors, tastes and smells with a minimal number of fruits.

Included below is a toy example. Here, we have three colors, two tastes and three smells. The connectivity is as shown on the left. The optimal solution is shown on the right. We can see that there are three paths that can cover all possible colors, tastes and smells. Hence, three fictional fruits will suffice and are the minimal required (since there are three colors and smells, we couldn't have done it with less than three).

Note: Cross-posted here: https://math.stackexchange.com/questions/3878929/minimum-edges-required-to-cover-all-vertices-of-three-way-graph. See great answer there as well.

---

My attempt:

One algorithm that comes to mind is the minimal path cover for a DAG. However, the well known formulation of that problem requires the paths to not share any vertices. We can see in the solution above that this constraint only gets in our way for this problem. The optimal solution does indeed have two paths that share a common taste vertex ($t\_1$). Hence, it doesn't immediately apply.

Another approach involves finding the min-edge cover for the bi-partite graph between colors and tastes and another min-edge cover between tastes and smells. Then, we can go to each taste and greedily assign colors and smells from the respective min-edge covers until everything is covered. This approach has a danger: the two min-edge covers are not aware of each other. In the figure below, the situation on the left shows one possible set of min-edge covers which leads to the optimal solution. But, we could also end up with the situation on the right. In that case, we'll end up needing four fruits to cover everything which is sub-optimal.

So, how do we fix the algorithm above? We want to encourage the behavior on the left from the min-edge cover and discourage the behavior on the right. We observe that $t\_1$ is a "super-vertex" with more colors and smells attached to it. So, we can assign the edges emanating from it lower costs. Then, we can modify the min-edge cover algorithm to prefer the edges with low costs. One approach would be to take the minimum of the number of colors and smells attached to each taste and divide $1$ by this. Then all edges emanating from that taste get this as the cost.

This algorithm will work for our toy example. However, how do we prove its optimality in general? And if it isn't optimal, how do we devise an optimal algorithm?

# Answer
I *think* this can be solved by reduction to a circulation problem.

Introduce a graph with source $a$ and sink $z$. The edges are as follows:

* All edges will have infinite capacity, lower bound 0, and cost 0 unless mentioned otherwise.
* Add an edge $z \to a$ with cost 1.
* Add edges $a \to c\_i$ for each color $c\_i$ and $s'\_k \to z$ for each smell $s\_k$.
* For each allowable combination $c\_i,t\_j$, add an edge $c'\_i \to t\_j$, and each allowable combination $t\_j,s\_k$, add an edge $t'\_j \to s\_k$.
* Add edges $c\_i \to c'\_i$, $t\_j \to t'\_j$, $s\_k \to s'\_k$ with lower bound 1.

Find the minimum cost solution to this circulation problem. I *think* there exists an integral solution, and it can found in polynomial-time.

The solution corresponds to a collection of fruits, and the cost of the solution is the number of fruits required. Each unit of flow corresponds to a fruit. The structure of the graph ensures that each attribute is covered by at least one fruit.
> 3 votes

# Answer
Let's denote:

* $C$, the $c$ different colors,
* $T$, the $t$ different tastes,
* $S$, the $s$ different smells,
* $X$, the edges of the possible color/taste combinations,
* $Y$, the edges of the possible taste/smell combinations,
* $G((C, T, S), (X, Y))$, the tripartite graph of the problem.

**FIRST STEP**

Let's take the bipartite graph $G\_L (C, T, X)$ containing colors and tastes (sub-graph of $G$). Let solve the following problem: find $t$ edges that cover all taste vertices and the maximum of color vertices.

For this use Hopcroft-Karp algorithm to get the maximum cardinality matching and complete with arbitrary edges for the unassigned taste vertices. Let's call $E\_L$ this subset of $X$.

This step time complexity is $O(|X|\sqrt{max(c, t)})$.

**SECOND STEP**

Let's take the bipartite graph $G\_R (T, S, Y)$ containing smells and tastes (sub-graph of $G$). Let solve the following problem: find $t$ edges that cover all taste vertices and the maximum of smell vertices.

As first step, use Hopcroft-Karp algorithm and complete arbitrarily to get $E\_R$, subset of $Y$.

Now, gathering $E\_L$ and $E\_R$, you get $t$ fruits that cover $T$. Let's call $M\_L$, the uncovered colors and $M\_R$, the uncovered smells. Note that by construction, it does not exist $t$ other fruits that cover $T$ with lower $|M\_L|$ or $|M\_R|$.

This step time complexity is $O(|Y|\sqrt{max(t, s)})$.

**THIRD STEP**

If $M\_L$ or $M\_R$ is empty, just build arbitrary fruits that contain the element of respectively $M\_R$ or $M\_L$.

Else there is a max flow problem to solve. Let's create a source with edges to every element of $M\_L$ and a sink with edges coming from every elements of $M\_R$. All these edges have weight 1.

Use also all edges of $X$ (from $C$ to $T$) and $Y$ (from $T$ to $S$) with infinite weights.

In fact, we need the residual graph of all the fruits we already generated in previous steps. So for every fruit $(a, b, c)$ of $(C, T, S)$, put a "cancel edge" of weight 1 from $c$ to $b$ and from $b$ to $a$.

Now every augmenting path you find let you change your fruits to generate a new fruit that will cover both a color of $M\_L$ and a smell of $M\_R$.

When there is no more augmenting path, the remaining unassigned elements of $M\_L$ and $M\_R$ have to be covered with different arbitrary fruits.

This step time complexity using Ford-Fulkerson algorithm is $O((|X|+|Y|)min(|M\_L|, |M\_R|))$

**PROOF**

Following steps 1 and 2, by construction, the minimum number of fruits to cover $G\_L$ (respectively $G\_R$) is $t+|M\_L|$ (respectively $t+|M\_R|$). Then the minimum number of fruits $f\_{opt}$ to cover $G$ and answer the problem follows:

$t + max(|M\_L|, |M\_R|) \le f\_{opt} \le t + |M\_L|+|M\_R|$

Let's call $A\_n$, the set of $n$ fruits that covers by priority the most elements in $T$, then in $C$, then in $S$. We denote $U(A\_n) = (u\_t, u\_c, u\_s)$, the number of vertices uncovered by $A\_n$ in $(T, C, S)$. The solution of the problem is $A\_{f\_{opt}}$ such that $U(A\_{f\_{opt}}) = (0,0,0)$. As a new fruit can always be chosen to cover 1 element, while $n \< f\_{opt}$, $U(A\_{n+1}) \< U(A\_n)$.

Note that for $n$ fruits, $A\_n$ is not unique, for instance any fruit would work for $A\_1$. Also, by construction, it exists at least one $A\_{n-1}$ which is subset of $A\_n$.

After step 2, by gathering $E\_L$ and $E\_R$ we obtain $A\_t$ as the $t$ fruits fully cover $T$ and as much as possible of $C$ and $S$. $U(A\_t) = (0, M\_L, M\_R)$.

Now in step 3, $n \ge t$, while there is an augmenting path, it let you build $A\_{n+1}$ such that $U(A\_{n+1}) = (0, u\_c-1, u\_s-1)$. Obviously, a new fruit cannot cover more that one color and one smell. If there is no augmenting path, it does not exist any $A\_n$ that let you generate a new fruit covering both, one color and one smell. Thus, every new fruit will cover a single one of the remaining colors and smells and at this point $f\_{opt} = n+u\_c+u\_s$.
> 2 votes

---
Tags: graphs, combinatorics, discrete-mathematics
---


# Question
Title: Algorithm for assigning items to one of two sets (2-CNF?)
I have a set of items (`A, B, C, D, ...`) which I want to assign to one of two sets (`set1, set2`). Trying all possible assignments and selecting my favorite has complexity $O(2^n)$, so I am trying to prune the number of assignments evaluated. I want to do this based on available knowledge that certain pairs MUST be present in the same set.

For instance: given `A, B, C, D`, and knowing that the following pairs must be together: `A & B, B & C` a solution would be `set1 = {A,B,C}, set2 = {D}`. Knowing that `A, B, C` must be together drastically reduces the number of assignments which have to be evaluated.

Note that there are pairs of items that may not occur in the same set. These relations however, are less obvious, which is why I restricted myself to finding the pairs listed above.

This already kind of looks like a satisfiability problem, which is good, as 2-CNF can be solved in linear time. In satifiablity, setting the variables to `true / false` could mean assigning the items to `set1 / set2` respectively. However, expressing items must be in the same set looks like this: `(A /\ B) V (!A /\ !B)`, which is 2-**D**NF.

2-DNF can be converted to 2-CNF in polynomial time, but would it be possbile to translate my problem directly to 2-CNF? This would allow me to keep the linear time complexity.

EDIT: As explained in the comments, 2-CNF would be satisfied by placing all items in the same set, which would defeat the purpose as this may not result in a "favorite" assignment. A better solution is the answer by @D.W., where for each connected component (which represents a cluster of items that must appear together), we can choose in which set to place it. This reduces the number of assignments that have to be evaluated, and allows us to find our "favorite" assignment.

# Answer
> 0 votes
There's a simpler approach, without using 2CNF. Instead, build an undirected graph with edges between pairs of items that must be together, then find connected components (e.g., using DFS). Now you can freely choose, for each component, which set it is associated with, and add all of its elements to that set; the result will be valid regardless of how you make those free choices.

---
Tags: time-complexity, 2-sat
---


# Question
Title: Are there more Turing-unrecognizable languages than recognizable?
Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language being Turing-recognizable?

# Answer
Yes, in fact one can show that there are uncountably many languages (say by representing a language as a sequence of the form $\\{0, 1\\}^\mathbb N$ which can be interpreted as the binary form of some real number in $\[0, 1\]$) while there are only countably many TMs (as any TM can be represented by a finite string), so almost all languages are undecidable, i.e. assuming we draw a language from an uniform distribution the probability of it being decidable would be 0.
> 2 votes

---
Tags: turing-machines, church-turing-thesis
---