# Question
Title: Why is the quantity of sentences not finite?
I'm currently studying formal languages. My lecture states that, while the words of a language are finite, the sentences build with the underlying grammar are not. But I don't get why this should be *generally* true. I can imagine grammar which leaves me with a finite amount of sentences.

I agree that one could create a language with infinite amount of sentences but I can't see why it should be generally the case.

# Answer
> 14 votes
The statement is not true for arbitrary languages and grammars. For example, the grammar $G$ consisting of the rules $$S \to a|b|C\\C \to cD\\D \to d|\epsilon$$ can produce the words $a$, $b$, $cd$ and $c$, so $|L(G)| = 4$, therefore $L(G)$ is finite.

---

The alphabet ("words of the language") is finite by definition. The language may or may not be finite. A trivial example of a grammar producing an infinite language is $G' = (\\{ S \\}, \\{ a \\}, P, S)$ with $P = \left\\{ S \to a|aS \right\\}$. $G'$ produces the infinite language $L(G') = \\{ a^n : n \> 0 \\}$.

Both finite and infinite languages exist and can be generated by grammars.

---

Note that all finite languages can be expressed through regular grammars and are therefore regular languages. However, not all regular languages are finite (see $G'$) The class of regular languages (type 3) is a subset of the class of context-free languages (type 2) which is a subset of the class of context-sensitive languages (type 1) which is a subset of the class of recursively enumerable languages (type 0): $$\text{Finite languages} \subset \text{Type 3} \subset \text{Type 2} \subset \text{Type 1} \subset \text{Type 0}$$

(And these are only the languages you can generate using formal grammars, in fact, recursively enumerable languages (type 0) are just a subset of the set of all languages.)

# Answer
> 32 votes
Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number, 2 is a number, 3 is a number, 4 is a number, 5 is a number, 6 is a number, 7 is a number, 8 is a number, 9 is a number, 10 is a number, 11 is a number, 12 is a number, 13 is a number, 14 is a number, 15 is a number, 16 is a number, 17 is a number, 18 is a number, 19 is a number, 20 is a number, 21 is a number, 22 is a number, 23 is a number, 24 is a number, 25 is a number, 26 is a number, 27 is a number, 28 is a number, 29 is a number, 30 is a number, 31 is a number, 32 is a number, 33 is a number, 34 is a number, 35 is a number, 36 is a number, 37 is a number, 38 is a number, 39 is a number, 40 is a number, 41 is a number, and 42 is a number. Of course, one could also think of other thing to point out, for example, that the son of the son of the son of the son of the son of the son of the son of the son of the son of my son is my grand grand grand grand grand grand grand grand grand son. I hope I did not make a mistake there, or two mistakes, or three mistakes, or four mistakes, or five mistakes, or six mistakes, or seven mistakes. Let us stop there, as 7 is a nice number.

Do you still think that there is a bound on the length of grammatically correct English sentences?

# Answer
> 2 votes
Here is an example from the famous book "Gödel, Escher, Bach" :

This is a sentence.

“This is a sentence” is a sentence.

‘“This is a sentence“ is a sentence’ is a sentence.

... you get the idea.

# Answer
> -1 votes
Since quotes are allowed in sentences, and quotes do not have to be grammatically correct, then there must be an infinite number of sentences:

*The man said "Blah blah blah blah blah...".*

---
Tags: formal-languages
---


# Question
Title: Term of System F whose type-erasure is $2(2)$
If $2$ is the Church numeral $\lambda fx. f(f(x))$, then is there a closed term $t$ of System F of type $\forall \alpha ((\alpha \to \alpha) \to (\alpha \to \alpha))$ such that the type-erasure of $t$ is the untyped term $2(2)$?

# Answer
> 3 votes
Consider the System F version of two:

$$ T = \Lambda \alpha.\lambda f:\alpha\to\alpha. \lambda x:\alpha. f(f(x))$$

We can then search for a term $M$ of the form

$$ M = \Lambda \alpha. T \tau\_1 (T \tau\_2) $$

and try to find types $\tau\_1,\tau\_2$, possibly depending on $\alpha$, such that $M : \forall \alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Surely $M$ becomes $2(2)$ after type erasure.

I'll leave finding $\tau\_1,\tau\_2$ as an exercise. Think about what is the type of $M$, and require it to be the wanted one: this provides $\tau\_1$. After that, choose $\tau\_2$ so that $M$ is well-typed.

---
Tags: lambda-calculus
---


# Question
Title: Showing that Hadamard is its own inverse
Im trying to work out that a Hadamard transform H (a unitary matrix) is its own inverse by applying it twice to an arbitrary state $|x⟩$:

$$H|x⟩ = \frac{1}{\sqrt{2^n}}\sum\_{y \in \\{0,1\\}^n}(-1)^{x \cdot y}|y⟩\\,.$$

Then \begin{align\*} H\left(\frac{1}{\sqrt{2^n}}\sum\_{y \in \\{0,1\\}^n}(-1)^{x \cdot y}|y⟩\right) &= \frac{1}{2^n}\sum\_{y \in \\{0,1\\}^n} (-1)^{x \cdot y}\sum\_{z \in \\{0,1\\}^n}(-1)^{y \cdot z}|z⟩\\ &=\frac{1}{2^n}\sum\_{y \in \\{0,1\\}^n}\sum\_{z \in \\{0,1\\}^n} (-1)^{x \cdot y}(-1)^{y \cdot z}|z⟩\\ &= \frac{1}{2^n}\sum\_{y \in \\{0,1\\}^n}\sum\_{z \in \\{0,1\\}^n}(-1)^{y \cdot (x + z)}|z⟩\\,. \end{align\*}

But I don't know how to get from here to $|x⟩$ again.

I know that $HH^\* = I$, but I want to show it this way, to understand what is happening.

# Answer
> 4 votes
Rewrite your final expression as $$ \sum\_{z \in \\{0,1\\}^n} \left| z \right\rangle \cdot \frac{1}{2^n} \sum\_{y \in \\{0,1\\}^n} (-1)^{y \cdot (x+z)}. $$ So to complete the proof, we need to show that $$ \sum\_{y \in \\{0,1\\}^n} (-1)^{y \cdot (x+z)} = \begin{cases} 2^n & \text{if } x=z, \\ 0 & \text{otherwise}. \end{cases} $$ If $x=z$ then $x+z = 0$ (computing modulo 2!), and so $(-1)^{y \cdot (x+z)} = 1$ for all $y$, hence the sum equals $2^n$. If $x \neq z$ then pick some $i$ such that $x\_i \neq z\_i$. We can partition $y$ into the $i$th coordinate $y\_i$ and all the rest $y\_{-i}$. Now $$ \sum\_{y \in \\{0,1\\}^n} (-1)^{y \cdot (x+z)} = \sum\_{y\_{-i} \in \\{0,1\\}^{n-1}} (-1)^{y\_{-i} \cdot (x+z)\_{-i}} \sum\_{y\_i \in \\{0,1\\}} (-1)^{y\_i \cdot (x+z)\_i} = 0, $$ since $x\_i+z\_i = 1$ (modulo 2) and $\sum\_{y\_i \in \\{0,1\\}} (-1)^{y\_i} = 1-1=0$.

---
Tags: quantum-computing
---


# Question
Title: Decoding a binary linear code given its generator matrix
Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$

I need to decode the received word $r$, $\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I am really strugggling with this. I know a message $m$ is encoded as $mG$.

So $mG$=$\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I have tried doing this by eye but couldn't find a single $m$ that I could multiply $G$ by to give me $r.$ Is there another method? Also I know that there must be $2^4=16$ codewords and when I wrote them out this one wasn't in them? Not sure if that helps or maybe I did that wrong?

# Answer
If you don't want to check all possibilities, you can use row operations to convert four columns of the matrix (of your own choosing) to the identity matrix, which will enable for very quick decoding. The code generated is exactly the same.

In more details, each row operation corresponds to multiplying the generator matrix from the left by some invertible matrix. In all, the effect of row operations is to multiply the original generator matrix by some invertible matrix from the left, say $H = AG$ is the new generator matrix. Since $A$ is invertible, both generator matrices generate the same code. If $r = xH$ then $r = (xA)G$, so if you decode $r$ for $H$, you can also decode it for $G$ very easily.

In your case, the row operations result in the following matrix: $$ \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix} $$

To decode $\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$, we simply add the first two rows to get the vector $\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}$. This shows that the original vector doesn't belong to the code.
> 1 votes

---
Tags: matrices, coding-theory, error-correcting-codes
---


# Question
Title: In which direction should I carry out a reduction when proving decidability/recognizability?
> **Definition:**
>
> $\text{A fuction}\ f: \Sigma^\* \to \Sigma^\*\ \text{is a reduction from Language A to language B if}\ w\in A \iff f(w) \in B\ \text{for every}\ w \in \Sigma^\*$.

**My question is which direction should I take in order to reduce a problem to another the other?**

From what I've been reading I concluded we can prove that $A \leq\_m B$ is we can use the TM of $B$ in order define the operation of the TM of $A$.

Let suppose I want to show that any co-recognizable language $L\_k$ reduces to $\overline{HALT} = \\{(\langle M \rangle, w): M(w)\ \text{doesn't halt}\\}$, that is $L\_k \leq\_m \overline{HALT}$.

Then if $T$ is the machine working on $w \in L\_k$ then I think we can make it work in this way

```
T on input w
  Run M on w;
     If M(w) = Halt
        Then Halt;
     Else
        Loop;

```

So if $w \notin \overline{HALT}$, then $M(w)$ halts and $T(w)$ halts $\implies w\notin L\_k$.

If $w \in \overline{HALT}$, then $M(w)$ doesn't halt and $T(w)$ doesn't halt $\implies w\in L\_k$.

Now suppose I want to prove that any co-recognizable language $L\_k$ reduces to $L\_{all} = \\{\langle N \rangle: N\ \text{halts on every input}\\}$.

My idea was to show that $\overline{HALT} \leq\_m L\_{all}$ and then by transitivity follows that $L\_k \leq\_m L\_{all}$.

So I have to ''use'' the machine $R$ operating on $L\_{all}$ to define a machine $P$ operating on $\overline{HALT}$.

Bu then I found this post Is the language of Turing Machines that halt on every input recognizable? which confused me a bit. There is shown that, indeed, $\overline{HALT} \leq\_m L\_{all}$ $(\overline{H} \leq\_m AH$ in the notation of the cited post), but using the machine operating on $\overline{HALT}$ (with its corresponding input) to define the machine operating on $L\_{all}$. To my eyes, it looks like the other way around.

So I'm lost.

One thing that gives peace to my soul is that all $m$-complete language are isomorphic. So probably I could shield myself behind this, assume that $L\_{all}$ is $m$-complete in the class of co-recognizable language just as $\overline{HALT}$, and show what was shown in the post above. I mean, loosely speaking, assume the direction of reduction doesn't matter.

But if I don't want make this assuptiom (that $L\_{all}$ is m-complete and therefore isomorphic) and just show that $\overline{HALT} \leq\_m L\_{all}$. Is valid to go from $(\langle P\rangle, w) \to R$

# Answer
When we reduce a language A to a language B, we take an instance $x$ of A and transform it into an instance $f(x)$ of B so that $x \in A$ iff $f(x) \in B$. The way to remember that this is the correct direction is that shows you how to decide A if you can decide B. This is the normal, everyday life meaning of "reduction".

The linked answer does exactly that – it transforms an instance of $\overline{HALT}$ to an instance of $L\_{all}$, thus reducing $\overline{HALT}$ to $L\_{all}$.
> 3 votes

---
Tags: turing-machines, reductions
---


title: Regular Expression Problem

text:
# Question
Title: Regular Expression Problem
Question is

$$\left\\{ w | w \text{ contains an even number of } 0\text{s or exactly two }1\text{s} \right\\}$$

I need to confirm my answer but i don't from where to ask someone.

My answer is

```
1*(01*0)*+11

```

but i don't know if it's correct or not

# Answer
> 0 votes
Your expression is close to correct for the 'even number of zeros' part; you just forgot the string could end in ones. I.e:

```
1*(01*0)*1* + 11 [where 'exactly two ones' means precisely that]

```

or

```
1*(01*0)*1* + 0*10*10* [where 'exactly two ones' implies any number of zeros]

```

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


# Question
Title: Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable?
Given a language $L$, I sometimes try to find a subset of $L' \subseteq L$ which I can prove is undecidable. I conclude that if a subset of $L$ is undecidable, then $L$ must be undecidable as well. Is this correct for arbitrary languages $L$ and $L' \subseteq L$?

What if someone said: $L'$ could be empty (we don't know due to the undecidability of $L'$), and we cannot conclude anything about $L$ from $L' = \varnothing$, therefore the proof is insufficient. Is this a valid point?

---

For example, in order to prove that the language $$L = \left\\{ w : M\_w \text{ halts on a a finite set of inputs} \right\\}$$ is undecidable ($M\_w$ is a turing machine constructed from $w$), I use the fact that $L \text{ is undecidable} \iff L^c \text{ is undecidable}$. $L^c$ can be described as $$L^c = \left\\{ w : M\_w \text{ halts on an infinite set of inputs} \right\\}$$ and $$L' = \left\\{ w : M\_w \text{ halts on all inputs } \Sigma^\* \right\\}$$ can be considered a subset of $L^c$. Using reduction, I can then prove that $L'$ is undecidable. If my assumption about subsets is correct, then $L^c$ must be undecidable as well, and therefore $L$ is undecidable.

(I know that the undecidability of the above language can be proven simpler, but I need an example for the use of subsets.)

# Answer
No, your conclusion is not correct. The fact that $L'\subseteq L$ is undecidable do not imply anything about $L$. Indeed, consider $L=\Sigma^\*$ for some finite alphabet $\Sigma$. Then, $L$ is decidable.

Now consider $L'\subset L$ such that $w\in L'$ iff $w$ is the description of a halting Turing machine written with characters from $\Sigma$. Then, $L'$ is, of course, undecidable.
> 3 votes

# Answer
$L'$ can not be empty and undecidable at the same time.

However, the objection stands: given $L' \subseteq L$, knowing that $L'$ is (un-)decidable does not imply anything about $L$.

Indeed, if the complement of $L'$ is infinite, there are uncountably many languages larger than $L'$, so most of those are undecidable (and not even RE).

There are also languages larger than $L'$ which are cofinite, i.e. the complement of a finite set. Those are decidable.

In general, trying to reason about the decidability of sublanguages or superlanguages is not useful. You have to write a reduction function (and prove it such) to achieve (un-)decidability results. If inclusion were enough, probably no one would bother with reduction :-)
> 2 votes

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


# Question
Title: Backpropagation in multiple output neural networks
I want to understand how the backpropagation algorithm would work on a neural network with multiple outputs.

More specifically, I have a network with 21 binary (0/1) outputs and I want to minimize the number of outputs that I get correctly; in other words, I want to minimize the hamming distance between the output vector and the desired vector.

How does the loss function work here? How do I backpropagate the error and update the weights? I know this might be long to explain so I'm also happy with links to some good references that I could read on the matter.

# Answer
You have to pick a loss function before you can apply backpropagation or train your network. Once you do, you can apply backpropagation. Backpropagation doesn't tell you how to pick a loss function; that's something you have to do, based on what you're trying to achieve.

Neural networks don't have binary outputs. Rather, they have continuous outputs. You might want to use a logistic loss on each of the 21 outputs, and sum up those 21 losses and use that as your overall loss function. The logistic loss is effectively a generalization of the 0-or-1 loss to the case where you have a continuous output and you want to predict either 0 or 1.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: What is the Expected run time of an algorithm that randomly generates N unique strings of length D?
I was trying to rigorously/mathematically analyze the runtime of the following algorithm:

```
while i < n {
    b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
    if b_n NOT in HashTable[b_D]:
        HashTable[b_D] = b_D
        i++
}

```

First I started by thinking what is the probability of two strings matching and realized that the probability is equal to the probability of all bits matching:

$$ Pr\[b^1 = b^2\] = Pr\[\cap^D\_{i=1} \\{ b^1\_i = b^2\_i\\} \] = \frac{1}{2^D} = 2^{-D}$$

Then I realized that its crucial to know what the probability of a collision happening with something in the hash table if the hash table has $k$ elements (notice that its an equality because there are no intersections with events since all elements in the hash table are assumed to be unique):

$$ Pr\[collision\] = Pr\[\cup^k\_{i=1} \\{ b^{current} = b^{HashTable}\\} \] = k 2^{-D} $$

now the way I would normally proceed to calculate this is by writing the runtime $T(n)$ in terms of indicator random variable or some type or random variable and them compute an expectation over the distribution of coin flips of the algorithm.

$$ \mathbb{E}\[T(n)\]$$

however, I am having difficulties writing this step. The main issue is that it seems that in principle this algorithm could run forever (with low probability) so its possible that we loop several time in the same iteration trying to find a non colliding binary string. I think this weird **unknown** repetition is what I am having a hard time including in the summation. Anyone has any suggestion on how to proceed?

---

I think I just had a realization of maybe how to do this. Define:

$$ X\_i = \text{variable indicating if it took i steps to complete} $$

then we can do:

$$ T(n) = \sum^{\infty}\_{i=1} i X\_i $$

the difference from usual algorithms like this is that the first $n$ terms **have to be zero** since we need $n$ strings, so we can never take less than $n$ steps since we need $n$ strings.

Now I just need to compute $Pr\[X\_i\]$.

# Answer
The usual way to approach your problem is as follows. When you select the $i$th string, there are $i-1$ previous strings that you have to avoid, so the probability that you generate a new string successfully is $\frac{2^D-(i-1)}{2^D}$. The expected number of strings generated before you generate a new string is thus $\frac{2^D}{2^D-(i-1)}$ – this is just the expectation of a geometrically distributed random variable. Considering all $N$ steps, the overall expectation is $$ \sum\_{i=1}^N \frac{2^D}{2^D-(i-1)} = 2^D \sum\_{j=0}^{N-1} \frac{1}{2^D-j} \approx 2^D \log \frac{2^D}{2^D-N} \approx \frac{2^D}{2^D-N} N. $$
> 2 votes

---
Tags: algorithms, algorithm-analysis, randomized-algorithms, randomness
---


# Question
Title: Name for the "starting vertex" and "ending vertex" of a directed edge
Say a graph contains a directed edge **e** from vertex **a** to vertex **b**. Is there a standard name for vertex **a** relative to edge **e**? And similarly for vertex **b**?

Something akin to vectors in high school physics, where the initial point of the vector is called the "tail" and the terminal point of the vector is called the "tip"? I'd like to say something like "**a** is the tail of edge e" or "**b** is the terminal vertex of edge **e**."

# Answer
> 4 votes
* $a$ is the *tail* or *initial vertex* of the edge $(a,b)$
* $b$ is its *head* or *terminal vertex*.

---
Tags: graphs
---


# Question
Title: Show that if Automata $A$ recognize language $L$, there also exists an automata $A′$ that recognize $Double(L)$
I don't know if this question should have better been on math.Stackexchange

Let be the operation $Double$ on the words on an $\Sigma$ alphabet which inserts after each character a copy of this character. Thus, $D(ab) = aabb$, $D(abaab) = aabbaaaabb$, etc... We had to prove that these regular expressions are closed by this operation and it was a sucess.

> We now have to prove this properties for automata. In other words, we have to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$.
>
> I shouldn't use equivalence between automatas and regular expressions

**goal :** I therefore deduce that I have to prove that autmomatas are closed by the Double operation.

**the hypothese :** is that it exists a language $L$ such taht it exists an automata $A$ which recognizes it.

**proof attempt :** $D(L)$ being a language, it must be a *automata* associated.

But:

1. has(have ?) every language(s?) an associated automata?
2. Isn't this proof too short or taking its goal has an hypothesis ?

## Proof attempt n°2

Following Rick Decker's advises, here is the second attempt to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$ :

To prove it, we are goint to construct an automata $A'$ such that $A'=D(L)$.

The idea is to construct an input string of $w$ that we reads from left to right. After having read the entire string $w$, it checks whether the following char is the same. If it is the case we remain in the final state. Otherwise, we go to a transitional state and if the following char isn't exactly the same, we go to the bin state.

* 1. $Q=\\{q\_0, q\_1, q\_2, p\\}$, $q\_1,q\_2$ are waiting states, $p$ is a bin state.
* 2. $\Sigma$ is the alphabet. For the example it is : $\\{a,b\\}$.
* 3. $\delta : Q × \Sigma → Q$ is a function, called the transition function,

$$\begin{array}{c|cc|c|c|} & a & b\\ \hline q\_0 & q\_2 & q\_1\\ q\_1 & p& q\_0\\ q\_2 & q\_0&p\\ p & p & p\\ \hline \end{array}$$

* 4. $q=q\_0$.
* 5. $F=q\_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.

# Answer
Unfortunately, your second attempt is not correct. Since your automaton recognized all the words of the type $aabbbbaabb$, etc. And not the $Double(L)$ for a given regular language $L$.

You should proceed as follows. If $L\subseteq\\{a,b\\}^\*$ is regular, then there is a DFA which recognizes it. Let $\mathcal{A}=\langle\\{a,b\\},Q,F,q\_0,\delta\rangle$ the description for such a DFA. Assume $Q=\\{q\_0,q\_1,\ldots,q\_k\\}$ and $F=\\{q\_k\\}$ (WLOG we assume only one final state).

Now we are supposed to describe the DFA for $Double(L)$ provided $\mathcal{A}$. Here is the description of $D(\mathcal{A})=\langle\\{a,b\\},Q',F',q'\_i,\delta'\rangle$.

$q'\_i=q\_i$

$Q'=Q\cup\bar{Q^a}\cup\bar{Q^b}\cup\\{q\_P\\}\\;$ where $\\;\bar{Q^a}=\\{\bar{q^a\_j},\\,q\_j\in Q\\}$ and $\bar{Q^b}$ is defined similarly; $q\_P$ is for the sink state.

$F'=\\{\bar{q^a\_k},\bar{q^b\_k}\\}$

where all the "barred" symbols are new symbols.

The idea is to use the "barred" states to check the "Double" property. Hence here is how we define the function $\delta'$ on the basis of the old $\delta$.

Step 1: $\delta'=\emptyset$

Step 2: if $(q\_i,a,q\_j)\in\delta$ then $\delta'=\delta'\cup(q\_i,a,\bar{q^a\_j})\cup(\bar{q^a\_j},a,q\_j)\cup(\bar{q^a\_j},b,q\_P)$ and $\delta=\delta\setminus\\{(q\_i,a,q\_j)\\}$

Step 3: if $(q\_i,b,q\_j)\in\delta$ then $\delta'=\delta'\cup(q\_i,b,\bar{q^b\_j})\cup(\bar{q^b\_j},b,q\_j)\cup(\bar{q^b\_j},a,q\_P)$ and $\delta=\delta\setminus\\{(q\_i,b,q\_j)\\}$

Step 4: if $\delta\ne\emptyset$ then goto Step 2.

The idea is that you store in the barred state the next symbol you expect; if the next symbol is the expected symbol then you go on, otherwise send everything to the sink.
> 2 votes

# Answer
You said you showed this result using regular expressions. Take the idea you used then and apply it to automata. You assume you're given an automaton $A$ for the language $L$. You need to construct an automaton $A'$ which accepts all and only the strings in $D(L)$.

Here's a hint to get you started: if you have a rule in $A$ of the form $\delta(p, a) = q$, meaning that in state $p$, seeing input $a$, you go to state $q$, how would you modify that rule so that from state $p$, seeing $a$ and $a$ again, will go to state $q$? Perhaps you might introduce another state along the way from $p$ to $q$?
> 2 votes

---
Tags: automata
---


# Question
Title: BFGS vs L-BFGS -- how different are they really?
I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum super fast, whereas BFGS converges very slowly, and that too to a nonsensical minimum.

**QUESTION:** From my readings, it seems to me that BFGS and L-BFGS are basically the algorithm (quasi-Newton methods), except that the latter uses less memory, and hence is faster. Is that true? Otherwise, if they are more different, then how so?

Ultimately, I want to figure out if the difference in performance is due to some differences in the actual algorithms, or due to their implementation in the python SciPy modules.

**EDIT:** I am adding some data to support my claims of divergent behaviour from the two algorithms.

```
 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192

*** BFGS code ***

At iterate    1,  f= 21249.561722
At iterate    2,  f= 15710.435098
At iterate    3,  f= 15443.836262
At iterate    4,  f= 15386.035398
At iterate    5,  f= 15311.242917
At iterate    6,  f= 15211.986938
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116

```

# Answer
> 4 votes
No, they're not the same. In some sense, L-BFGS is an *approximation* to BFGS, one which requires a lot less memory. BFGS and L-BFGS are explained in great detail in many standard resources.

Very crudely, you can think of the difference like this. BFGS computes and stores the full Hessian $H$ at each step; this requires $\Theta(n^2)$ space, where $n$ counts the number of variables (dimensions) that you're optimizing over. L-BFGS computes and stores an approximation to the Hessian, chosen so that the approximation can be stored in $\Theta(n)$ space. Effectively, L-BFGS uses the approximation $H \approx M^\top M$ for some $k \times n$ matrix $M$ (I think).

Each step of L-BFGS is an attempt at approximating/guessing what the corresponding step of BFGS would do. However, a single step of L-BFGS takes a lot less space and time than a single step of BFGS. Consequently, you can do many more steps of L-BFGS within a particular time bound than BFGS. Therefore, you might find that L-BFGS converges faster, because it can do so many more iterations within a given amount of time than BFGS can.

I don't know what a nonsensical minimum means, or why BFGS would converge to something worse than L-BFGS if both were allowed to run for an unbounded amount of time.

---
Tags: optimization
---


# Question
Title: Is $L = \{\langle M, w \rangle: \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$ decidable?
I'm trying to find whether

$$L = \\{\langle M, w \rangle: \exists q.\ \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\\}$$

is decidable or not.

I don't know how to proceed here. I mean, I have the feeling that I have to know which state $q$ the machine $M$ 'skipped' in order to go ahead. For instance if $q = \text{Accept}$, it means that $M(w) = \text{Reject}$ and I guess that, in this case, $L$ can be shown to be a reduction from $L\_{empty}$ (written also $E\_{TM}$). So if we assumed that $L$ was decidable $\implies E\_{TM}$ is decidable which is not true.

But what about the case where $q \neq \text{Accept}$ state?

# Answer
> 2 votes
You can prove that $L$ is undecidable using a diagonal argument: Assume $M$ decides $L$. Then, define $\tilde{M}$ as follows: On input $x$, run $M$ on input $\langle x, x \rangle$. If it accepts, go through all states and then halt; otherwise halt without going to some dedicated state $q\_0$.

If you now run $\tilde{M}$ on input $\tilde{M}$, it runs $M$ on input $\langle \tilde{M}, \tilde{M} \rangle$. Since $M$ decides $L$, it accepts if and only if $\tilde{M}$ on input $\tilde{M}$ does not go through some state. This contradicts the construction of $\tilde{M}$. Hence, $L$ is not decidable.

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


# Question
Title: How would a CPU know if a piece of data is in cache or RAM or on disk?
How would a CPU know if a piece of data is in cache or RAM or on disk?

This would imply there's some sort of meta addressing scheme on where everything is.

# Answer
> 0 votes
How does the CPU know if a piece of data is in L1 cache? The L1 cache is part of the CPU (it's on the same chip) so the CPU just asks the L1 cache "do you have the data for address X?"; if it gets the answer "yes", it is good; if it gets the answer "no", then the CPU tries to read from RAM.

How does the CPU know if a piece of data is in physical memory or on disk? The operating system keeps track of what data has been paged out to disk. See https://en.wikipedia.org/wiki/Virtual\_memory for details on that.

---
Tags: cpu-cache
---


# Question
Title: Comparing Selection, Insertion, and Bubble Sorts for database application
Explain and compare selection, insertion and bubble sorts. Assume that your application (say a data base application) deals with large records where comparisons are performed by means of integer keys. Assume also that your application requires a stable sorting method, i.e. a method that does not change the relative ordering of elements that are equal. Which of these sorting methods would you choose, and why? (Hint: consider sorting based on the following integer keys 19, 14(1), 7, 12, 14(2), 10).

This is a question I'm studying in class, not sure which is the right one and why.

# Answer
> 1 votes
A "database" that isn't ashamed of calling itself "database" will have hundreds of thousands or millions of records. Any algorithm where the number of operations is quadratic except for special cases is totally unsuitable. So the answer is "none of the above".

You'd do some serious measuring to decide whether to just create an in-memory index (that means you don't sort anything at all, but you just record #1 = 7 at record 3, #2 = 10 at record 6, ...), or use merge sort or Quicksort. Quicksort only if you have a backup, in case there's a problem during the sort.

# Answer
> 0 votes
If you want a complete algorithm/definition of these sorts, you can just google it, so instead I'm going to give you a brief explanation.

**Bubble Sort**

Say n is the current element being swapped. When the sort starts n is the first element in the array. The algorithm begins by comparing n to the element adjacent to the right of it, and if it is bigger then it swaps n with the element to the right of n. Then it continues down the line, comparing each element to the right of n, swapping whenever n is larger. If n is smaller, however, the current n stays where it is and we choose a new n to be the element to the right of the old n. Then we compare the new n with the element to the right. Once we get accross the entire array we start at the beginning again and choose n to be the first element in the array, then continue til the array is sorted.

**Insertion Sort**

For insertion sort we maintain a sorted section of the list, and an unsorted section. The sorted section is on the left of the list, unsorted on the right. When the sort begins the sorted section has no elements and the unsorted section has every element in the array. The algorithm works as follows: Pick the first element in the unsorted list, insert it in the correct position in the sorted list, repeat until there are no more elements in the unsorted list and we are left with just a sorted list.

**Selection Sort**

Here we create a sorted list by "selecting" elements from least to biggest, and swapping them into the correct place. First, we choose the smallest element in the array and swap it into the first spot in the array. Then the second smallest element and swap into the second spot. Then third smallest and so on, until we have a sorted list.

**Performance**

Straight from my data structures and algorithms teacher, bubble sort is a *terrible* sorting algorithm, so just don't even use it. Is the list nearly sorted or is it random? If it is nearly sorted, then insertion sort is definitely faster. In fact it runs in linear time in that case. Compared to selection sort, which is O(n^2). It really just depends on the array, but in general Insertion sort takes the cake.

---
Tags: sorting, efficiency
---


# Question
Title: Implementation of caches on CPUs with pipelines
I've read that some current CPUs (e.g. Intel i7 and ARM A9) have (L1) cache latencies of multiple clock cycles while also being pipelined. Some devote multiple pipeline stages to instruction fetching.

How is the L1 cache implemented to support pipelining?

Is it, say, $k$ actual stages for decoding the address or does it use some asynchronous multiport logic with a datapath latency set to $k$ clock cycles?

# Answer
> 1 votes
http://caps.cs.binghamton.edu/papers/aggarwal\_ics\_2005.pdf

I've found this paper which explains in the introduction that with higher associative caches the datapath to read data, compare tags and drive output becomes too long to use with high clock frequencies. Therefore the cache access is split into the 3 stages: decode set, compare tags and read, drive data. It goes further and explains that the access can have an extra stage added to avoid redundent reads of data and only read data after comparing and matching the correct tag, which improves power usage.

Although not really related to my question the paper also explains cache set and way prediction techniques to reduce the latency by parallelising address calculation and the cache read operation, the original paper refers to an article on the alpha 21264 microprocessor on how to implement the prediction. http://mixteco.utm.mx/~merg/AC/pdfs/alpha\_21264.pdf

The technique is to reduce the latency by not waiting on the address calculation stages in the CPU pipeline. This is done by predicting the address of the data to be read and checking at the end of the operation.

# Answer
> 0 votes
"If so then what microarchitectual changes can be made to allow CPU to pipeline operations so that it can reach 1 operation per clock assuming all hits."

It seems you are confusing latency here with throughput. Many CPUs have two read and one write port, and can read two items and write one item in the same cycle. So I assume you are asking about one cycle latency. And this is a really interesting question, and the answer is: You can make your CPU *really* slow.

L1 cache doesn't have multi-cycle latency just for fun. Addressing data in a large cache takes time, and more time the bigger the cache is. You need more time to select the correct data, you need more time because you have tons of connections to all the different cache lines. The only way to get the number of cycles latency down is (a) reduce the clock speed and (b) reduce the size of the cache. Both are things that you don't want.

---
Tags: computer-architecture, cpu-cache, cpu-pipelines
---


title: Temporal alignment of two time series

text:
# Question
Title: Temporal alignment of two time series
I have two series of tuples

$$ A = \\{(x\_0,t\_{01},t\_{02}),(x\_1,t\_{11},t\_{12}),\ldots,(x\_n,t\_{n1},t\_{n2})\\} \\ B = \\{(y\_0,tt\_{01},tt\_{02}),(y\_1,tt\_{11},tt\_{12}),\ldots,(y\_m,tt\_{m1},tt\_{m2})\\} $$

where $m \neq n$ and $t$ and $tt$ are both time observations. $t\_{i1}$ and $tt\_{j1}$ are both the start of some epoch for arbitrary $i$ and $j$. $t\_{i2}$ and $tt\_{j2}$ are both the end of some epoch for arbitrary $i$ and $j$. $x\_i$ and $y\_j$ are the observations of a sensor during those epochs.

In my case $t\_{i1}$ and $tt\_{j1}$ are not guaranteed to match, nor are $t\_{i2}$ and $tt\_{j2}$. However, they do represent time epochs that overlap with each other. For instance if $t\_{11}$ and $t\_{12}$ stretches from 2015-01-02 to 2015-01-03 then $tt\_{11}$ and $tt\_{12}$ might go from 2015-01-01 to 2015-01-04.

What I'm hoping to do is align the observations $x\_i$ and $y\_j$ temporally into a single sequence that might look like

$$ C = \\{(x\_0,y\_0,ttt\_{01},ttt\_{02}),(x\_1,y\_1,ttt\_{11},ttt\_{12}),\ldots,(x\_p,y\_p,ttt\_{p1},ttt\_{p2})\\}, $$

where $p$ is the last observation in the sequence and the time observations $ttt\_{k1}$ and $ttt\_{k2}$ are the start and end of some epoch non-overlapping with later observations of $ttt\_{\mathit{whatever}}$.

I've already looked into some of the papers available on the subject and all of the work I've seen deals with image analysis, audio overlap, kernels, and others that seem a bit off focus than what I'm looking for. Is there more basic theory available that deal specifically with the situation I'm describing here? Or is my case just a specific one covered by some of the papers that I've been reading on?

# Answer
OK. So the problem is as follows (with different notation):

Inputs: disjoint intervals $I\_1,\dots,I\_k$; disjoint intervals $J\_1,\dots,J\_m$
Output: disjoint intervals $K\_1,\dots,K\_n$ that are a "refinement" of the $I,J$-intervals

The $I$-intervals are not necessarily disjoint from the $J$-intervals. We want the $K$-intervals to have the following property: if $x,y$ are in the same $K$-interval, then $x,y$ are in the same $I$-interval and $x,y$ are in the same $J$-interval.

This can be solved. Basically, you use a 'merge' procedure vaguely akin go the merge operation from Mergesort, but adjusted to deal with intervals. I'll assume the $I$-intervals are in sorted order, and the $J$-intervals are in sorted order (so $I\_1$ is the leftmost/smallest interval of the $I$-intervals, etc.).

The algorithm considers how $I\_1$ compares to $J\_1$:

* If $I\_1$ is wholly to the left of $J\_1$ (they don't overlap, and $I\_1$ is smaller than $J\_1$), then we output $I\_1$, delete $I\_1$ from the $I$-list, and continue.
* If $I\_1$ is wholly to the right of $J\_1$ (they don't overlap, and $I\_1$ is larger than $J\_1$), then we output $J\_1$, delete $J\_1$ from the $J$-list, and continue.
* If $I\_1,J\_1$ overlap and $I\_1$ is contained in $J\_1$, then do the following: if $I\_1$ is the interval $\[a,b\]$ and $J\_1$ is the interval $\[c,d\]$ (so $c\<a\<b\<d$), output the interval $\[c,a\]$, output the interval $\[a,b\]$, delete $I\_1$ from the $I$-list, delete $J\_1$ from the $J$-list, and insert $\[b,d\]$ to the front of the $J$-list.
* If $I\_1,J\_1$ overlap and $J\_1$ is contained in $I\_1$, do the symmetrical equivalent of the previous case.
* If $I\_1,J\_1$ overlap but neither is wholly contained in the other, and the left endpoint of $I\_1$ is to the left of the left endpoint of $J\_1$, do the following: if $I\_1$ is the interval $\[a,b\]$ and $J\_1$ is the interval $\[c,d\]$ (so that $a\<c\<b\<d$), output the interval $\[a,c\]$, output the interval $\[c,b\]$, delete $I\_1$ from the $I$-list, delete $J\_1$ from the $J$-list, and insert $\[b,d\]$ to the front of the $J$-list.
* If $I\_1,J\_1$ overlap but neither is wholly contained in the other, and the left endpoint of $J\_1$ is to the left of the left endpoint of $I\_1$, do the symmetrical equivalent of the previous case.

As you can see, once you've sorted the intervals, this can be handled by a linear scan using a case analysis. The total number of intervals in the output will be at most twice the total number of intervals in the input (i.e., $n \le 2(k+m)$).
> 2 votes

---
Tags: algorithms, time-series-analysis
---


# Question
Title: Büchi automata: accepting run vs. runs with arbitrarily many final states
I am currently learning about Büchi automata and have a combinatorial question about the acceptance condition.

Let $A=(Q,\Sigma,\delta,q\_0,F)$ be a (nondeterministic finite) Büchi automaton and $w=w\_1w\_2w\_3\ldots$ an infinite word over $\Sigma$. Suppose that for each natural number $n$ there exists a run

$q\_0 \xrightarrow{w\_1} q\_1 \xrightarrow{w\_2} q\_2 \xrightarrow{w\_3} \cdots$

that contains at least $n$ occurrences of a final state.

Does that imply the existence of an accepting run for $w$, i.e. one with infinitely many final states? I expect that the answer is no, but cannot find a counterexample. Hints would be appreciated.

# Answer
Consider $\Sigma = \\{0,1\\}$ and $w = 1101001000100001\ldots$, i.e., there is an increasing number of zeros between two ones. Now consider the automaton with states $q\_0, q\_1$, and $q\_A$ where $q\_A$ is the only accepting state. On input $0$, always stay in the current state. On input $1$ allow the following transitions: In state $q\_0$, either stay in $q\_0$ or go to state $q\_A$; in state $q\_A$, go to $q\_1$; in state $q\_1$, stay in $q\_1$.

If the transition $q\_0 \to q\_A$ happens at a position in $w$ that is followed by $n$ zeros, $q\_A$ will occur exactly $n+1$ times in that run. Since $w$ contains $n$ consecutive zeros for all $n$ but no infinite sequence of zeros, this is a counterexample to your statement.
> 5 votes

---
Tags: formal-languages, buchi-automata
---


# Question
Title: The complexity of $A^{k \cdot log_{x} (n)}$ is exponential?
The complexity of $A^{k \cdot log\_{x}(n)}$ is exponential? ($k$ and $x$ is constants, $A$ is defined constant base, $n$ is the size of the task).

It is in a class of polynomial complexity?

# Answer
> 1 votes
This is polynomial complexity, because

$$A^{k \log\_x n} = A^{k \lg n / \lg x} = (2^{\lg A})^{k \lg n / \lg x} = (2^{\lg n})^{k \lg A / \lg x} = n^{k \lg A / \lg x}$$

and $k \lg A / \lg x$ is a fixed constant.

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


# Question
Title: Can a Turing machine be both decidable and undecidable relative to itself?
Consider the language:

$A'\_{TM} = \\{\langle M,w\rangle: M \mbox{ is a TM with access to an oracle for } A\_{TM} \mbox{ and } M \mbox{ accepts } w\\}$

Clearly, we expect that any language is decidable relative to itself, including $A'\_{TM}$. So let $F$ be an oracle decider for $A'\_{TM}$ that has access to an oracle for $A'\_{TM}$. In particular, we can construct $F$ as follows.

$F = $ "On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

1. Query the oracle for $A'\_{TM}$ with $\langle M, w \rangle$.
2. If the oracle replies YES, accept. If the oracle replies NO, reject."

Now, consider the following TM, $D$.

$D$ = "On input $\langle M \rangle$, where $M$ is a TM.

1. Check if $M$ is an oracle TM with an oracle for $A'\_{TM}$. If it is not, reject. Otherwise, proceed to the next step.
2. Simulate $F$ on $\langle M, M \rangle$. If it accepts, reject. If it rejects, accept."

Now, suppose that we feed $\langle D \rangle$ as input to $D$. Then clearly, computation proceeds to Step 2, since $D$ has an oracle for $A'\_{TM}$. But Step 2 yields a contradiction, since we are forced to conclude that $D$ accepts $\langle D \rangle$ if and only if $D$ rejects $\langle D \rangle$. So it seems we must conclude that $A'\_{TM}$ is both decidable and undecidable relative to itself, which seems absurd.

# Answer
A Turing machine doesn't come with an oracle. The oracle comes from outside. Rather, an *oracle Turing machine* is a Turing machine that has a special way of accessing an oracle. When you run the Turing machine with a specific oracle $O$, whenever the machine activates the special mechanism for accessing an oracle, you forward the request to $O$. A phrase like "$M$ is an oracle TM with an oracle for $A'\_{TM}$" is thus meaningless.

You are saying that you run $D$ on the input $\langle D \rangle$, but you haven't specified what oracle you are running $D$ with. If you want $F$ to have the proper semantics, then you have to run $D$ with an oracle for $A'\_{TM}$. When run in this way, $D$ accepts $\langle D \rangle$ iff $F$ rejects $\langle D,D \rangle$ when run with $A'\_{TM}$, and so iff $D$ rejects $\langle D \rangle$ when run with $A\_{TM}$.

Notice that there is no contradiction: $D$ accepts $\langle D \rangle$ when run with the oracle $A'\_{TM}$ iff it rejects $\langle D \rangle$ when run with the oracle $A\_{TM}$.

The real reason this works out is that a machine cannot get as input an oracle TM together with an oracle, since the oracle is an *infinite* object and so it cannot be specified as input.
> 4 votes

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


# Question
Title: Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$
Does there exist a maximal set of Turing machines $S$ over the alphabet $\\{0,1\\}$ such that any $A \in S$ halts on input the description of any $B \in S$?

Take S to be the set of deciders. Then S satisfies the property, but is not maximal, because for example we can take:

* The set of TMs which are not equal to 0 and which halt on input any string not equal to 0. (Assuming 0 is not a deciding TM.)
* Where $A$ is any set of non-deciding Turing machines, the set of TMs which are not in $A$ and halt on input any string not in $A$.

Maybe we can construct such a set $S$ by infinite recursion or by Zorn's lemma, but I haven't been able to see how.

**Edit:** By *maximal*, I mean there is no $S' \supsetneq S$ satisfying this property.

# Answer
Let us construct a Turing machine $M$ such that $M$ first generates its own description $\langle M \rangle$ by recursion theorem. Then for any input $w$ it first checks if $w=\langle M \rangle$, if yes it halts. If not it starts counting infinitely. Now let $S=\\{\langle M \rangle\\}$. If you try to add any other Turing machine $T$ to $S$ , it could not be part of $S$ as $M$ won't halt on $\langle T \rangle$. Thus following your definition of a maximal set, $S=\\{\langle M \rangle\\}$ is such a set.
> 3 votes

# Answer
I'm not sure why I thought Zorn's lemma doesn't work, because it does, easily, and gives a stronger result than just a single example. Let's say that a set of Turing machines $S$ is *self-deciding* if, for any $A, B \in S$, $A$ halts on input $\langle B \rangle$. Then I claim that any self-deciding set $S$ can be extended to a maximal self-deciding set $S' \supseteq S$. (Since $\varnothing$ is self-deciding, this also shows at least one such set exists.)

*Proof.* Fix $S$. Let $\mathcal{A}$ be the collection of self-deciding sets containing $S$. $\mathcal{A}$ is partially ordered by inclusion (nothing to prove there). To apply Zorn, we need that any maximal chain has an upper bound. So take a chain $\mathcal{T} \subseteq \mathcal{A}$ and, as is usual, we just need to show that $\cup \mathcal{T} \in \mathcal{A}$. Fix $A, B \in \cup \mathcal{T}$. Then there exists $S \in \mathcal{T}$ such that $A, B \in S$, and since $S$ is self-deciding, $A$ halts on $\langle B \rangle$.
> 0 votes

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


# Question
Title: Is the search for a k-Hamiltonian Path NP-hard?
A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors.

This is an Hamiltonian Path:

This is a 3-Hamiltonian Path:

How would you prove that searching for a k-Hamiltonian Path is also NP-hard (if it is)?

# Answer
Any problem in **NP** that contains an **NP**-complete problem as a special case is **NP**-complete.

Any algorithm that can solve the $k$-Hamiltonian path problem must, in particular, be able to solve the case $k=1$, which is just an ordinary Hamiltonian path. We can obviously verify a claimed $k$-Hamiltonian path in polynomial time, so the problem remains in **NP**. Therefore, $k$-Hamiltonian path is **NP**-complete.
> 3 votes

---
Tags: proof-techniques, np-hard, hamiltonian-path
---


# Question
Title: How to extent primitive recursion from natural numbers to finite strings?
Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification with respect to finite strings.

* A relatively clean way out of this dilemma could be a two sorted language with both natural numbers and finite strings, and some basic functions between the two sorts, like the lengths of a string, or the string where one symbol is repeated n times.
* A nicer solution could be to avoid the need for natural numbers, and work with some more native finite string related concepts, like head/tail, substring, ... instead.

I wonder whether there exist a robust computational model (on finite strings) corresponding to primitive recursion, just like Turing machines represents a robust computational model (on finite strings) corresponding to general ($\mu$-) recursion.

# Answer
> 2 votes
You don't really need to do anything. Without loss of generality, let $\Sigma = \\{0, \dots, d-1\\}$. A string in $\Sigma^\*$ is (almost) just a natural number written in base-$d$. The only problem is that leading zeroes are significant in strings but not natural numbers so we instead associate the string $w\_1\dots w\_k\in\Sigma^k$ with the base-$d$ natural number that's written $1w\_1\dots w\_k$. The length function is just a suitably rounded logarithm, which is primitive-recursive anyway.

(The first way you'd try to compute a base-$d$ logarithm would probably be to use a *while* loop to repeatedly divide by $d$. But you can replace that with a *for* loop, since we know that $\log\_d n\leq n$.)

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


# Question
Title: Parity check and magnitude comparison in Residue Number Systems
Let

* $\\{m\_1,...,m\_t\\}$ be a set of relatively coprime integers
* $M=\prod\_{i=1}^tm\_i$ the range of this system
* $X$ an integer such that $X \in \[0,M-1\]$

This forms a Residue Number System and every integer $X$ can be uniquely represented in RNS format as $(x\_1,\dots,x\_t)$, where $x\_i = X\bmod m\_i, \forall i\in\[0,t\]$.

One can add,subtract,multiply efficiently in RNS by adding,subtracting,multiplying modulo $m\_i$ in parallel the corresponding RNS digits as in

$X\otimes Y=(x\_1,\dots,x\_t)\otimes(y\_1,\cdots,y\_t)=(x\_1 \otimes y\_1,\cdots,x\_t \otimes y\_t)$, where $\otimes=(+,-,\times) \bmod m\_i$

There are various operations though that are not efficient in RNS, like parity check or magnitude comparison. I've encountered an interesting algorithm for parity check directly in RNS and I would like to take advantage of it to perform sign detection (in fact checking whether the result of $X-Y$ is negative or not). The idea comes from another topic where I quote exactly the part I don't understand:

"*...one can compute $X-Y$ and if it underflows, the parity will be unexpected. That is, if $p(X)=X \bmod 2$, $p(X)\in\\{0,1\\}$ is the parity function, then $p(X−Y) \equiv p(X)+p(Y) \bmod 2$. However, if it underflows, it will wrap around to $M−1$. Therefore if the parity is off after $X−Y$, you know that $Y\>X$*".

What is meant by "parity if off?" How can I check an underflow by just checking the parities?

# Answer
The "parity check" of a number $X$ is 0 or 1 according to whether $X$ is even or odd. In other words, the parity of $X$ is $X \bmod 2$. We are assuming that you have a way to compute the parity of $X$, from the RNS representation of $X$. Let $p(X)$ denote the parity of $X$, i.e., $p(X) = X \bmod 2$.

Now let's suppose $X,Y$ are integers in $\[0,M-1\]$ that we have stored in RNS representation, and let's look at what happens when we subtract the RNS representations. If $X$ is represented as $(x\_1,\dots,x\_t)$ and $Y$ is represented as $(y\_1,\dots,y\_t)$, the result of the subtraction operation will be the RNS representation $(z\_1,\dots,z\_t)$ where $z\_i = x\_i-y\_i \bmod m\_i$.

What number $Z$ is $(z\_1,\dots,z\_t)$ the representation of? Well, if $X\ge Y$, then $Z$ will be $X-Y$. But -- and here is the key point -- if $X\<Y$, then $Z$ will not be $X-Y$, as $X-Y$ is negative and RNS can only represent numbers in the range $\[0,M-1\]$. Instead, what will happen is that we'll have $Z \equiv X-Y \pmod M$. Therefore, if $X\<Y$, we'll have $Z = X-Y+M$... which is not the same as $X-Y$.

If $X\ge Y$, then $X-Y \ge 0$ and we say that the subtraction $X-Y$ doesn't underflow; in this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ modulo 2. In other words, if $X \ge Y$, we will have $Z=X-Y$ and therefore using the properties of modulo-2 arithmetic we have

$$p(Z) = p(X-Y) \equiv X-Y \equiv p(X)-p(Y) \pmod 2.$$

In contrast, if $X \< Y$, then $X-Y \< 0$ and we say that the subtraction $X-Y$ underflows. In this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ plus 1 modulo 2. In other words, if $X\<Y$, we will have $Z=X-Y+M$ and therefore

$$p(Z) = p(X-Y+M) \equiv X-Y+M \equiv p(X)-p(Y)+1 \pmod 2.$$

Here I have used the fact that $M$ will always be odd, so $p(M)=1$.

---

This gives you a way to check whether $X\le Y$, given RNS representations for $X,Y$: you subtract them to get a RNS representation of some integer $Z$, and then test whether $p(Z) \stackrel{?}{\equiv} p(X)-p(Y) \pmod 2$.

The key observation is that "subtraction" of RNS representations is not *actually* computing the subtraction (of integers). Rather, it is computing the subtraction modulo $M$. If the result of the subtraction is in the range $\[0,M-1\]$, that's equivalent to subtraction in the integers. But if subtraction underflows, it's different.

This might look mysterious, but it's not as unfamiliar as it might feel. If you use twos-complement arithmetic on 32-bit integers, that is basically doing modulo $2^{32}$ arithmetic: addition of 32-bit ints is not actually addition (of integers), but addition modulo $2^{32}$. In other words, with twos-complement addition of 32-bit integers, the results of arithmetic operations "wrap around" modulo $2^{32}$. RNS is just like that, except that it "wraps around" modulo $M$ instead of modulo $2^{32}$.

---

"parity is off" means "parity is wrong", i.e., the parity doesn't match what you'd expect to get, if subtraction of RNS representations behaved like subtraction of integers.
> 2 votes

---
Tags: number-theory
---


# Question
Title: Showing that a binary linear code $C$ is self-dual
Let $C\*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c\_1, c\_2, c\_3, c\_4, c\_5, c\_6, c\_7$ is extended to the word $c\_1, c\_2, c\_3, c\_4, c\_5, c\_6, c\_7, c\_8$ for which $\sum\_{i=0}^8 c\_i =0$. Show that $C\*$ is self dual (I.e show that $C\*=C\*^{\bot}$.

Where $C\*^{\bot}$ is the orthogonal complement of $C\*$

I am given the generator matrix for $C$:

$$G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$

So I think $C\*$ is given by:

$$G\*= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0 & 1 &1 \end{bmatrix}$$

I can show $C\*$ and $C\*^{\bot}$ have the same dimensions but don't know what to do from here.

# Answer
> 1 votes
$G^\*$ is also a parity check matrix of the code $C^\*$ since $G^\*G^{\*T}=0$ and $\dim\ker\left(G^{\*}\right)=\text{rank}\left(G^\*\right)=4$. Since a parity check matrix of $C^\*$ is a generator matrix of $C^{\*\perp}$, we get that $C^\*$ is a self dual code.

---
Tags: matrices, coding-theory, error-correcting-codes
---


# Question
Title: How to draw (intuitively) the first and second principal component in PCA methods?
Assume I have some data in 2D. How to draw the first and second principal component in PCA method?

By referring to the image: the plot on the right is confusing, how I can detect the position of first PCA?

# Answer
> 2 votes
In the case of 2d data, the first principal component will be aligned along the direction of major continuity, and the second will be perpendicular to that, aligned along the least continuous direction. Generally just the eigen vectors at the mean x / mean y.

Sort of like so (sorry for the poor drawing)

My favorite reference on pca is A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS by Jon Shlens: pdf His example is in figure 2.

To address your comment:

# Answer
> 2 votes
If you draw a line in any direction, you can calculate the variance of the data points' projections on that line, i.e. how much they vary in that particular direction.

If you plot the curve where the distance from the origin to the curve in any direction is equal to the variance of your data in that direction, you will get an ellipse.

The major and minor axes of this ellipse are the first and second principal components.

---
Tags: machine-learning
---


# Question
Title: Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines
Consider $\mbox{Halt}\_\mbox{TM} = \\{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ halts on input } w\\}$ and $\mbox{A}\_\mbox{TM} = \\{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ accepts on input } w\\}$. I'd like to prove that any oracle TM $T$ that can query the $\mbox{A}\_\mbox{TM}$-oracle cannot decide $\mbox{Halt}\_\mbox{TM}$.

Intuitively, it appears that when $T$ queries this oracle with $\langle M, w \rangle$ and the oracle in turn replies "No" (i.e., $M$ does not accept $w$), $T$ is incapable of deciding whether $w$ is rejected by $M$ or $M$ is looping on $w$. Thus, the oracle cannot help $T$ in deciding $\mbox{Halt}\_\mbox{TM}$. However, this doesn't really prove that $\mbox{Halt}\_\mbox{TM}$ is undecidable relative to $\mbox{A}\_\mbox{TM}$, since $T$ could feed any query it pleases to the $\mbox{A}\_\mbox{TM}$-oracle. Would a contradiction proof work best in this case? (I.e., suppose that the halting problem is decidable relative to the acceptance problem...)

# Answer
> 4 votes
The two problems are equivalent up to many-one reductions.

**Reducing $\mathrm{Halt\_{TM}}$ to $A\_{\mathrm{TM}}$.** Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by marking all rejecting states as accepting. Then $\langle M,w \rangle \in \mathrm{Halt\_{TM}}$ if $\langle M',w \rangle \in A\_{\mathrm{TM}}$.

**Reducing $A\_{\mathrm{TM}}$ to $\mathrm{Halt\_{TM}}$.** Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by getting to an infinite loop at every rejecting state. Then $\langle M,w \rangle \in A\_\mathrm{{TM}}$ if $\langle M',w \rangle \in \mathrm{Halt\_{TM}}$.

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


title: Fitting a feedback loop to data points

text:
# Question
Title: Fitting a feedback loop to data points
If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation.

However, thinking in more programmer / computer science terms, let's say that I had something more like a pseudo random number generator where it had some internal state, and when you ran a function, it would do an operation, update the internal state and spit out a new value. (Note, I'm not trying to make a prng, just using it as an example of the type of function I'd like to fit to my data)

Are there any methods other than brute force for creating (or iteratively training, ala gradient descent) a system like that to give something close to a specific sequence of desired output values?

For example, a simple feedback function may look something like this in C++:

```
float SequenceGenerator()
{
    // internal storage
    static float internalState = 16.371f;

    // adjust the internal storage
    internalState += internalState * 83.12f;

    // keep the internal storage <= 100
    while(internalState > 100.0f)
        internalState -= 100.0f;

    // return the next value in the sequence
    return internalState;
}

```

I definitely see how i could choose some random value for the initial values for the starting state, and the multiplication amount. I can also see how I could compare the values that come out to my sequence and come up with something like a mean squared error.

I'm not sure however, how I might be able to do something like calculate a gradient to adjust those values to iteratively minimize the mean squared error.

Is there a way to do something like this?

(I can't seem to find appropriate tags other than PRNG, please let me know if there are better tags or feel free to edit)

# Answer
This is probably an *awful* approach to fitting points and prediction.

There's no reason to expect that a PRNG will do a good job at fitting points. Interpolation is effective because we think that not all curves are equally likely. Some kind of Occam's razor applies: all else being equal, the "simpler" the curve, the more likely that it is as a plausible model.

Thus, linear regression is useful precisely because not all curve shapes are possible; only straight lines. Empirically, straight lines occur more often than crazy-wiggly shapes. Similarly, polynomial regression is useful because a low-order polynomial is more likely than a high-order polynomial.

Now consider the following approach: try to fit the data you already have to an arbitrary function (with no restrictions on the function or the shape of the curve; all functions are valid/legal models). Well, that'll be an absolutely terrible approach at prediction. You'll be able to find a function that exactly fits all of the data you already have, but (most likely) it will be absolutely useless at predicting values you haven't seen -- it'll be absolutely useless at generalization / prediction. Essentially, you'll have massively overfitted the data set.

Now a PRNG is *designed* to behave like a true-random generator. In other words, all sequences of outputs are supposed to be equally likely (or, at least, you can't tell the difference). Fitting your data to a true-random generator will be useless at prediction/generalization. For the same reason, fitting your data to a PRNG is likely to be useless at prediction/generalization.

You should probably read about the "no free lunch" theorems for machine learning and prediction: https://en.wikipedia.org/wiki/No\_free\_lunch\_theorem, http://www.aihorizon.com/essays/generalai/no\_free\_lunch\_machine\_learning.htm, http://no-free-lunch.org/. To be effective at prediction, the learning technique *must* embed some bias about what hypotheses/models are more likely. A true-random generator has no bias and thus is useless. A PRNG behaves like a true-random generator and thus will probably be useless (or, to the extent it has bias, its bias is towards distributions that are very unlikely to appear in nature).
> 1 votes

---
Tags: algorithms, pseudo-random-generators, random-number-generator
---


# Question
Title: If a language is not Turing reducible to two languages, may it still be Turing reducible to their "union"?
Consider a language $L$ that is undecidable relative to $L\_1$ and is also undecidable relative to $L\_2$. Suppose, however, that there is a "multi"-oracle Turing machine $M$ that can query both the $L\_1$ oracle as well as the $L\_2$ oracle such that $M$ decides $L$. In other words, $L$ requires both the $L\_1$ and $L\_2$ oracles to be decided, but neither one alone suffices to decide $L$. I would like to come up with such languages $L$, $L\_1$, and $L\_2$. At first, I was hoping that the oracles for the rejecting and the accepting problems for Turing machines together could be queried to decide the halting problem (but neither oracle alone could be used decide it), but that turns out to be a dead end.

Now I'm wondering if I can approach the problem by trying to come up with two languages such that neither is Turing-reducible to the other, but I'm struggling to find examples.

# Answer
> 2 votes
A classical theorem of Sacks states that if $L$ is not computable, then it is almost surely not computable relative to a random oracle. In other words, if $O$ is a random oracle, then the probability that $L$ is computable given $O$ is zero.

Now take your favorite uncomputable $L$, and choose $L\_1,L\_2$ at random among all languages such that $L = L\_1 \Delta L\_2$ (here $\Delta$ is symmetric difference). Individually, $L\_1,L\_2$ are random oracles, and so almost surely $L$ is not computable given just $L\_1$ or just $L\_2$. However, it is clearly computable given both.

Another solution is to take any two incomparable Turing degrees $L\_1,L\_2$ and $L = \\{ 0x : x \in L\_1 \\} \cup \\{ 1x : x \in L\_2 \\}$. The proof then follows practically by definition.

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


# Question
Title: A PDA to recognize the Intersection of two regular languages?
I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages:

> Intersection of L1 and L2

L1 = L (aaa\* bab)
L2 = L (aab\* aba)

I can't tell if this is even possible because I don't see any common string that would be in both languages.

If it is not possible how should I formally state so? I am brand new to PDAs.

# Answer
> 3 votes
If the intersection is empty then you have to show that some PDA accepts the empty language. That doesn't sound too difficult.

More generally, every NFA is secretly a PDA (showing that every regular language is context-free), and so if you can construct an NFA for your language then you can easily convert it to a PDA.

---
Tags: regular-languages, pushdown-automata
---


# Question
Title: Determining whether a relation is the "union" of two other relations
Given a relations $P$ and $Q$ on $S$, what are the most efficient algorithms to find whether the relation satisfy the constraints $P \cup Q = S \times S$ and $P \cap Q = \emptyset$?

If it helps, for my application the elements of $S$ are strings. Apologies if my question is not up to standard, this is my first question on Stack Exchange and it's been several years since I've done any formal math.

# Answer
> 1 votes
The following should suffice:

```
for each (x,y) in P:
    if (x,y) in Q, print "nope" and quit
for each (x,y) in Q:
    if (x,y) in P, print "nope" and quit
count the number of pairs in P and Q.
if this sums to |S|^2, output "yup, otherwise output "nope".

```

You could use any method. For instance, you could compute $P \cup Q$ directly, then compute $P \cap Q$ directly (say, using mergesort-like methods), and check that each has the desired value.

All of these will have essentially the same asymptotic running time.

---
Tags: sets
---


# Question
Title: Insertion sort vs Merge sort - memory access
I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not.

According to him, the insertion step in insertion sort requires random access. But can't it be implemented using sequential access in a linked list, going through each element, and as soon as you find that the element of the next node is more than the element you wish to insert, you squeeze that element after the current element (for ascending order list).

He is almost never wrong, but he also doesn't entertain doubts, due to which I'm forced to ask here. Please let me know. Thanks!

# Answer
> 2 votes
The implementation of merge sort that your instructor has in mind accesses memory sequentially, in the sense that merging steps from left to right over the two arrays being merged and the target array as well. Insertion sort has a more complicated memory access pattern.

As you note, if you sort linked lists instead of arrays, insertion sort also conceptually moves from left to right. However, the implementation of linked lists will still do pointer operations that lead to non-sequential memory access.

# Answer
> 1 votes
You are over-thinking things here. By 'random access', you professor merely means that insertion requires access to an arbitrary location in the already-sorted sublist, regardless of how that location is found. By contrast, with merge sort, each element move during a merge pass requires only that some element be taken off of the front of one list and moved to the end of another list; no other list locations need be considered.

---
Tags: algorithms, sorting, memory-access, mergesort
---


# Question
Title: Do reductions form a total binary relation?
I was wondering if the following property holds true:

$$\forall A, B \subseteq \Sigma^\* : A \leq\_m B \lor B \leq\_m A$$

And the same for Turing reductions

$$\forall A, B \subseteq \Sigma^\* : A \leq\_T B \lor B \leq\_T A$$

# Answer
> 5 votes
If $A \not \preceq B$ and $B \not \preceq A$ then we say that $A,B$ are *incomparable* with respect to the order $\preceq$.

As mentioned in the comments, the halting problem and its complement are incomparable with respect to many-one reductions; indeed, one of the reasons behind considering many-one reductions is that they make such distinctions possible.

One can also construct sets $A,B$ which are incomparable with respect to Turing reductions. These are known as *incomparable Turing degrees*. One way to do it is using diagonalization, as we explain below.

It will be somewhat less confusing to construct Boolean functions $\alpha,\beta$ instead of sets $A,B$. The construction will proceed in infinitely many steps. At step $i$ we will have finite partial functions $\alpha\_i,\beta\_i$, which extend the functions $\alpha\_{i-1},\beta\_{i-1}$ from the previous step. Initially, $\alpha\_0 = \beta\_0$.

At step $2i$, we make sure that the $i$th program cannot compute $\alpha$ given $\beta$. We start by picking the minimal input $x$ not in the support of $\alpha\_i$. For each complete function $\beta'$ extending $\beta\_i$, we run program $i$ on input $x$ with $\beta'$ as oracle. If none of these runs ever terminates, we set $\alpha\_{i+1}(x)$ arbitrarily, and continue to the next step. Otherwise, suppose that program $i$ terminates on input $x$ with $\beta'$ as oracle. Since the program terminates, it only accesses the oracle at a finite number of places. We extend $\beta\_i$ to $\beta\_{i+1}$ so that it agrees with $\beta'$ on this finite number of places. Finally, we set $\alpha\_{i+1}(x)$ to disagree with the output of program $i$ on input $x$ and oracle $\beta'$.

At step $2i+1$ we make sure that the $i$th program cannot compute $\beta$ given $\alpha$, in the same way. Our construction ensures that $\alpha = \bigcup\_i \alpha\_i$ and $\beta = \bigcup\_i \beta\_i$ are total functions that correspond to incomparable Turing degrees.

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


# Question
Title: Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items
I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items are distinct, so they have different properties.

The query must only contain AND logical operators. For example, a query can be property A and NOT property B and property C.

Obviously, I must construct a query that has an intersection of properties such that the search space is reduced by $1/3$. Is there a faster way of doing this than simply doing a $O(2^k)$ brute force algorithm?

# Answer
> 2 votes
You are missing a condition – no two elements have exactly the same set of properties. Consider for example the extreme case in which no item has any properties – any query will get either all elements or none of them. We can also assume that $n\>1$.

A simple iterative procedure constructs such a query. Let the properties be $P\_1,\ldots,P\_k$.

* Let $x\_1$ be the setting of $P\_1$ which maximizes the number of elements satisfying $P\_1=x\_1$.
* Let $x\_2$ be the setting of $P\_2$ which maximizes the number of elements satisfying $P\_1=x\_1$ and $P\_2=x\_2$.
* And so on.

Denote by $N\_i$ the number of elements satisfying $P\_1=x\_1,\ldots,P\_i=x\_i$. Thus $N\_0 = n$ and $N\_k = 1$ (by the missing condition). Let $i\>0$ bet the minimal index such that $N\_i \< 2n/3$ (such an index exists since $N\_k=1 \< 2n/3$). Thus $N\_{i-1} \geq 2n/3$. By construction, $N\_i \geq N\_{i-1}/2 \geq n/3$. It follows that $n/3 \leq N\_i \< 2n/3$.

---
Tags: algorithms, combinatorics, sets
---


# Question
Title: about the complexity of recursive sequence
If i have a recursive sequence $a\_1=4$ and $a\_{n}=a\_{n-1}^{2}-2$ in $\mathbb{Z}\_{M\_{n}}$ where $M\_n=2^n-1$

how i can calculate the complexity time of this sequence ? if we put it in the loop for n-1 iteration .

pseudocode :

S=4; i=2;

While($i\<n$,

$S=S^2-2 (\mod M\_n)$

If( S==0 then Break\[\]);

);

im not sure that overall complexity is $O(log^3(M\_n))$

# Answer
I calculated the first few values of your sequence: $$ 4,2,2,2,2,2,2,2,2,\ldots $$ Indeed, $a\_2 = 4^2-2 \bmod{2^2-1} = 14 \bmod{3} = 2$, and henceforward we have $a\_{n-1}^2-2 = 2^2-2 = 2$ and so $a\_n = 2$.
> 3 votes

---
Tags: complexity-theory, time-complexity, runtime-analysis
---


# Question
Title: How hard is finding the discrete logarithm?
The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.

I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what approaches (i.e. algorithms) are the best for accomplishing this task.

The wikipedia link above doesn't really give very concrete runtimes. I'm hoping for something more like what the best known methods are for finding such.

# Answer
> 23 votes
**Short answer.**
If we formulate an appropriate *decision problem* version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes **NP**, **coNP**, and **BQP**.

**A decision problem version of Discrete Log.**
The discrete logarithm problem is most often formulated as a *function problem*, mapping tuples of integers to another integer. That formulation of the problem is incompatible with the complexity classes **P**, **BPP**, **NP**, and so forth which people prefer to consider, which concern only *decision* (yes/no) problems. We may consider a decision problem version of the discrete log problem which is effectively equivalent:

> *Discrete Log (Decision Problem).* Given a prime $N$, a generator $a \in \mathbb Z\_N^\times$ of the multiplicative units modulo $N$, an integer $0 \< c \< N$, and an upper bound $b \in \mathbb N$, determine whether there exists $1 \leqslant L \leqslant b$ such that $a^L \equiv c \pmod{N}$.

This would allow us to actually compute log<sub>*a*</sub>(*c*) modulo *N* by binary search, if we could efficiently solve it. We may then ask to which complexity classes this problem belongs. Note that we've phrased it as a promise problem: we can extend it to a decision problem by suspending the requirements that $N$ be prime and $a \in \mathbb Z\_N^\times$ a generator, but adding the condition that these restrictions hold for any 'YES' instance of the problem.

**Discrete Log is in BQP.**
Using Shor's algorithm for computing the discrete logarithm (*Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer*), we may easily contain **Discrete Log** in **BQP**. (To test whether or not $a \in \mathbb Z\_N^\times$ actually is a generator, we may use Shor's order-finding algorithm in the same paper, which is the basis for the discrete logarithm algorithm, to find the order of $a$ and compare it against $N-1$.)

**Discrete Log is in NP ∩ coNP.**
If it is actually the case that $N$ is prime and $a \in \mathbb Z\_N^\times$ is a generator, a sufficient certificate either for a 'YES' or a 'NO' instance of the decision problem is the unique integer $0 \leqslant L \< N-1$ such that $a^L \equiv c \pmod{N}$. So it suffices to show that we can certify whether or not the conditions on $a$ and $N$ hold. Following Brassard's *A note on the complexity of cryptography*, if it is *both* the case that $N$ is prime and $a \in \mathbb Z\_N^\times$ is a generator, then it is the case that $$ r^{N-1} \equiv 1 \\!\\!\\!\\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \\!\\!\\!\\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$} $$ by definition (using the fact that $\mathbb Z\_N^\times$ has order $N-1$).

* A certificate that the constraints on $N$ and $a$ both hold would be a list of the prime factors $q\_1, q\_2, \ldots$ dividing $N-1$, which will allow us to test the above congruence constraints. (We can test whether each $q\_j$ is prime using AKS test if we wish, and test that these are all of the prime factors of $N-1$ by attempting to find the prime-power factorization of $N-1$ with only those primes.)
* A certificate that one of the constraints on $N$ or $a$ fail would be an integer $q$ which divides $N-1$, such that $a^{(N-1)/q} \equiv 1 \pmod{N}$. It isn't necessary to test $q$ for primeness in this case; it immediately implies that the order of $a$ is less than $N-1$, and so it is a generator of the multiplicative group only if $N$ fails to be prime.

# Answer
> 4 votes
In the general and worst-case scenarios Niel de Beaudrap's answer is correct, to the best of my knowledge.

However in the case that $N-1$ has only small prime factors, the Pohlig-Hellman algorithm finds the logarithm in $O(log^2(N))$ time. Therefore, for this case, the Discrete Log problem is in $P$. As such, when a cryptographic protocol depends on the hardness of this problem, it is important to choose the modulus, $N$, such that $N-1$ has large prime factors.

# Answer
> -1 votes
since $|a|=O(N)$, then $b=O(N)$. (Meaning brute-force is in EXP.)

For a non-deterministic machine, there is a polynomial witness since we can do modular exponentiation in P. (I.e. the problem is in $NP$.)

The theory that discrete logarithms are in $NP$ but not $P$ is the basis of modern cryptography, but that's obviously unproven.

Shor's method (linked to on that wikipedia page) runs in polynomial time on a quantum computer.

---
Tags: algorithms, complexity-theory, time-complexity, discrete-mathematics
---


# Question
Title: Why is backpropagation called backwards propagation of error, when it back propagates error derivatives?
Wikipedia says:

> The backward propagation of errors or backpropagation, is a common method of training artificial neural networks and used in conjunction with an optimization method such as gradient descent.

Ultimately, backward propagation is used to get the partial derivates of the weights and biases of the network, so that gradient descent can be used.

This means you end up with $\frac{\partial TotalError}{\partial weight\_i}$ and $\frac{\partial TotalError}{\partial bias\_i}$ at the end, for all weights and biases, but you don't actualy end up with any sort of specific error value for the neurons.

With that in mind, why is it called back propagation of errors, instead of backpropagation of error gradient or something similar?

# Answer
It's actually the error for the neurons. The actual reason for derivation is this:

* You find an error then you find the derivative of the error according to some differential equation.
* Gradients you obtain using that derivative is basically to determine how much one single neuron in the network made mistake. Gradient at one neuron means if you update the weights or biases according to that you decrease the error network makes.

Backpropagation is the mathematical system for assesing how much one neuron made mistake so you can improve it. Definition is true in that sense.
> 2 votes

---
Tags: neural-networks
---


# Question
Title: Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable?
I have proven that it is **not** regular and context free. But is it Turing decidable/recognizable? I'm thinking yes, as I am able to write a Java program for it, and by the Church-Turing thesis the power of the Turing Machine and a Java program is equivalent (or am I wrong here?).

# Answer
You are right about the fact that being able to conceive a Java program for doing the job, then there must exist a Turing machine which will also recognize that language. However, you don't need the Church-Turing thesis to confirm your statement. You need something weaker, namely the fact that both Java and TM are acceptable programming systems and hence they are isomorphic (ie. they compute the same set of partial functions) by Roger's theorem.

The main point is that Roger's theorem is a theorem and Church-Turing thesis is not proven.
> 1 votes

# Answer
Sure, the turing machine would count the a's, than it will calculate 2^n and then count the b's
> 0 votes

---
Tags: computability, undecidability
---


# Question
Title: Closure of regular languages are closed under certain cut operations
Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define

$$f(L) = \\{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\\}$$

For example, if $f(n) = n$ this is just the "halving" operation, and regular languages are well known to be closed under this -- just simultaneously walk forwards and backwards (where the backwards walk tries all possible paths, like in the subset construction).

According to HMU, regular languages are also closed under taking the functions $2n, n^2, 2^n$. It is easy to see for $2n$, or any linear function for that matter - just walked backwards with whatever the speed. How can this be done for $n^2$ or $2^n$? It doesn't seem feasible to just increase the speed, since that would require remembering the number of steps taken so far.

Also, can we adapt the solution to get some general sufficient conditions on which $f$ has this property? (I doubt there are necessary and sufficient conditions, but would love to be proved wrong)

# Answer
> 4 votes
Take a DFA $\langle Q,q\_0,F,\delta \rangle$ for $L$. For every state $q \in Q$, it is known that $$ N\_q = \\{ n : \delta(q,x) \in F \text{ for some $|x|=n$} \\} $$ is an eventually periodic set. In these terms, we have $$ f(L) = \bigcup\_{q \in Q} \\{ w : \delta(q\_0,w) = q \text{ and } |w|+f(|w|) \in N\_q\\}. $$ A few simple arguments show that $f$ is *admissible* (the set of regular languages is closed under $f$) if for every modulus $m$, there is a DFA $\langle Q',q'\_0,\delta' \rangle$ over the alphabet $\\{0\\}$ which "computes" $|w|+f(|w|) \bmod m$, in the sense that on input $0^n$, you can recover $n+f(n) \bmod{m}$ from $\delta'(q'\_0,0^n)$. This, in turn, happens if for every modulus $m$, the function mapping $n$ to $n+f(n) \bmod{m}$ is eventually periodic. Since $n \bmod{m}$ itself is periodic, we conclude that:

> A function $f$ is admissible iff for all $m$, the function $\psi\_{f,m}(n) = f(n) \bmod{m}$ is eventually periodic.

The Chinese Remainder Theorem shows that it suffices to consider values of $m$ which are prime powers.

All polynomials are clearly admissible: if $f$ is a polynomial, then $\psi\_{f,m}$ has period $m$. Exponential functions $a^n$ are also admissible: if $m=p^k$, then either $p \mid a$, in which case $\psi\_{f,m}$ is eventually zero, or $(p,a)=1$, in which case Euler's formula shows that $\psi\_{f,m}$ has period $\varphi(m)$.

I'm not sure if the set of admissible functions can be characterized any further – this is an interesting research direction.

---
Tags: regular-languages
---


# Question
Title: Constructing logical sentences that involve negative integers over the nonnegative integers
Consider the following statement:

> If $x$ and $y$ are integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

I'd like to build a sentence for this statement in the model of $(\mathbb{N}, +)$, where $\mathbb{N}$ is the set of nonnegative integers and $+$ is just the relation (where here I define a relation as a mapping from tuples to a boolean value): $\\{(a,b,c): a + b = c\\}$. By "sentence", I mean a logical formula with no free variables.

How can I write the highlighted statement in terms of the given model if variables in this model can only take only take on nonnegative integers? It seems at best I can only build a sentence in this model for the following statement:

> If $x$ and $y$ are *nonnegative* integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

Or is it possible to define negative quantities in the model of $(\mathbb{N}, +)$?

# Answer
Any integer $x \in \mathbb{Z}$ can be expressed in the form $x = x\_+ - x\_-$ where $x\_+ \in \mathbb{N}$ and $x\_- \in \mathbb{N}$ (i.e., every integer can be expressed as the difference of two natural numbers; and conversely, the difference of any two natural numbers is always an integer).

Try using that to formulate your statement. You'll need to work out how to define the $\le$ operator, but that's a separate issue.
> 0 votes

---
Tags: logic, first-order-logic
---


# Question
Title: Is it possible to use machine learning to interpret a programming language and guess it's output
I know machine learning can make some predictions. With enough input data and example output data a machine can accept an image as input and determine that the image is likely a "flower" (output).

Could the same method apply to an interpretive programming language? Let's say Python for example. The inputs on every "line" of python would be existing memory and the new "line" of syntax. So if x = 2 (some data in ram as say CPython would set it instead of the actual syntax). Our new line of syntax is `x + 2`. The output is `4` (perhaps the updated ram state could also be considered an output). With enough sample input and output could a machine learning algorithm effectively "invent" it's own python interpreter? Perhaps our invented interpreter would determine there is a 98% chance that 2 + 2 results in 4.

A few people are asking why would anyone would want to do this. Curiosity mostly and certainly reading too much Godel, Escher, Bach. I think it's interesting because:

* Perhaps it would find novel optimizations. Computers already find new strategies in chess. Why not interpreters or compilers?
* The idea of a programming language interpreting syntax probabilistically, that doesn't even have to follow strict rules, is interesting. Can we go from `2 + 2 = 4` to `2 plus 2 equal four` to `Please add two and two`.
* Making a really horrible python interpreter would be funny.

# Answer
> 4 votes
I doubt it. That requires learning a pretty complex function, which seems beyond the reach of current machine learning techniques.

But there's probably no reason to use machine learning for this, as we already know how to program an interpreter, and that will be more effective than using machine learning.

# Answer
> 1 votes
I haven't seen anybody ever trying this.

However, Karparthy tried if Character-RNNs can create new code in The Unreasonable Effectiveness of Recurrent Neural Networks:

```
/*
 * Increment the size file of the new incorrect UI_FILTER group information
 * of the size generatively.
 */
static int indicate_policy(void)
{
  int error;
  if (fd == MARN_EPT) {
    /*
     * The kernel blank will coeld it to userspace.
     */
    if (ss->segment < mem_total)
      unblock_graph_and_set_blocked();
    else
      ret = 1;
    goto bail;
  }
  segaddr = in_SB(in.addr);
  selector = seg / 16;
  setup_works = true;
  for (i = 0; i < blocks; i++) {
    seq = buf[i++];
    bpf = bd->bd.next + i * search;
    if (fd) {
      current = blocked;
    }
  }
  rw->name = "Getjbbregs";
  bprm_self_clearl(&iv->version);
  regs->new = blocks[(BPF_STATS << info->historidac)] | PFMR_CLOBATHINC_SECONDS << 12;
  return segtable;
}

```

Now, without executing it, what does the code do?

Did you have problems with that? Well, in that case I hope it helped to illustrate how difficult the task is you're asking. And I didn't even start with ioccc (e.g. this gem and more)

Having said that, I guess it could work for simple instances pretty well. Just finding `print("[whatever]")` could work. But I don't thing it would understand loops. Yet alone variable assignments. But I didn't try.

---
Tags: machine-learning
---


title: Very divisible subsets

text:
# Question
Title: Very divisible subsets
I've recently come across the following problem.

We're given up to $10^4$ distinct positive integers $a\_1,\dots , a\_n$, each of them below $10^6$. Let's call a subset $S \subset \\{a\_1,\dots,a\_n\\}$ a very divisible subset if any number in this subset divides the product of other numbers in this subset.

The task is to find the largest such subset. It is guaranteed that there is at least one with at least $3$ elements. If there are several such subsets we can output any of them. For example if we're given numbers $2, 3, 4, 5, 7, 8, 9, 10$ then the algorithm might output $2, 4, 5, 8, 10$.

It's neither a homework nor an ongoing contest. I'm just curious how to solve it. Unfortunarely for now i can't see any solution better than brute force through all the subsets. And such approach is unfeasible under given limitations. Any ideas will be highly appreciated. Thanks in advance.

P.S. Here's an original statement of this problem: https://www.e-olymp.com/en/problems/7331

# Answer
> 2 votes
Here is an idea. By factoring the numbers, we are reduced to the following problem:

> Given a set $S$ of vectors in $\mathbb{N}^k$, find a maximum-size subset $T \subseteq S$ such that for every $x \in T$ we have $x \leq \sum\_{y \in T - x} y$ (pointwise).

If there is some $x \in S$ and some coordinate $i \in \[k\]$ such that $x\_i \> \sum\_{y \in S - x} y\_i$, then clearly $x\_i$ cannot belong to any such set $T$, and we can simply remove it. Keep removing such elements from $S$ until no such elements exist. Then for every $x \in S$ and $i \in \[k\]$ it is the case that $x\_i \leq \sum\_{y \in S-x} y\_i$, and so the filtered set $S$ is the unique solution.

Let me demonstrate this solution using your example $2,3,4,5,7,8,9,10$. Only 4 prime factors appear here (2,3,5,7), and converting $2^x3^y5^z7^w$ to the vector $xyzw$, we obtain the following vectors: $$ \begin{align\*} 2 &= 1000 \\ 3 &= 0100 \\ 4 &= 2000 \\ 5 &= 0010 \\ 7 &= 0001 \\ 8 &= 3000 \\ 9 &= 0200 \\ 10 &= 1010 \end{align\*} $$

We remove 7 due to the 4th coordinate. We then remove 9 due to the 2nd coordinate. We then remove 3 due to the 2nd coordinate. We cannot remove any more numbers, and so are left with the answer 2,4,5,8,10.

The challenge is to implement this greedy algorithm efficiently, which you can do by maintaining the sum of all elements left in the set, and using several priority queues (though perhaps there is a better solution). Details left to you.

# Answer
> 1 votes
The good news is: The greedy algorithm works. Start with T = S. Then as long as T has an element that doesn't divide the product of all other elements, remove it. I first had read the problem as "each number in T divides the product of two other numbers in T" - the greedy algorithm works in that case as well.

Just an addition to Juval's algorithm to keep the time polynomial in the problem size, for example if we are given just three 100 digit numbers:

If you had very large numbers, then the factoring could take excessive time. If you have n numbers, and n' of them have large factors that you can't find easily, then you can calculate about ($n'^2 / 2)$ gcd's and find which have common factors. If $a\_i$ has a large unknown prime factor and no other $a\_j$ has a common divisor then you can throw $a\_i$ out without bothering to actually find the factor.

---
Tags: number-theory
---


title: Hardness of Approximation of MAX-3SAT

text:
# Question
Title: Hardness of Approximation of MAX-3SAT
This is probably a duplicate of this question, but I need a somewhat blunter answer. Let's say I have a polynomial time algorithm that finds an assignment that satisfies more than $\frac{7}{8}$ of the clauses of a satisfiable 3SAT instance. Do I collect my million dollars from the Clay Institute for proving $P=NP$?

# Answer
> 3 votes
I believe that Håstad gave such an algorithm in 2000, see On bounded occurrence constraint satisfaction. His algorithm is stated for instances where each variable occurs at most $B$ times, and the advantage over 7/8 depends on $B$. The running time, however, seems not to depend on $B$.

In order to prove that P=NP, you need to find an algorithm which, given a satisfiable instance, satisfies at least $7/8+\epsilon$ clauses, for some *constant* $\epsilon\>0$. This will enable you to distinguish between satisfiable instances and instances which are at most $7/8+\epsilon/2$ satisfiable, which is NP-hard as my answer to the question you mention shows.

---
Tags: satisfiability
---


# Question
Title: How to calculate run time of insertion sort and Merge sort?
I am currently studying computer science and we were given assignment to implement two algorithm(Insertion sort and Merge sort) and run them in order to track their running times across different input arrays. And ask us to do: "Your task is to run each algorithm 3 times on 5 input arrays with 5, 50, 500, 5000, and 50000 random integers each, and report their running times both as a table and "n vs. time" plots"

I have already implemented algorithm but I am not sure how to calculate runtime of both algorithm. Any help would be appreciated. Thank you.

# Answer
> 0 votes
In sorting algorithms you can count the number of comparsions and consider it as run time of worst case. Just add one static counter in your code it will reflect the time complexity in a better form. Otherwise the general approach of calculating run time works fine always. Most language has a function that gives system time.

---
Tags: algorithms
---


# Question
Title: Calculate the size of Logical and Physical Address
Suppose a logical address space of 32 pages of 2048 words. There are 64 frames in the main memory. According to given information calculate the various parameters related to paging.

Calculate the size of Logical Address? Calculate the size of Physical Address?

# Answer
> 2 votes
We know

logical address contains: page number and page offset (page size)

physical address contains : number of frames and frame size

---

Logical address space contains 32 pages and to represent 32 pages we need 5 bits $2^5=32$.

Each page contains 2048 words therefore the offset or "d" parameter can be represented by 11 bits $2^{11}=2048$.

So total number of bits to represent logical address : $5+11=16$ bits.

---

Similarly 64 frames can be represented by 6 bits $2^6=64$ and offset will be same (because page size is equal to frame size) i.e. 11 bits. The total number of bits to represent physical address: $6+11=17$ bits.

---
Tags: cpu, paging
---


title: Sort write-once array

text:
# Question
Title: Sort write-once array
You have to sort a given array (assuming nothing more than the elements are totally ordered) which is write once read many (WORM) in constant space i.e using a constant number of variables.

So, my naive approach was to fix the position of one element at a time. But in what order? If I do it first to last then the information of the element of the index where I placed the first element is lost. So, if I start with the first element, then try to fix the element where the first element was placed, I will eventually run into problem because I'll have to remember the relative order of the current element and the elements sorted till now.

It seems doable but I can't really figure it out. For now, I don't care about running time.

# Answer
Here is an approach which is not too efficient in terms of running time. Suppose your array has length $n$, say $A\[1\],\ldots,A\[n\]$. Given an element of your array, you can determine its rank (i.e., the value of $k$ such that it is the $k$th smallest element), so we can assume that the array contains a permutation of $1,\ldots,n$.

Consider now the cycle induce by the element $A\[1\]$, that is, write $$ A\[1\] = x\_1, A\[x\_1\] = x\_2, \ldots, A\[x\_\ell\] = 1. $$ If $x\_1 = 1$ then $1$ is already at the correct place. Otherwise, you want to modify the array so that: $$ A\[1\] = 1, A\[x\_1\] = x\_1, \ldots, A\[x\_\ell\] = x\_\ell. $$ Hopefully you can see how to do it using constant space.

Go over all the elements $A\[1\],\ldots,A\[n\]$ in this way. Elements which you have already sorted (for example, $x\_1$ in the example above) will already be at the correct place, so you will only modify each cycle once. In other words, you will only write to each position once.
> 2 votes

---
Tags: algorithms, sorting
---


title: Is every acyclic graph 2-colorable?

text:
# Question
Title: Is every acyclic graph 2-colorable?
Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with color $Y$. Is the reasoning valid?

# Answer
> 2 votes
An acyclic graph, usually known as a *forest*, is a collection of disjoint trees. It is only a tree if it is connected. Since trees are 2-colorable (for the same reason you mention), it follows that forests are also 2-colorable.

It is also possible to reduce the general case to the connected case: given a forest, you can join the different connected components to form a tree. The resulting tree is 2-colorable, and the same 2-coloring is also valid for the original forest.

---
Tags: graphs, colorings
---