# Question
Title: If L is regular, so is L2 (proof using closure properties)
I've got a question that asks me to explain how if a language L is regular, then so is:

$M=\\{s \in \\{a, b\\}^\* |\ \exists\ t \in L\ such\ that\ |s|\_a = |t|\_a\\}$

I believe I would have to get M into the form: $M=\\{a^i |\ i\geq0\\}$ since we know that any equation of that form is regular, but I'm not quite sure how to go about that using closure properties.

# Answer
> 3 votes
Here are several possible ways of proving that if $L$ is regular then so is $M$.

**Method 1**

Show first that the language $K = \\{ a^r : |s|\_a=r \text{ for some } s \in M \\}$. You can obtain $K$ from $L$ by deleting all letters other than $a$. Then show that $M$ is regular by "undeleting" all letters other than $a$.

**Method 2**

Construct an NFA for $M$ directly, given an NFA for $L$. At each step, the new NFA accepts non-$a$ letters gratuitously, both in the input and in its simulation of the NFA for $L$. It also reads $a$, but then must also simulate an $a$ transition on the NFA for $L$. Finally, it accepts whenever it can get the NFA for $L$ to be at an accepting state.

**Method 3**

Parikh's theorem shows that $K$ (defined in Method 1) is eventually periodic. That is, for some integers $m,p$ and sets $A \subseteq \\{0,\ldots,m\\}$, $B \subseteq \\{0,\ldots,r-1\\}$ we have $$ K = \\{ a^i : i \in A \\} \cup \\{ a^{m+rj+i} : j \geq 0, i \in B \\}. $$ Given this, we can construct a DFA for $M$ directly (exercise).

---
Tags: formal-languages, regular-languages
---


# Question
Title: What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?
I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant when we say that we can construct a circuit which 'simultaneously computes' all partial derivatives of a function. Does simultaneously computing mean that there are multiple output gates or does it mean that every partial derivative is computed by some sub-circuit of of $D$.

# Answer
> 1 votes
The new circuit will have multiple output gates, each one computing a different partial derivative. See for example Definition 2.1 and the ensuing proof in lecture notes of Wigderson.

---
Tags: complexity-theory, circuits
---


title: Are Random Forests Turing-Complete?

text:
# Question
Title: Are Random Forests Turing-Complete?
Is the random forests algorithm Turing-complete? As in, can any algorithm be represented by a given "tree" in the forest?

# Answer
Random forests are useful only for inputs of a given size, so they are not really eligible for Turing-completeness. However, any function on inputs of size $n$ can be computed by a decision tree, so in that sense the model is complete (though in practice we limit the depth of the trees).
> 2 votes

# Answer
No, they're not Turing complete. The handle inputs of a fixed size. Also, they can't loop, so will always halt -- it follows that they don't have the ability to perform Turing-complete computation.
> 5 votes

---
Tags: algorithms, randomized-algorithms, turing-completeness
---


# Question
Title: Proving a certain superset the halting language is not recursive
Let $\Sigma =\\{ 0, 1\\}$. Let $val:\Sigma^\* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L\_{halt} = \\{\langle M\rangle \langle w\rangle \mid M $ halts on $w \\}$.

I define the following language:

$L=\\{ x \mid x\neq x^R \wedge (x\in L\_1 \vee x\in L\_2 \vee x\in L\_3)\\}$

where:

* $L\_1=\\{ x \mid x\in L\_{halt} \wedge x^R \in L\_{halt} \wedge val(x)\<val(x^R) \\}$
* $L\_2=\\{ x \mid x\notin L\_{halt} \wedge x^R \notin L\_{halt} \wedge val(x)\<val(x^R) \\}$
* $L\_3=\\{ x \mid x\in L\_{halt} \wedge x^R \notin L\_{halt} \\}$ (in this language there is no requirement on $val$ function)

That is, a string in $L$ has 3 options how to look like.

Intuitively I can feel that $L\notin R$, but I do not know how to approach a formal proof for this.

I tried using a reduction $L\_{halt} \leq L$, and then since $L\_{halt}\notin R$ I can deduce that $L\notin R$, but I could not find a reduction that will work.

The closest thing I could come up with is using an intermediate reduction, first defining $L\_{halt}^{'} =\\{ 1 x 0 \mid x \in L\_{halt} \\}$ and then easily $L\_{halt} \leq L\_{halt}^{'}$ and all I have to do is $L\_{halt}^{'} \leq L$, so my idea for reduction was given $x=1y0$ then $f(x)=y$ (the reduction returns $y$), but then this reduction has a problem if $y\notin L\_{halt}$ and $y^R\notin L\_{halt}$ then it might be possible that $val(y) \< val(y^R)$ and then $f(x)=y\in L$ but $y\notin L\_{halt}^{'}$...

I'm kind of stuck at how my reduction should work?

I'm also assuming that any string from $\Sigma^\*$ is a possible encoding of a $\<M\>\<w\>$, that is I cannot assume something about the encoding itself and also every word is a possible encoding of $\langle M\rangle \langle w\rangle$...

# Answer
> -1 votes
Main idea of the proof is since $L$ is kind of superset of $L\_{halt}$ we select reduction in such a way that we always deal with only that subset of $L$ which resembles $L\_{halt}$.

First let us choose any encoding such that if $\langle M,w \rangle \in L\_{halt}$ then $\langle M,w \rangle^R \not\in L\_{halt}$. $L\_{halt}$ is undecidable in every reasonable encoding so this is okay. Also this will be true for most of the encodings if we include $\langle \rangle$ also in the encoding. (Reverse will be $\rangle w^R, M^R \langle$). Also we should have $val(\langle) \> val(\rangle)$. I assume that $val$ is calculated as a number with base $|\Gamma|$ where $\Gamma$ is the tape alphabet. In the question decimal base is mentioned, which means the same. We need to add extra 4 bits (= 1 decimal digit) in each cell if we do not have enough space for new symbols.

For this encoding we can have an identity reduction for valid input of the form $\langle M,w \rangle$. For invalid input not of the form $\langle M,w \rangle$ we shall reduce the input to $\langle\epsilon,\epsilon\rangle$ which does not belong to $L$. Let us call this reduction $f$. We assume that in our encoding $\langle\epsilon,\epsilon\rangle \not\in L\_{halt}$.

We can now easily prove $x \in L\_{halt}$ if and only if $f(x) \in L$.

($\Rightarrow$)
Let $x = \langle M,w \rangle \in L\_{halt}$.
Then clearly $val(x) \> val(x ^R)$.
And $\langle M,w \rangle^R \not\in L\_{halt}$.
Therefore $\langle M,w \rangle \in L\_3$ and hence $\langle M,w \rangle \in L$ as naturally $x \neq x^R$, Symbols $\langle,\rangle$ ensures that $x \neq x^R$.

($\Leftarrow$)

Note it $f(x) = \langle \epsilon, \epsilon \rangle$ then it does not belong to $L$. So take the other valid cases.

Let $f(x)= y =\langle M,w \rangle \in L$.
Then $\langle M,w \rangle \in L\_3$, as $val(y) \> val(y^R)$.
This gives us $\langle M,w \rangle \in L\_{halt}$ straight away.

The idea of this proof holds even if we are given a specific encoding for $L$ as well.

1) If the encoding for $L$ is such that we do not have begin symbol $\langle$ and end symbol $\rangle$. Also assume $x\_{reject}$ is a string such that $x\_{reject} \not\in L$. We can easily find such a string as $L \neq \Sigma^\*$. In this case the strings got by reduction will not be necessarily in $L\_3$. We also assume our encoding of turing machines is such that we can find a string $\alpha$ such that $0^\*\alpha$ is never a proper prefix.

To always get strings in $L\_3$ we define the reduction as follows. All invalid input strings which are not of the form $\langle M,w \rangle$ are reduced to $x\_{reject}$, and all valid input strings which are of the form $\langle M,w \rangle$ are reduced to $\langle M',w\alpha^R0^{|M'|+1}\rangle$. $M'$ will remove suffix $\alpha^R0^\*$ and then behave as $M$.

With this reduction the proof given above can be modified slightly to prove that $L$ is undecidable.

If the encoding for $L$ is such that $\langle$ and $\rangle$ are always included and $val(\langle) \< val(\rangle)$ then in the reductions given above we will always get strings from set $L\_1$ and $L\_2$. In this case by using $\alpha^R0^\*$ suffix it is easier to get reduced strings from set $L\_2$. Then it is better to reduce language $\overline{L\_{halt}}$ which is also undecidable to $L$ to prove undecidability of $L$.

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


# Question
Title: How can I show that the Cook-Levin theorem does not relativize?
The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) :

> Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to $A$.

What I tried was, take $A$ to be the oracle to halting problem and let $L=\\{1^n | \\;\exists \\; \langle M,w \rangle \\; \text{s.t.} \\; |\langle M,w \rangle|=n \\; \text{ and Turing machine M halts on w} \\} $.
With this assignment I ensure $L \in NP^{A}$ and $L$ is not polynomial reducible to 3SAT if oracle is *not* provided to the machine carrying out reduction. Although to map an instance $1^n$ I would have to search through $2^n$ strings even if oracle is provided to the reduction machine. But this does not seem like a proof for absence of polynomial reduction in this case.
Is there a way to prove it using the same example ? Is there a simpler example ?

# Answer
Please refer Does Cook Levin Theorem relativize?.

Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability.

In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ and $U\_B$ such that $U\_B \in NP^B$ and $U\_B \not\in P^B$, thus proving that there are oracles $B$ for which $P^B \neq NP^B$.

We shall modify the $U\_B$ and $B$ to $U\_{B'}$ and $B'$ such that we get a new language that cannot be reduced to 3SAT even if there is availability of $B'$ as an oracle.

First assume that we can pad every $3SAT$ boolean instance $\phi$ to $\phi'$ with some additional dummy 3CNF expressions such that $|\phi'|$ is odd and they are equivalent, i.e., $\phi$ is satisfiable iff $\phi'$ is satisfiable. We can do it in $n+O(1)$ time and with $O(1)$ padding, but even if it takes polynomial time and extra polynomial padding it does not matter.

Now we need to combine the $B$ and $3SAT$ to $B'$ somehow so that BGS theorem still holds but additionally $3SAT \in P^{B'}$. So we do something like the following.

$U\_{B'} = \\{1^n \ \ |\ \ \exists x \in B, $ such that $|x| = 1^{2n}\\}$ and

$B' = B'\_{constructed} \ \cup \\{\phi \ \ |\ \ \phi \in 3SAT $ and $ |\phi| $ is odd $\\}$.

Now we shall construct $B'\_{constructed}$ according to the theorem such that if the deterministic machine $M\_i^{B'}$ for input $1^n$ ($n$ is determined as in theorem) asks the oracle $B'$ a query of odd length we check if it is in $3SAT$ and answer correctly but if it asks a query of even length we proceed according to the construction, that is, answering correctly if it is already in the table, otherwise answer no every time. Then since we are running for $1^n$ we flip the answers at $2n$ length so that $M\_i^{B'}$ does not decide $U\_{B'}$.

We can prove similarly as in the BGS theorem that for this $B'$ and $U\_{B'}$ too, we have $U\_{B'} \in NP^{B'}$ and $U\_{B'} \not\in P^{B'}$.

$U\_{B'} \in NP^{B'}$ is easy to prove. We construct a non-deterministic Turing Machine which for input $1^n$ creates non-deterministic branches that runs for $2n$ steps to generate a different $2n$-length string and then asks oracle $B'$ if the $2n$-length string is in $B'$, and if the answer is yes it accepts $1^n$ else it rejects $1^n$. This construction shows that $U\_{B'} \in NP^{B'}$.

$U\_{B'} \not\in P^{B'}$ can be proved with the help of diagonalization argument. Basically it is different from every $L(M\_i^{B'})$ for every oracle Turing Machine that have $B'$ as an oracle. This is because of how we construct $B'\_{constructed}$.

Now we shall prove by contradiction that there does not exist a reduction from $U\_{B'}$ to $3SAT$ even with the availability of oracle $B'$.

Assume there is a reduction using oracle $B'$, i.e., $U\_{B'} \leq^{B'}\_P 3SAT$.

That means we can reduce a string of the form $1^n$ to a 3SAT instance $\phi$ using a polynomial-time deterministic machine which uses $B'$ as oracle.

We can now describe a deterministic TM $M^{B'}$ which will decide strings $U\_{B'}$ in polynomial time using $B'$ as an oracle. First this machine reduces the input $1^n$ to a 3SAT-instance $\phi$ using $B'$ as an oracle. This can be done because we have the reduction above. Then if $\phi$ is not odd length $M^{B'}$ will pad it to make $\phi'$ which is odd length. Next, it will give this $\phi'$ to oracle $B'$ and get the answer yes/no. It will accept if the answer is yes and reject if the answer is no.

This machine is deterministically polynomial and uses oracle $B'$.

Thus we have proved that $U\_{B'} \in P^{B'}$, a **contradiction**.

Therefore $U\_{B'} \not\leq^{B'}\_P 3SAT$.
> 12 votes

---
Tags: complexity-theory, np, nondeterminism, oracle-machines, relativization
---


title: "Not in big theta but in big O"

text:
# Question
Title: "Not in big theta but in big O"
Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me to prove that f(x) isn't in big omega of g(x) but I really don't know where to start with this one. I tried to look for scenerios where there wouldn't be any positive constants. However, I had trouble doing that.

# Answer
One of the answers to your question: $f(n) = n$, and $g(n) = n^2$.

Then $f(n) = O(g(n))$ but not $\Theta(g(n))$. This is because $n^2$ is an upper bound on $n$ , for all $n \geq 0$, but it is not tight (actually we only need the inequality to be true for $n \> N$ for some $N$, by the definition of $O()$).

By saying that the bound is not tight, what we mean is that we do not have $cn^2 \leq n \leq c'n^2$, for large enough $n$'s (it should hold for all $n \> N'$ for some $N'$ by the definition of $\Theta()$ if $n$ were $\Theta(n^2)$). Also $c$ and $c'$ are positive here and the following discussion.

Since $n^2$ is upper bound on $n$ it is easy to get $n \leq c'n^2$ part. But we can never get to the $cn^2 \leq n$ part. Even if we take $c$ very small,say 0.01 in the picture, at $n \> 100$ it will not remain smaller. So we can never have $n$ between $cn^2$ and $c'n^2$ for all values $n\>N'$. This is because we will always find some big number where $c'n^2$ will be above $n$.

$O()$ is just an upper bound, where as $\Theta()$ is a tight bound. Also if we have $f(n) = o(g(n))$ then the bound in not tight yet it is an upper bound. Then $g(n)$ is a loose upper bound. If $f(n) = o(g(n))$ then any such pair of $f(n)$ and $g(n)$ will satisfy the condition of your question.
> 7 votes

# Answer
It is easy to find functions with tight upper and lower bounds which have *no* simultaneous bounds, like:

$\begin{align} f(n) = \begin{cases} n & \text{if } n \text{ is even} \\ n^2 & \text{if } n \text{ is odd} \end{cases} \end{align}$

It is easy to see that $f(n) = O(n^2)$ and $f(n) = \Omega(n)$, none of which can be improved; and that there is no $\alpha$ such that $f(n) = \Theta(n^\alpha)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Linear equation solving with special sparse coefficient matrix
Given a linear equation system of $n$ equations with unknowns $a\_1,a\_2,...,a\_n\in \[0,1\]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ zero terms in each matrix row), what is the fastest way (in terms of time complexity) to solve such a system.

I know that simple equation-by-equation reduction will result in $\mathcal{O}(n^2)$ if I'm not mistaken. But is there a faster way of solving it (ideally linear in $n$, e.g. $\mathcal{O}(kn)$)? Because I'm new to the subject of computational linear algebra I have no idea wether or not this is possible.

EDIT: I should also say that either the coefficients in an equation are all the same and add up to zero (so they basically describe an arithmetic mean, for example $\frac{1}{2}a\_1+\frac{1}{2}a\_2-a\_3=0$) OR the equation consists of a single variable and a value (e.g. $a\_5=1$).

# Answer
> 3 votes
There are iterative methods in which each iteration takes time $O(nnz)$, where $nnz$ is the number of non-zero entries. See for example Chapter 4 of Saad's lecture notes. For the state-of-the-art, consult Section 5 of Lee and Sidford (2013). For special types of matrices, see Lee, Peng and Spielman (2016).

---
Tags: algorithms, time-complexity, linear-algebra, numerical-algorithms
---


title: how to generate/read a glyph in ocr?

text:
# Question
Title: how to generate/read a glyph in ocr?
I have been practicing with some Machine Learning algorithms for OCR, but I have a doubt about the glyph concept. For example in the UCI repository:

https://archive.ics.uci.edu/ml/machine-learning-databases/letter-recognition/letter-recognition.names

where it says:

```
4. Relevant Information:

   The objective is to identify each of a large number of black-and-white
   rectangular pixel displays as one of the 26 capital letters in the English
   alphabet.  The character images were based on 20 different fonts and each
   letter within these 20 fonts was randomly distorted to produce a file of
   20,000 unique stimuli.  Each stimulus was converted into 16 primitive
   numerical attributes (statistical moments and edge counts) which were then
   scaled to fit into a range of integer values from 0 through 15.  We
   typically train on the first 16000 items and then use the resulting model
   to predict the letter category for the remaining 4000.  See the article
   cited above for more details.

```

and when I see the file letterdata.csv I find something like this:

```
"letter","xbox","ybox","width","height","onpix","xbar","ybar","x2bar","y2bar","xybar","x2ybar","xy2bar","xedge","xedgey","yedge","yedgex"
"T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8

```

So for what I have read this first line refers to the character T that has certain values according to the attributes:

```
7. Attribute Information:
     1. lettr   capital letter  (26 values from A to Z)
     2. x-box   horizontal position of box  (integer)
     3. y-box   vertical position of box    (integer)
     4. width   width of box            (integer)
     5. high    height of box           (integer)
     6. onpix   total # on pixels       (integer)
     7. x-bar   mean x of on pixels in box  (integer)
     8. y-bar   mean y of on pixels in box  (integer)
     9. x2bar   mean x variance         (integer)
    10. y2bar   mean y variance         (integer)
    11. xybar   mean x y correlation        (integer)
    12. x2ybr   mean of x * x * y       (integer)
    13. xy2br   mean of x * y * y       (integer)
    14. x-ege   mean edge count left to right   (integer)
    15. xegvy   correlation of x-ege with y (integer)
    16. y-ege   mean edge count bottom to top   (integer)
    17. yegvx   correlation of y-ege with x (integer)

```

while some attributes are easy to understand, but I have a problem to visualice this in my head; I mean a glyph it is not like a grid in which a handwritten character is put on? something like this:

\]

but where is the individual pixel data on the dataset letterdata.csv that I mentioned at the beginning of the question? Also and for not opening another question thread, how these glyphs are generated and if there is a glyph reader in which I can put the data like: "T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8 and I can visualize the corresponding letter. Any help?

# Answer
> 2 votes
This is addressed in the *relevant information* you quoted, specifically in the following sentence:

> Each stimulus was converted into 16 primitive numerical attributes (statistical moments and edge counts) which were then scaled to fit into a range of integer values from 0 through 15.

Many machine learning algorithms won't be successful with the raw raster data, instead requiring features such as the 16 "primitive numerical attributes" mentioned above. (Deep learning algorithms should work correctly with the raster data, though.)

Computing these numerical attributed is a one-way process: you cannot recover the glyph from its statistics. We compute these statistics since we think they are the salient features which distinguish one letter from another.

---
Tags: ocr
---


# Question
Title: DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$
I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in words and I feel the description is incorrect.

The first language reads like this:

> $L\_1=\\{w:(n\_a(w)–n\_b(w)) \text{mod 3} \> 0 \\}$

The solution goes like this:

* DFA states have meaning.
* There will be three states counting number of a's occurred till now in the input string mod 3. Similarly there will be three states counting number of b's occurred till now in the input string mod 3.
* So total states will be $3\times 3=9$. Say state $01$ means $n\_a(w)\text{mod 3}=0$ and $n\_b(w)\text{mod 3}=1$.
* The slides say that states with label $10, 20, 01$ and $21$ will be final states.

**Q.1** However, I feel state $01$ should not be the final state, simply because $0-1\text{ mod 3}=-1\text{mod 3}=-1\not\gt0$. Am I correct?

Similarly, the second language is:

> $L\_2=\\{w:(n\_a(w)+2n\_b(w))\text{mod 3}\<2\\}$

The slide explains this as follows:

* The DFA will have similar states and transitions as in case of above language, with below changes.
* As $b$'s go in the sequence: 0, 1, 2, 0, ...; $2b$ goes in the sequence: 0, 2, 1, 0,...
* So change the label 01 with 02, 11 with 12, 21 with 22, 02 with 01, 12 with 11 and 22 with 21.
* Change accepting states in above language to 00, 10 and 01.

**Q.2** However I feel this is incorrect interpretation of the language. I interpreted as follows:

```
State n_a(w)    n_b (w) (n_a(w)+2n_b(w))mod 3       Is final state?
00    0         0       (0+0) mod 3 = 0 < 2         Yes
01    0         1       (0+2) mod 3 = 2             No
02    0         2       (0+4) mod 3 = 1 < 2         Yes
10    1         0       (1+0) mod 3 = 1 < 2         Yes
11    1         1       (1+2) mod 3 = 0 < 2         Yes
12    1         2       (1+4) mod 3 = 2             No
20    2         0       (2+0) mod 3 = 2             No
21    2         1       (2+2) mod 3 = 1 < 2         Yes
22    2         2       (2+4) mod 3 = 0 < 2         Yes

```

where `n_a(w)` means "*number of a's encountered so far in the input string*" and `n_b(w)` means "*number of b's encountered so far in the input string*"

Am I correct with this?

# Answer
As Yuval noted, you can do this with three states. Since the behavior of the FA depends only on $(n\_a(w)-n\_b(w)) \mod 3$, if we interpret the question as $(.)\mod 3$ can be only 0, 1, or 2, then we'll have three states: $q\_0, q\_1, q\_2$ where $q\_i$ will represent having seen a number of $a$s and $b$s so far such that $(n\_a(w)-n\_b(w))\mod 3 = i$.

Now consider being in state $q\_0$. That means that $(n\_a(w)-n\_b(w))\mod 3 = 0$, so if we encounter an $a$, we'll have seen input $w'=wa$ and so we'll then have $n\_a(w')=n\_a(w)+1$ so $n\_a(w')-n\_b(w')=n\_a(w)-n\_b(w)+1\equiv (0+1)\pmod 3$ so we'll change to state $q\_1$. In a similar way, seeing a $b$ will take us from $q\_0$ to $q\_2$. Doing this for the other two states will yield the transition table $$ \begin{array}{c|cc} & a & b \\ \hline q\_0 & q\_1 & q\_2 \\ q\_1 & q\_2 & q\_0 \\ q\_2 & q\_0 & q\_1 \end{array} $$ with start state $q\_0$ and final states $q\_0$ and $q\_1$.
> 1 votes

# Answer
For your first question, the mod 3 operation is understood to yield a result in 0,1,2. If you consider instead the "arithmetic modulo" operation which returns a signed result, then the language $L\_1$ is no longer regular.

For your second question, $a-b$ and $a+2b$ are the same modulo 3. Draw your own conclusions.

For both questions, the minimal DFAs actually consist of only 3 states.
> 0 votes

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


# Question
Title: How might I express a sequence of operations in formal terms?
I want to be able to represent a set of operations in sequential order such that they will represent what is traditionally called a "function" (which is not always the mathematical definition of a "function"). However, I'm trying to define more primitive terms:

* **object** \- Anything that can be manipulated throughout the course of a program; that is, they can be read and set.
    + **place** \- A container that can hold value. (e.g. variables)
    + **value** \- A value. (e.g. 2+2 is a value but not a variable).
* **procedure** \- A sequence of operations.

I want to be able to define *procedure* in more definite terms. Note that I will be starting without the definitions of *operations*, as I want to be able to define basic operations as procedures.

I know that I may want to introduce the sense of "time" and "space" for programs, time being necessary due to the definition of "sequence" that I put forth. Is there a better way to define it? Is there already work out there that explores this?

**How would you formally define a procedure or operation at its most basic level?**

# Answer
Take a look at Gurevich's abstract state machines. See also the abstract state machine homepage. A key paper is Gurevich's Sequential Abstract State Machines Capture Sequential Algorithms.
> 1 votes

---
Tags: programming-languages, semantics, formal-methods
---


title: Confusion about compiler and assembler

text:
# Question
Title: Confusion about compiler and assembler
I have two questions.

1. After compilation of any C program result is assembly language code which should depend on processor. So my question is: how do different computers with different processor types, for example Intel i3,i5,i7 etc., are able to run the same software, for example, media-player, browser, etc.?
(I guess strangely it depends on Operating System) and on that software site they do not ask for processor type.
2. Do programs interact with any part of operating system for conversion of assembly code to machine code?

# Answer
Regarding your first question, the Core i3, Core i5 and Core i7 share the same instruction set, apart for a few marginal instructions. In particular, there is backward compatibility, and so code that works for Core i3 would also work for Core i5 and Core i7 (unless it uses some undocumented behaviours, or specifically tests for the processor version). However, to get superior performance, optimizers need to know the exact target processor, and special instructions should be utilized. This can be handled in at least two ways: (1) crucial functions could have several versions, depending on the processor (either completely different versions or just different optimizing parameters), (2) libraries are used which implement the previous approach.

Regarding your second question, the operating system is usually relied on for handling files, so yes, even an assembler needs to interact with the operating system.
> 9 votes

# Answer
A compiler and an assembler are both programs that (roughly stated) translate human readable source code (C or assembly language) to machine code (or some code not designed for human consumption). There really is not much of a difference, except for the source language. You might as well call both "compiler".

Compilers for higher level languages (like C) have to figure out what the code is supposed to do, and translate it into a very different language (e.g. machine language for your machine), there is a lot of leeway to do so. For low level languages, like assembly language (which is close to the machine language) there is very little wiggle room, if any.

The resulting machine code is binary representation of the instructions to be executed. This has to be packaged up for other tools to process this in several ways (e.g. to *link* several separately compiled pieces to create an executable program), and for this apart from the instructions themselves other information is added (addresses inside the code where a function starts, places where an external function is called to patch it's address in, ...). The resulting program file contains the instructions to be executed, but also information needed to control it's placing in memory, where it should start execution, and others. A file containing this is handled by the operating system to load instructions into memory and start running. There are several different such formats. Each operating system uses it's own format. Many such formats are defined so they work for different instruction sets/formats (they aren't intrinsecally machine-dependent), some operating systems (like Linux) are even able to handle several formats (to be able to run e.g. executables for other systems).
> 3 votes

# Answer
1. Ok regarding the first question, nowadays we don't have a separate compiler and assembler they both are bind into one single unit. So we combinely call it as compiler and this compiler is divided into two parts front end and back end(assembler i.e platform dependent). Every machine has its own assembler i.e intel will have its own, motorola will have its own and so on. Now these assembler design depends on the instruction sets of the machines. For example intel may have opcode of "00FC10" for add but any other machine may have different opcode for add so to overcome this problem we have machine specific assembler. Regarding i3,i5 and i7, intel processors are backward compatible i.e anything that you generate for i3 that will definitely run on other high end intel processors. And moreover no organisation would make something which will harm their previous efforts.

2. Now coming to your second question, O.S may or may not be involved in this conversion it all depends on your code that is to be translated. Now if you have more system calls and more of relocation things than O.S will be needed very frequently.

Hope this will help.
> 1 votes

---
Tags: operating-systems, compilers
---


title: Properties of coset

text:
# Question
Title: Properties of coset
Let $C$ be a linear code with minimum distance $2k$. I want to show that there is a coset of $C$ that contains at least two vectors of weight $k$.

Firstly, it holds that the minimum distance of the code is equal to the lowest non-zero weight of a codeword. So this means that the weights of the codewords are greater than these of the elements of the coset of $C$, right?

Solving the system $Hx=0$, where $H$ is the parity matrix, we can find the coset of $C$, right?

But in this case we don't have a generator matrix of the dual code. How can we get information about the parity matrix?

Or how else can we get information about the coset of $C$?

# Answer
Let $v$ be *any* vector of weight $k$. Then all vectors in $C+v$ have weight at least $k$. Furthermore, if $w \in C$ is any vector of weight *exactly* $2k$ (such a vector must exist since the minimal weight of $C$ is $2k$) and $v$ is a "subset" of $w$ then $v,w+v \in C+v$ are two vectors of weight exactly $k$.
> 2 votes

---
Tags: linear-algebra, coding-theory
---


# Question
Title: Time complexity of comparing two $N \times N$ Matrices?
So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of operations is less than $O(N^{2})$ or is the matrix comparison lower bound also $\Omega(N^2)$?

# Answer
> 4 votes
A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they are equal. That takes time $\Omega(M)$.

---
Tags: complexity-theory, time-complexity, lower-bounds, matrices
---


# Question
Title: Language where pumping does not work -- Pumping lemma
I understand that the length of y must be greater than 0 but I do not understand how to show B\_2 is a regular language or why pumping up does not work in part ii.

# Answer
> 0 votes
For (i), the pumping lemma says there is *some* such division, not that any division you happen to choose has to work. For (ii), because any string starting and ending in $0$ is in the language ($x$ is anything whatsoever in it's definition).

---
Tags: pumping-lemma
---


# Question
Title: Running-time cost of Tweaked Nested Loop
I understand that the following nested for-loop:

```
for(i=0; i<n/2; i++)
    for(j=0; j<n/2; j++)
         print(j)

```

has the runtime complexity of

which has a simplifed complexity of

but what is the resulting complexity of making j bound to i/2 in the inner loop? For instance:

```
for(i=0; i<n/2; i++)
    for(j=0; j<i/2; j++)
         print(j)

```

Would this be

?

# Answer
> 1 votes
The complexity would be

$$\sum\_{i = 0}^{n/2-1} \sum\_{j = 0}^{i/2-1} 1\\,,$$ which is $O(n^2)$.

# Answer
> 0 votes
It is also $O(n^2)$. Because

```
for(i=0; i<n/2; i++)
    for(j=0; j<i/2; j++)
         print(j)

```

is asymptotically equivalent to

```
for(i=0; i<n; i++)
    for(j=0; j<i; j++)
         print(j)

```

which calls the print statement $n \times (n - 1)$ many times.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Examples of specialized instructions of assembly language not available in compilers?
In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language.

> Another major advantage of assembly language is the ability to exploit specialized instructions - for example, string copy or pattern-matching instructions. Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction. However, the programmer who wrote the loop can replace it easily with a single instruction.

How can a loop be replaced by string copy or pattern matching? Can somebody give an example on specialized instructions that are not available in a high-level language and how a specialized instruction can replace a loop?

# Answer
> 4 votes
Some machines have complex processor instructions that can do the same job as a loop with a simple body. For example, x86 processors have an instruction `scasb` instruction that searches for a byte value; the C `strlen` function, which searches for a null byte and can be written in C as

```
while (*p != 0) p++;

```

can be written in x86 assembly as

```
repne scasb

```

Another example is bit counting. Many processors have instructions to do things like finding the number of bits that are set in a word, or finding the index of the lowest-order set bit in a word. However, most programming languages have no operator or function for that, so the programmer has to write a loop like

```
bit_count = 0;
while (n != 0) {
    if (n & 1) ++bit_count;
    n = n >> 1;
}

```

whereas recent x86\_64 processors have an instruction for that:

```
popcnt

```

Some C compilers provide extensions to the standard language that give access to this instruction (and compile to a loop-based form if such an instruction doesn't exist on the target machine).

Yet another example is instructions that accelerate some common cryptographic algorithms (e.g. AES-NI on recent x86 processors). Unlike the previous two, this example is of interest only to the rarefied world of cryptography implementers, so compiler writers are less inclined to provide ways to generate those instructions apart from inline assembly.

Your textbook seems somewhat dated to me. Loop instructions hard-wired in processors are a very CISC feature that most modern processors don't have, the notable exception being the x86 architecture where it is implemented in microcode for backward compatibility. Compilers have become better at understanding what a piece of code including a simple loop does, and converting them to optimized machine instructions. The statement “Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction” is not always true for 21st century compilers. It is *sometimes* true; for example I can't seem to get GCC to recognize my naive `popcnt` implementation above.

# Answer
> 4 votes
Counting bits set, Brian Kernighan's way

```
unsigned int v; // count bits set (1)
unsigned int c; // result
for (c = 0; v; ++c)
{
  v &= v - 1;
}

```

This code becomes `popcnt`

# Answer
> 0 votes
Modern CPUs include specialized instructions (mostly privileged ones, i.e., only the operating system kernel is allowed to use them) to do Input/Output, messing with table pages, flushing the various CPU caches, return from an interrupt. The operations invoked make no sense in regular code (and wouldn't be allowed in the first place), so they aren't in the repertoire of instructions emitted by the compiler. To allow their use, most C compilers (C is often used to write operating system kernels) have ways to include assembly snippets inline.

If you look at the discussions on languages in StackOverflow, you'll see that the compiler is required to emit code that just behaves "as if" it was doing the operations written by the programmer. The instructions used to "fake" what you request can very well be quite different from what you'd expect, computations might be done in wildly different orders, useless computation silently elided, and so on. In the case of C, the compiler is allowed to use knowledge of what standard library functions do, and replace e.g. `printf("%s", string)` with `puts(string)`, and `sin(x) * sin(x) + cos(x) * cos(x)` with `1.0`. Take some (not too complex) code, and ask to compile with maximal optimization to assembly language (ask for debugging, that'll add some comments that help referencing back to the source). You'll be surprised.

---
Tags: programming-languages, compilers
---


# Question
Title: Decidability of dependent typing on primitive recursive languages
With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this: would an implementation of dependent typing for a primitive recursive language(not Turing-complete) be guaranteed to halt? Thanks!

# Answer
Not only is the answer to this question yes, but this is exactly the strategy that modern implementations like Coq and Agda take! To be precise, the type checker has to preform evaluation when deciding definitional equality so it would, if given the right language, be possible to write an infinite loop and ask whether a term was definitionally equal to another term. Because of the way we define definitional equality in most cases, this demands evaluation.

The *calculus of constructions* (CoC) is actually strongly normalizing. Type checking of CoC is decidable and requires no termination checking. But to make this theory more useful, we add the ability to define inductive types and recursions over them. This way, we get the *calculus of inductive constructions* (CIC), which Coq is based on. You can view this as a means of adding terms to our language which add computational content that would otherwise not be present.

Note than many inductive types can already be represented in CoC without the aid of CIC, but CoC cannot represent everything CIC can. Coq and Agda both have termination checkers which accept all primitive recursive functions, *and* both also allow encoding the Ackermann function. You can see more about this in a question I once asked here on a characterization of the class of primitive recursive functions.

Good refrences on Agda's termination checker are

There is also a lot of work on *sized types* to provide an alternative to termination checking as well as some work on abstract interpretation based solutions. Currently however, checking for a generalization (see Foetus) of primitive recursion is as far as the state of the art in mainstream implementations goes — at least as far as I am aware.
> 6 votes

# Answer
Primitive recursive isn't actually an interesting threshold here. As long as the language only allows terminating programs, and type equality is defined by normal form equality, dependent typing can be checked statically.

The gist of the proof is obvious: if the language only allows terminating programs, then all computations on types terminate, because they're computations in the language. However, there are some subtleties.

One subtlety is that type checking must be defined by syntactic means. If type checking is semantic, all bets are off. For example, consider the program $\lambda x:\mathbb{N}^k. (\mathtt{if} \\: D(x) \\: \mathtt{then} \\: \texttt{"bad"} \\: \mathtt{else} \\: 0)\_{\mathbb{N}}$ where $D$ is a Diophantine equation. If $D$ has no solution then this program will never try to pass off the string $\texttt{"bad"}$ as an integer (type $\mathbb{N}$). If the typing rules are defined by the runtime semantics, this program is well-typed iff the Diophantine equation has no solution, which is an undecidable problem. If the typing rules follow a classic syntactic presentation, then this program is ill-typed, because it requires both branches of the `if` statement to be well-typed.

Another subtlety lies in the definition of type equality. Type checking requires not only calculating types, but also checking if they're equal (or more generally if one type is a subtype of another). Even if type checking follows syntactic rules, equality could bring back undecidable semantics — consider $(\texttt{make\_array}(n,0))\_{\texttt{array}(m)}$ (make an array of length $n$, of type array of length $m$): the compiler must be able to decide whether $m$ and $n$ are equal. If $m$ and $n$ are themselves calculated, say as solutions of a Diophantine equation, this could be undecidable.

A third subtlety is that decidable type *checking* is a lot more common than decidable type *inference*. Type checking may require a lot of type annotations in the code. Without type annotations, ever relatively weak type systems are undecidable; for example System F, which only has terms depending on types and not types depending on terms, has undecidable type inference (whereas type checking is easy).

All these subtleties are really manifestations of the same underlying concern. If the type checker only needs to calculate terms, then as long as the language only allows terminating programs, the type checker itself is terminating. But if the type system allows expressing more than what the language itself can do — by adding a level of quantification (the property must hold for all possible executions, not just for one execution), by adding a way to compare the semantics of two expressions, or by adding a step of partial reconstruction — then the type system pretty quickly becomes undecidable. The most basic dependently typed version of the lambda calculus, $\lambda\Pi$ in the lambda cube, has a syntactic type system, as do its extensions the calculus of constructions which is the basis of program/proof languages such as Coq.

Languages with a terminating dependent type system generally cope with this problem by requiring sufficient type annotations, and defining a syntactic type system. If the programmer doesn't give enough information to let the compiler conclude that the program is well-typed, then the program is rejected, even though there's still some possibility that it would execute without any type error. This is particularly important in languages where programs are proofs, and well-typed programs are correct proofs.
> 4 votes

---
Tags: computability, undecidability, type-checking, dependent-types, primitive-recursion
---


# Question
Title: On submultisets of given cardinality and bound that sum to $0$
Given multiset of integers $a\_1,\dots,a\_{m}$ where $|a\_i|\leq\log^cm$ for some $c\in\Bbb R^+$. Is it $\mathsf{NP}$-complete to decide if there is a cardinality $\lceil m^\alpha\rceil$ submultiset for some $\alpha\in(0,1)$ whose sum is $0$?

How many submultisets of such cardinality can we expect to have vanishing sum?

# Answer
> 1 votes
Assuming that $c$ is fixed, this can be solved using dynamic programming in quasipolynomial time. We compute inductively *all* possible sums of all submultisets of size $k$ for all $k \leq \lceil m^\alpha \rceil$. Since each such sum is at most $2^{\log^c m} \lceil m^\alpha \rceil$, this algorithm runs in $O(2^{O(\log^c m)} m^{O(1)})$, which is quasipolynomial. This suggests that the problem is not NP-hard.

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: Determine if there are 2 integers in 2 separate arrays add up to a given number
If I'm given 2 unsorted arrays A and B of n distinct integers and an integer z, how can I determine if there exists an integer in A and an integer in B that add up to z with an expected run time of O(n)?

I'm pretty sure that I would have to use a hash table(s) of some sort since I'm dealing with expected run time but I'm not sure how the algorithm would work.

Any help would be really appreciated! Thanks!

# Answer
Insert the elements of the first array into a hashset `S` by subtracting from `z`. I.e., if `3` is an element of the first array, instert `z - 3` into `S`. Then for each element in the second array, check if `z - element` is already in `S`. This procedure is O(n).
> 2 votes

# Answer
Your best bet will be to sort the arrays one in ascending order and other in descending order and then do a linear scan. The complexity of the algorithm will be $O(n \log n)$.

You might not be able to do better than this in the general case.

If the arrays are sorted we will be able to do it in linear time, by traversing one array in the ascending order and other in the descending order. There is no need to actually reverse one of the arrays.
> 0 votes

---
Tags: algorithms, hash-tables
---


# Question
Title: Why Is KD-Tree-based Nearest Neighbor Exponential in K?
I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why.

What I'm looking for is a solid runtime-complexity analysis which explains this aspect of the problem.

# Answer
> 2 votes
kNN tends to be exponential because the search space increases with $2^k$. Imagine you partition the space around your search point into quadrants. For k=1 you just have to search two 'quadrants' (higher and lower values), for k=2 it's 4 quadrants, for k=3 it's 8 quadrants, i.e. exponential growth of search space. That is what the kD-tree suffers from, because it has to search $2^k$ sub-branches.

Other trees perform much better, for example the CoverTree. I also found that the PH-Tree works quite well, it seems to consistently take twice as long as the CoverTree for datasets between k=8 and k=27 (I didn't have datasets with higher k).

---
Tags: algorithm-analysis, data-structures, search-trees, nearest-neighbour, search
---


# Question
Title: Context sensitive grammar for an odd number of copies of the same word
Let $L = \\{ w^m \mid m = 2k +1, k \ge 1 \\}$. Please give some idea to write a Context sensitive grammar for $L$. Will it be like $L' = \\{www \mid w \in \\{a, b\\}^\*$? Then for each $w$ we have to introduce one nonterminal?

# Answer
> 2 votes
If $w$ in the question is a fixed string (or even from a finite set of finite strings) then you can write a context free grammar for it. Every context free grammar is also a context sensitive grammar. So following grammar suffices.

$S \rightarrow wwS\ |\ w$

If $w \in \\{a,b\\}^\*$ then you will have to do something like (https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language) but with variable number of copies.

Also first try to solve for $L = \\{w^m\ \ | \ \ m\geq 1, w \in \\{a,b\\}^\*\\}$.

It should be possible to write a context-sensitive-grammar because we can easily construct a linear bounded automata. Write $1^m$ non-deterministically in a separate track, copy it as $0^m$, $1^m$, $0^m$ through out the tape in that track, and then check it all contain the same copy of $w$ in the input track. (note you can also ensure odd number of copies here). Also note that even though we may not go right or left of input, we can still use different tracks by choosing a larger tape alphabet.

With this program if we apply the Myhill-Landweber-Kuroda Theorem (A language is accepted by a LBA iff it is context sensitive) we can easily get a context sensitive grammar.

Or taking ideas from the LBA, we can write the CSG in following way: first generate something like $BA\_aA\_bA\_aA\_a...A\_aFDD...$ odd number $...DE$. Then whenever $A\_a$ and $A\_b$ transpose with $D$ they will leave behind $a$ and $b$. $D$ will start transposing only when it is touched by marker $F$ which will turn to $G$ to prevent further transposing. $D$'s will generate $a$' and $b$'s until it toucher $B$. $D$'s will create marker $H$ when they touch $B$, $H$ will move right and when it encounter $A\_a$ or $A\_b$ it will become $I$. $A\_a$'s and $A\_b$'s will have to move to the right of $a$'s and $b$'s to enable $I$ to get to $G$. This $I$ when it touches $G$, it will become $F$ which will start another round of substituting and generating $w$. $A\_a$'s and $A\_b$'s will vanish when they touch $E$. $B$ stands for beginning symbol, $D$ for delimiter symbol, and $E$ for end symbol. So combining all the ideas you get the following (We treat the case $w = \epsilon$ separately):

$S \rightarrow BTFUE \ | \ \epsilon$
$T \rightarrow TA\_a\ |\ TA\_b\ |\ A\_a\ |\ A\_b$
$U \rightarrow UDD\ |\ D$

Above is a straight forward CFG to generate the pattern that we want. Now are CSG rules. I will write the rules as non-contracting grammar.

$FD \rightarrow DG$
$A\_aD \rightarrow DaA\_a$
$A\_bD \rightarrow DbA\_b$
$aD \rightarrow Da$
$bD \rightarrow Db$
$A\_aa \rightarrow aA\_a$
$A\_ab \rightarrow bA\_a$
$A\_bb \rightarrow aA\_b$
$A\_bb \rightarrow bA\_b$
$BD \rightarrow BH$
$Ha \rightarrow aH$
$Hb\rightarrow bH$
$HA\_b\rightarrow A\_bI$
$HA\_a\rightarrow A\_aI$
$IA\_a\rightarrow A\_aI$
$IA\_b\rightarrow A\_bI$

Now a few more rules which do not follow the rules of non-contracting grammar.

$IG \rightarrow F$
$FE \rightarrow E$
$B \rightarrow \epsilon$
$A\_aE \rightarrow E$
$A\_bE \rightarrow E$
$E \rightarrow \epsilon$

If we convert the above grammar to a non-contracting grammer we can then convert it to a CSG for the language. This can be done if we do not use markers ($B$, $E$, $D$, $F$, $G$, $H$, and $I$, markers or their avatars need to be removed by replacing with $\epsilon$ at the end of production) but instead use real symbols for markers. The idea remains the same but the grammar becomes a little more complicated. $D$'s, $E$ and $F$ should stand for last letter of $w$, $B$ should stand for first letter of $w$. The last run should generate $w$ while vanishing $A\_a$ and $A\_b$.

---
Tags: formal-languages, formal-grammars, context-sensitive
---


# Question
Title: Building static hash table with particular collisions
## Is there efficient algorithm to encode keys in hash function with provided collisions?

By efficient I mean with low-*ish* runtime of **lookup operation** (taking constants into account) and **realistic time of finding such function**.
Keys are floating point values - *I can compare them for equality as they are raw, unprocessed. Equality holds, and there are no round-offs*.
If there is better chance for algorithm on integers - I am still interested.
I did not included specific scheme for building perfect hash - it might be the wrong way or different scheme supports such change.

> Let $h(x)$ be hash function (the one to be found)
> $X$ be set of sets of float values that $\forall x \in X\_i, h(x) = c\_i$
> $\forall X\_i, |X\_i| \in \[2, 20\]$
> Let $Y$ be set of float values that there are no collisions (it does not collide with any $X\_i$)

For example, I have set $X = \\{\\{1, 5.5, 24\\}, \\{7, 20\\}\\}$ and the set $Y = \\{4, 25, 31.2, ...\\}$

> $h(1) = h(5.5) = h(24) = c\_0$
> $h(7) = h(20) = c\_1$
> $h(4) = c\_2$
> $h(25) = c\_3$
> $h(31.2) = c\_4$
> $c\_i = c\_j \iff i = j$

$X$ set containts colliding tuples, $Y$ contains values that collide with nothing.
$Y$ is about 85-95% of input, $X$ occupies the rest.
If for example $X$ has values in tuples of multiplicities {3, 5, 2, 2, 20, 14, 3}, this are 49 values, but 7 distinct buckets and Y has 451 elements, these are 451 distinct buckets.
In the hashtable there will be at least 458 buckets (this is perfect, and preffered), but might be a bit bigger up to 1%.
All possible inputs are given, $h(x)$ will never execute for value that was not in the input.
Order of the values from input does not matter, $h(x)$ does not need to preserve order, does not need to be monotone.

### TLDR; Below are previous attempts, some background etc.

---

### Background

In the initial phase I gather data from the device, this phase ends when for given settings I have collected all possible outputs.
This data is collected as floating point numbers. I calculate outputs based on what I get and create mapping of all values to calculated results (this are not continous functions, not piecewise, distinct values with collisions, which are giving the same results).
The callibration phase gives me value to add to calculated results from initial phase.
In the main part I gather data from device, this time with feedback where I need recalculated values in real time.
There are constraints on memory, query time, and I have 10^7 elements, which need to be calculated and then augmented with some value.
The data seems quite random to me (and to DieHard statistical tests also).

---

### Solution attempts

So I thougth about hash function, calculate everything in advance, and make queries easy.
The problem is the normal hashtable does not fit very well because of slowdowns on collisions and when it is perfect it is too big, but collisions if happen on data that gives the same results - fits quite well.
There are a lots of perfect hashing techniques, or methods of collision resolution, but I could not find any materials about picking collisions on my own (this is twice perfect solution, not only I get rid of collisions but also data redundancy vanishes).
So I took CMPH library, and added rejections to collisions to reject if collision is not on the list. The solution is working (on smaller inputs, on real-like I got only two results so far, on relaxed collisions, due to search time).
The probability that I will find perfect function randomly or semirandomly in 10^7 elements is too low to consider.
So I thought about some modified solution, like taking several hash functions, adjusting them, finding similarities - everything is doable on very small sets, then time needed to execute drops like avalanche.
There are addidional test I did, like with Pearson hash, the idea is very cool, but the data size is bigger than 10^5, and values are floats, so it complicates a bit.

---

### Workplace settings

The size of the set is about 10^7 elements, hash table with function $h(x)$ is flat array, that does not support collision resolution (from my perspective, the values from sets $X\_i$ transform into the same output, so are mapped into one element).

---

### Easier, discarded solutions

* The most obvious attempt is to create minimal perfect static hash function from all elements. This solution is discarded because of memory constraints - it does not fit into memory in one piece, redundancy of data.
* Each set $X\_i$ gets own perfect hash function, and upon query I try $Y$ set as the most probable, and then every set $X\_i$ via own hash function until I find the value. (I thought that Yuval Filmus answer is very similar to that approach), which might look a bit like Bloom filter, but the values queried via $h(x)$ are always in the table, and maintaining about 10^6 values more hashes is too slow.

---

### Disaster solutions

* Trees - Many sorts of trees - too slow, way too slow.
* Mixture of hash and tree, Bloomtree(??). I never hoped that it would work but checked it anyway. Of course too slow.

# Answer
> 7 votes
The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \in S$, and put all other $y \in S$ in the table with an entry stating "$x$".

Now take a good hash function $h$, and construct a new one as follows:

* On input $x$, check whether $x \in T$.
* If $x \notin T$, return $h(x)$.
* If $x \in T$, return $h(T\[x\])$.

If $h$ were a uniformly random function, then this would result in a uniformly random function conditioned on your collisions.

There are some optimizations possible here:

* The hash function used to access $T$ can be weak.
* The table $T$ might be too large to fit in the cache, so accessing $T$ might be slow. We can add a Bloom filter that does fit in cache to ameliorate this.

# Answer
> 2 votes
Check perfect hash functions, particularly the first reference given in that Wikipedia page. The general idea (in the case of strings) is to select some character positions that combined give no collisions.

# Answer
> -1 votes
I would try to find a Pearson 256-bit lookup table. My code to generate C code for such a table with your desired properties is at https://github.com/rurban/Perfect-Hash/blob/master/lib/Perfect/Hash/Pearson.pm as described in https://stackoverflow.com/questions/1396697/determining-perfect-hash-lookup-table-for-pearson-hash

```
char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

```

You can tune the cost function to check for your exact wanted collisions. Pearson tables are usually faster even with a few collisions than highly tuned perfect hash tables without any collision because of the zero constant factors, and the lookup table fits nicely into the cache.

However my code is only in slow perl and I just try some random lookup tables until the overall cost function is minimized and some timeout. It would need quite some CPU time to find it. I would write the search function in C.

---
Tags: data-structures, efficiency, hash, hash-tables
---


# Question
Title: Meaning of topological distance between 2 pixels
I came across the notion of topology and topological distance in the context of image processing several times (especially when it came to mathematical morphology). I looked for a not too abstract explanation of "topological distance" but haven't found one yet. Can you please explain (in layaman's terms) the notion of topological distance between 2 pixels? And what's the difference between a euclidean distance and a topological distance in image-processing?

# Answer
> 4 votes
*Nonlinear Signal and Image Processing: Theory, Methods, and Applications* defines topological distance as follows. First, you have to define when two pixels are *neighbors*. The book offers two possibilities:

* The neighbors of a pixel are the 4 "cardinal" pixels around it.
* The neighbors of a pixel are the 8 pixels surrounding it.

This defines a graph (two pixels are connected by an edge if they are neighbors). The *topological distance* between two pixels $p,q$ is then the graph distance between $p$ and $q$.

The first choice above corresponds to $L^1$ ("Manhattan") distance, and the second choice to $L^\infty$ distance. This contrasts with the usual $L^2$ (Euclidean) distance.

---
Tags: image-processing, topology
---


# Question
Title: How many different heaps are there of a given shape?
Let's say we have a tree like this:

Suppose we are given $N$ distinct elements, $N$ being the number of vertices in the tree (in this case, $N=13$).

> In how many ways can we distribute the given $N$ elements in the tree so that it has the max-heap property (any vertex is larger than its children)?

# Answer
> 1 votes
You can compute this recursively as follows. It will be convenient to denote (binary) trees using the following notation: a tree is either a leaf $\ast$ or is formed from two subtrees $(T\_1,T\_2)$. For a tree $T$, let $|T|$ denote the number of vertices in $T$, defined inductively by $|\ast|=1$ and $|(T\_1,T\_2)| = |T\_1|+|T\_2|+1$. Finally, let $N(T)$ denote the number of ways of allocating the integers $1,\ldots,|T|$ to $T$ so that the max-heap property is satisfied.

The base case is $N(\ast)=1$. Now consider a tree $T=(T\_1,T\_2)$. Clearly we must put $|T|$ at the root. Every filling out of the rest of the tree can be described as follows:

* Choosing a set $S\_1$ of integers as labels for $T\_1$. The other elements $S\_2$ function as labels for $T\_2$.
* Arranging $S\_1$ in $T\_1$ in a way satisfying the max-heap property.
* Same for $S\_2$ and $T\_2$.

The number of ways of accomplishing the second bullet is $N(|T\_1|)$, and the number of ways of accomplishing the third bullet is $N(|T\_2|)$; in both cases, the exact contents of $S\_1$ and $S\_2$ are not important. The number of choices in the first bullet is $\binom{|T|-1}{|T\_1|}$, and we conclude that $$ N((T\_1,T\_2)) = \binom{|T\_1|+|T\_2|}{|T\_1|}N(T\_1)N(T\_2), $$ with initial case $N(\ast) = 1$.

Using this formula you can easily compute that for your tree the number of possibilities is $304128$ (I believe).

You can also "unroll" the formula: $$ N(T) = \prod\_{x=(x\_1,x\_2) \in T} \binom{|x\_1|+|x\_2|}{|x\_1|}, $$ where $x$ goes over all internal nodes in $T$. For example, for your tree we get (top to bottom, left to right) $$ \binom{12}{5} \binom{4}{3} \binom{6}{5} \binom{2}{1} \binom{4}{1} \binom{2}{1} = 304128. $$

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


# Question
Title: Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?
Let $S\subseteq \\{0,1\\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ is of minimum size if there is no other $(n,k)$-universal set $S'$ where $|S'|\<|S|$.

is there a known algorithm to construct a $(n,k)$-universal set in general and of (close-to) minimum size in particular?

# Answer
Such constructions appear in papers of Seroussi and Bshouty, Alon, and Naor and Naor. See Bshouty for the latest on this topic.
> 1 votes

---
Tags: algorithms, sets, coding-theory
---


# Question
Title: Proof by Reduction: From Empty Language to Halting Problem on Empty Input
Question: Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}.

Is it possible to show that $H$ is undecidable by reducing $E$ to it? (You can take it as a given that we know $E$ to be undecidable.) If so, show the work. If not, explain why not.

---

My attempt:

Assume that $H$ is decidable (that there exists a Turing Machine that decides $H$) and write a subroutine that maps the input, a machine description $\langle M \rangle$, to some other machine description $\langle N \rangle$, as follows:

def $R(\langle M \rangle)$:
def $N(x)$:
Check whether $M$ accepts no input whatsoever.
If so:
accept and halt on all inputs $x$ (including when $x$ == '')
else, if $M$ accepts some input:
loop forever on all inputs $x$ (including when $x$ == '')
return $\langle N \rangle$

Does the above mapping work?

The subroutine $N(x)$ completely ignores the input $x$, and first checks whether $M$ accepts nothing. IFF so, $N$ will halt on every input $x$. Otherwise, IFF $M$ accepts something, then N will loop forever on all inputs $x$.

So, IFF $\langle N\rangle$ is accepted by a decider Turing Machine as belonging to $H$ (meaning $N$ halts on all inputs, including the empty string), we know $\langle M \rangle$ is accepted as belonging to $E$ (meaning $M$ accepts nothing).

Vice versa: IFF $\langle N \rangle$ is not accepted as belonging to $H$ ($N$ loops forever on all inputs, including the empty string), we know $\langle M \rangle$ is not accepted as belonging to $E$ ($M$ accepts something).

So we have a mapping where $\langle M \rangle$ is an element of $E$ IFF $\langle N \rangle$ is an element of $H$, Thus the mapping works. A decider Turing Machine for $H$ would be able to tell the difference, thereby leading us to be able to decide $E$. But since we know a priori that $E$ is undecidable, $H$ is also undecidable.

---

I'm just getting my feet wet on mapping-reducibility and am unsure whether the above is correct. Any help would be greatly appreciated.

# Answer
See (Blank tape halting problem vs. Emptiness problem ($H\_0$ vs. $E\_{TM}$)).

$H$ is Turing-recognizable but not co-Turing-recognizable.

$E$ is co-Turing-recognizable but not Turing-recognizable.

Their undecidabilities are of different kind. So we need to reduce $M$ to $N$ in such a way that:

$\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

Consider the following reduction from $M$ to $N$. Turing Machine $N$ on empty input will simultaneously generate all input and run $M$ as a universal Turing Machine on that input (again simultaneously) and halts (either accept of reject, doesn't matter) if some simultaneous thread of $M$ accepts on some input. On non-empty input it does not matter what $N$ will do.

We can easily see that if $M$ does not accept anything then it implies $N$ will never halt on empty input. If $M$ accepts something then it implies that $N$ will halt on empty input.

Therefore, $\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

So, we have got a Turing reduction (in fact, a polynomial time Karp reduction).

$E \leq\_M \overline{H}$
> 4 votes

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


title: Turing machine enumerator

text:
# Question
Title: Turing machine enumerator
As the number of Turing Machines is countably, we can create some list of them and number them 1, 2, 3,... Suppose turing machine k computes some function $f\_k$. Is there a turing machine S that can computer $f\_k(k)$?

It seems like there should be, as I am fairly confident that you can write such a program in a turing-complete language. However, I am having a hard time seeing how an $n$ state turing machine (if S is n states) could compute every function computed by an $n^2$ state turing machine, for example.

# Answer
Indeed, there is such a Turing Machine. First, realize that it's computable to convert any integer $k$ into the $k$th Turing Machine description, just by enumerating them. Then, once we have the Turing Machine description, we can use a Universal Turing Machine to compute the function described.

The key is that, while there are less states in the $n$-state machine than in one with $n^2$, any number of additional states can be encoded on the tape of the Turing Machine. So there's no limit to the amount of information we have when computing the $k$th function, since an arbitrary amount of information can be encoded on the tape.
> 1 votes

# Answer
Universal Turing Machine for every model has finite number of states, but it can simulate any Turing Machine with arbitrary large number of states. This is because all the state information of the simulated machine (actually the whole configuration) is kept into the tape.

So it is not the case of how finite states can hold potentially very large information. It is rather how (finite state + infinite tape) holds (very large number of states + infinite tape). Basically there is no problem with storing $(n^2 + \infty)$ information in $(n+\infty)$ space.

And there are two ways to enumerate Turing Machines. Easier way out is just take binary representation of $i$ as Turing Machine $M\_i$. If it is a valid representation it is okay, if it is not, we shall assume it to be a Turing Machine that does not accept any input. The Universal Turing Machine will also honor this fact.

But if we are given a fixed representation and need to generate $i$'th **valid** Turing machine then we need to do it in hard way. We need to generate $\alpha\_{M\_i}$ the representation of $M\_i$ one by one after checking if it is a valid Turing Machine. In this case the Universal Turing Machine will always get a valid representation of a Turing Machine.
> 0 votes

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


# Question
Title: Can I remove left recursion on this grammar
$S \rightarrow Sa \mid S \mid \epsilon$

This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but I think it gives something like that :

$S \rightarrow S'$

$S' \rightarrow aS \mid S' \mid \epsilon $

but this is equivalent to say

$S' \rightarrow aS' \mid S' \mid \epsilon $

Is this the right way to think about this?

# Answer
> 5 votes
Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$.

If you analyze carefully you will see that you are not applying Algorithm 4.19 at all. We are just removing left recursion where we have only immediate left recursion.

Cycles are of the form $A\rightarrow B, B\rightarrow C, C\rightarrow A$. When we remove left recursion in immediate left recursive grammars, we are ignoring $S\rightarrow S$.

Also presence of $\epsilon$ creates problem for the algorithm 4.19 given in the red dragon book (2007 edition), but the method of removing left recursion in immediate left recursive grammar works even in the presence of $\epsilon$.

---
Tags: context-free, formal-grammars, left-recursion
---


# Question
Title: Decomposing a closed walk in a directed graph into cycles
Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a\_1, a\_2, \dots, a\_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of $a\_1$ must equal the target vertex of $a\_k$. My claim is that the multiset of arcs $W'=\\{a\_1, a\_2, \dots, a\_k\\}$ can be partitioned into sets (not multisets) $W'\_1, W'\_2, \dots, W'\_m$ such that the arcs in each $W'\_i$ form a simple cycle.

There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.

I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?

# Answer
The problem stated in the question is also presented in the exercise of the book.

If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.
> 2 votes

# Answer
Construct the graph $G = (V,E)$ such that $\forall \ v \in V, \ \exists \ a\_i \in W$ such that $a\_i$ is incident to $v$ and $E = W$ itself.

This graph $G$ will be connected. Now the multiset $W'$ is an Euler Tour in the graph hence the graph is Eulerian as well. Thus you can use the fact that if we have a cycle $C$ in an Eulerian graph, then the graph remains Eulerian even after removal of $C$.

Reference
> 0 votes

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


# Question
Title: Is the NP-hardness Proof with One Way Implication Correct and Why?
A problem $\Pi$ is NP-hard if I can prove this:

* a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and
* $f(x) \in \Pi\iff$ $x \in \Pi'$.

If I can show only one way implication, that is $f(x) \in \Pi\Rightarrow$ $x \in \Pi'$. Is this reduction known, correct and why?

For me it is correct because, if I had an algorithm for $\Pi$ then I would use it to solve $\Pi'$. Therefore, $\Pi$ is at least as hard as $\Pi'$ then $\Pi$ is NP-hard.

# Answer
> 5 votes
Consider the following two wrong "reductions" from $SAT$ to $L = \\{1\\}$. Let $\phi$ be a $SAT$ instance.

We "reduce" every $\phi$ to 1, i.e. $f(\phi) = 1$. Now we have $\phi \in SAT \Rightarrow 1 \in L$. But $L$ is clearly not NP-hard.

Next we "reduce" every $\phi$ to 0, i.e. $f(\phi) = 0$. Now we have $ 0\in L \Rightarrow \phi \in SAT$. But again $L$ is clearly not NP-hard.

Thus we can see that for a correct reduction we need a proper if and only if condition: $x \in \Pi' \Leftrightarrow f(x) \in \Pi$.

If we have a reduction as above, and if we know that SAT is NP-complete (in other words a hard problem), we have two corollaries from this.

1) Any language can be reduced to SAT. So every language can be reduced to SAT and then to $L$, so $L$ is also NP-complete (now we know that $L$ must also be a hard problem).

2) Any algorithm for membership of $L$ can be used to solve membership to SAT. So if we have an "algorithm" for $L$ then so do we have an "algorithm" for SAT. The algorithm will work this way. From $\phi$ we will construct $f(\phi)$ and then apply our "algorithm" to $f(\phi)$. If answer is YES then $\phi$ is also satisfiable, and if answer is NO then $\phi$ is not satisfiable.

So from 2) we can see that an algorithm for $L$ is applicable for $SAT$. But vice versa is not true. Any algorithm for $SAT$ (polynomial or exponential) can not be used for $L$ using this reduction (there might be other ways but not using just the above reduction). Notice the uncovered region in $L$. So this is what is meant by cryptic comment: solution of $L$ $\Rightarrow$ solution of SAT.

---
Tags: complexity-theory, reductions, proof-techniques
---


# Question
Title: Searching through all program of a stack-based language with little memory
I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.

Given a program fragment, I can determine if it is terminated, and, if not, how many operands it requires. Currently, my search strategy is:

```
 If program is terminated --> test it
 else --> add all programs with one additional operand to the queue

```

However, the queue ends up using too much space. Instead, I'd rather keep the queue small, and find a way to produce all valid programs efficiently (more efficiently than just trying all program text). What is a good strategy to generate all valid programs for a simple stack language?

**UPDATE** The language is guaranteed to halt (and is of course not Turing complete).

**UPDATE:** The approach I am working on is as follows:

1. Observe that, for certain program fragments, nothing that can be appended to them will make them valid
2. Define an ordering over each token that may appear in a program.
3. Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
4. For n = 0 to infinity:
5. Start with a program of n tokens; set each token to the first
6. Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
7. Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
8. Etc. until the last token
9. Increment the last token until the program is valid; test that program
10. On to the next one

# Answer
I can give you a answer about the principles.

Find a computable bijection between your programs and the natural numbers. In essence, you would construct an admissible numbering. Then, you can just iterate over the naturals, compute the program corresponding to each number and perform your checks. You do not need to store any programs but the one under consideration.

The challenge is, of course, to find this bijection; it will depend on your language. If that helps you can relax injectivity; it is not necessary but duplicates will have performance impacts, obviously.

One concrete idea is: represent your language by a context-free grammar. Enumerate left-derivations along rule precedences, going from one program to the next using backtracking. It may even be possible to encode the derivation process in numbers, yielding a mapping as mentioned above.
> 1 votes

---
Tags: programming-languages, search-algorithms, efficiency, enumeration, space-analysis
---


# Question
Title: single agent vs multiple agent reinforcement learning
I am confused about 'single' vs 'multiple' agent reinforcement learning.

Let's say that I have 1 hunter who I am training to hunt 1 static prey, so that only the hunter is moving around. This is definitely single-agent RL.

If there are two hunters and two preys (moving or static), then this becomes multiple agent RL. It would be 'easier' to study two independent hunters, perhaps, but that is a different problem.

My question is this: If there is 1 hunter only, but there are two preys. There is 'some form of interaction' (vaguely defined) between the hunter and prey. Is this still a single-agent RL? or a multiple one?

Is it possible that my agent is the hunter, and all preys be just part of the environment?

# Answer
A key difference between RL and MARL arises when you consider that other agents are strategic and their behaviour is adaptive. Game theoretical concepts are very important within the scope of MARL and bring in a new range of issues. From a single agent perspective, the environment is non-stationary as every strategic agent is changing their policies to best respond to the each other.

A good discussion on the challenges of MARL can be found here: http://busoniu.net/files/papers/marl\_chapter\_springer.pdf

Regarding your question: Yes, you can use a single agent RL as long as the preys are not learning. If you plan to apply RL to every agent (hunter and preys), you will find new issues such as convergence problems, etc. There is a lot of research going on around this. To start I would suggest you have a look at some basic and classic concepts such as Fictitious Play and WoLF (Win or Learn Fast).
> 2 votes

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


# Question
Title: Number of processes needed to maximize CPU utilization under I/O wait conditions
A computer has 2 GB of RAM of which the operating system occupies 256 MB. The processes are all 128 MB (for simplicity) and have the same characteristics. If the goal is 99% CPU utilization, what is the maximum I/O wait that can be tolerated?

My professor said that there are 14 processes in the memory before proceeding with the solution. Why are there 14 processes?

# Answer
> 0 votes
You want all processes to fit in memory. If there are $N$ processes, then together with the OS they take up $256+128N$ megabytes. Since there is only room for $2048$ megabytes, we need $256+128N \leq 2048$. Dividing by $128$, this is $N+2 \leq 16$.

---
Tags: computer-architecture, cpu
---


# Question
Title: premiss of reduction rule (abst) of pure type systems
$$(abst) \\:\frac{\Gamma, x: t\_1 \vdash t\_2: t\_3 \quad \Gamma \vdash (x: t\_1) \to t\_3: s}{\Gamma \vdash (x: t\_1. t\_2): (x: t\_1) \to t\_3}$$

In this rule, why is $(x: t\_1) \to t\_3$ required to be an inhabitant of some sort? Isn't assuming $t\_1: s$ enough?

# Answer
There are two issues here.

The first most obvious one, is that if there is no rule $(s\_1,s\_2,s)$ in the pure type system, then there is no way to get from the hypotheses $$ \Gamma \vdash t\_1:s\_1$$ and $$ \Gamma, x:t\_1\vdash t\_3:s\_2$$ to the conclusion $$ \Gamma\vdash (x:t\_1)\rightarrow t\_3 : s$$ You can see that if there is no such rule, then your hypothesis is insufficient for forming the product type, and therefore you shouldn't be able to form terms of that type. Note that in the Calculus of Constructions, *any* $s\_1, s\_2$ has a corresponding $s$ ($=s\_2$), so the premisses are sufficient for the conclusion in all cases.

Another, more subtle issue is that even the fact $\Gamma, x:t\_1\vdash t\_3:s\_2$ for some $s\_2$ is not obvious from the fact $$\Gamma, x:t\_1\vdash t\_2:t\_3 $$ While actually true, this fact can be subtle to prove depending on how you set up your rules.

The rule you give minimizes the hassle, as it gives you directly the hypothesis that the product is well-formed without having to prove it after the fact.
> 3 votes

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


# Question
Title: Turing machine that can tell if it ends in standard position?
Suppose we have a TM $M$ with alphabet $\\{0, 1 \\}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape is $0$.

Suppose the tape is initially consists of a bunch of $1$s, a $0$, a bunch of $1$s, a $0$, and so on for a finite number of $1$ and then the rest is $0$. $M$ is initially scanning the left-most $1$.

Is there a turing machine that can appended to this guy so that, whenever it is about to halt, it checks if it is in standard position? If it is standard position, then it returns to standard position and halts. If it is not in standard position, then it does not halt. This standard position checking could depend on the turing machine (and probably had to depend on the number of states at least) but should not depend on the initial state of the tape.

I thought that arguing that the TM only has to check $n+1$ $0$s beyond the last $1$ in either direction because the turing machine cannot add a $1$ that far away from the last $1$, but there are counter examples. For example, there is a 3-state machine that, when given the tape 100 _ 1, it changes $1$ to $0$ for "spots" 2-100 and then halts at the second argument.

# Answer
> 1 votes
In most of the models of Turing Machines there is a separate blank symbol $B$. Sometimes we may even have a start symbol $\rhd$. This makes it easy to check if $M$ halts in standard position.

If $0$ is also treated as the blank symbol, and the tape is initialized with 0's on both side of inputs (with no separate blank symbol) then the analysis of computation becomes a little bit difficult (Where is the boundary?).

In your case, it is doable without much hassle as 0's in the input always occur singly. First rewrite the whole input as 2-bit alphabet, converting 0 to 10 and 1 to 11, B will be 00 and start symbol $\rhd$ will be 01. Now we are happy to go. We just need to modify the Turing Machine to consider 2 bits at a time.

# Answer
> 0 votes
If your TM is about to halt, do as follows:

* Check it is reading a 1, if not, go loop
* Go back to the start of the tape (might have to mark it somehow and shift everything over when starting), skipping only 0s. If you find a 1, go loop.
* Advance until you see the first 1. Advance over a stretch of 1 (to reach a 0 or blank)
* If you reached a blank, the tape ends in 1s. Go back to the last 0 (or tape start), advance one space and halt
* If you reached 0, the used tape should end in 0s. Read to the end of the used tape. If you hit a 1, go loop.
* Upon finding a blank, go right over 0s, then 1s, stop at the first 0 (or tape start).
* Move right one space (to the first 1), and halt

---
Tags: computability, turing-machines, computation-models
---


title: Grammar for square numbers in unary

text:
# Question
Title: Grammar for square numbers in unary
I have to write a grammar for the following language: $$\\{1^{n^2} \mid n\geq 1 \\}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as the sum of first $n$ odd numbers but couldn't proceed any further.

# Answer
Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$'s. The following is not the most efficient grammar, but it will do.

Context free grammar rules:

$S \rightarrow BAFUE\ |\ \epsilon$
$U \rightarrow UD \ | \ D$

Non-contracting grammar rules:

$FD \rightarrow DG$
$AD \rightarrow D1A$
$1D \rightarrow D1$
$A1 \rightarrow 1A$
$BD \rightarrow BH$
$H1 \rightarrow 1H$
$HA\rightarrow AI$
$IA\rightarrow AI$
$IG \rightarrow AAF$

Now some non non-contracting rules:

$FE \rightarrow E$
$B \rightarrow \epsilon$
$AE \rightarrow E$
$E \rightarrow \epsilon$

Though this grammar has four non non-contracting rules, I have left them as it is, to help understanding. With a little effort we can convert it into a non-contracting grammar and then to a context-sensitive-grammar.

$IG \rightarrow AAF$ is the important rule, every time it adds two extra $AA$'s to be later substituted by 1's.
> 3 votes

# Answer
Imagine a head that walks over the sentential form and expands some non-terminals it finds. What should the head do?

> Start with a single $A$ and the head to the left of it, i.e. $\circ A$. The head passed from left to right and expands every $A$ it finds to a $1$ and a new $A$ -- and the last $A$ spawns a a new $A$ and triggers that the head copies the last block of $1$s.

How do you move the head?

> With rules of the form $\circ A \to A \circ$.

How do you control what the head does where?

> Introduce marked copies of symbols. For instance, the last $A$ could be a $\hat A$.
> 2 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: General question on approach to showing sample size required is $\Omega(\cdot)$
I was not able to find a similar question in the archives, so pardon this relatively elementary question if it has been asked before.

Let $E\_n$ be some event that depends on the sample size $n$ and suppose we are looking for an upper bound on $n$ that guarantees $Pr(E\_n)\geq 1-\varepsilon$ for some $\varepsilon\in(0,1)$. For example, if we are flipping a biased coin that lands heads with probability $p\>.5$ and we define the event $E\_n = \\{\text{# of heads}\>\frac{n}{2}\\}$ then we are looking for $n\in O(f(p))$ since the sample size will be a function of the parameter $p$. One way I have seen this approached is to upper bound the probability of $E\_n$ NOT occurring and then set this upper bound to be at most $\varepsilon$ and then solving such that we get $n\geq\text{ something involving } p$. My interpretation of this is that it is sufficient to have $n$ this big to guarantee $Pr(E\_n)\geq 1-\varepsilon$ which is why it is an upper bound.

My question then is this: if my interpretation above is correct, is there an analogous approach to showing a lower bound for $n$ i.e. $n\in\Omega(g(p))$?

# Answer
There is a difference between the two questions. Let $p\_n$ be the number of heads in $n$ trials divided by $n$. We know that for large $n$, $p\_n$ is very close to $p$; qualitatively this is the law of large numbers, and quantitatively this is the central limit theorem. This phenomenon is known as *concentration*. This is what you use to give an upper bound on $n$. In contrast, to give a lower bound on $n$ you need to show *anti-concentration*: that for small $n$, $p\_n$ has a reasonable probability of being somewhat far from $p$. The techniques for showing anti-concentration are often more delicate.

In your particular example, concentration can be shown using classical inequalities such as Chernoff's inequality. For anti-concentration you can use the Paley–Zygmund inequality, but you won't necessarily get good bounds. To get nearly tight bounds you can use a general-purpose double-sided inequality such as Berry–Esseen, or a specialized one à la de Moivre–Laplace.
> 0 votes

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


# Question
Title: Help me understand the logic behind x - y in binary by boolean?
x and y are 4 bit signed numbers (2s complement..)

x - y can be obtained by:

```
!(!x + y)

```

I know that in 2s complement

```
-y = (!y + 1)

```

So I can pretty much understand how this works:

```
x - y = x + (!y + 1)

```

But, what sort of magic is going on in here, how does this work:

```
!(!x + y)

```

I mean, when I do the math with pen and paper all is fine, but I do not know **why** it is working..

# Answer
If $z$ is an $n$-bit number then $!z=2^n-1-z$. So $$ !(!x+y)=2^n-1-(2^n-1-x+y) = x-y. $$
> 4 votes

---
Tags: arithmetic, boolean-algebra
---


# Question
Title: How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k \<\< n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the number of disk accesses?

Are there known algorithms for this problem? I searched for external matrix multiplication etc. but couldn't find much.

# Answer
> 3 votes
"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access.

From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012):

> Blocking a matrix multiply routine works by partitioning the matrices into submatrices and then exploiting the mathematical fact that these submatrices can be manipulated just like scalars.

"The cache performance and optimizations of blocked algorithms" by Lam, Rothbrg, and Wolf (1991):

> ...presents cache performance data for blocked programs and evaluates several optimizations to improve this performance.

More lecture notes:

---
Tags: algorithms, efficiency, cpu-cache, linear-algebra, space-analysis
---


# Question
Title: Clarification of the definition of a POMDP
From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as:

* A complete directed graph $G=(V, E)$
* A set of actions $A\_u$ for each vertex $u \in V$
* A reward function $R$ that maps any vertex to some reward, i.e., $R \colon V \mapsto \mathbb{R}$.
* A probability function $P$ that gives the probability $P\_a(u, v)\in \[0, 1\]$ of taking edge $(u, v)$ after performing action $a \in A\_u$ at node $u$

The behavior of any MDP is talked about in terms of some policy $F$, where $F\_0$ is the initial state that the policy starts in, and $F(u)\in A\_u$ is the action $F$ takes when at node $u$, which is defined for all $u \in V$.

We then say that the MDP starts in $u=F\_0$, performs some action $a=F(u)$, then moves to some other vertex $v \in V$ with probability $P\_a(u, v)$. It repeats this process, where on turn $t$ it performs an action $b=F(w)$ some node $w \in V$, then moves to some other node $z\in V$ according to probability $P\_b(w, z)$.

Now, a POMDP (partially observable markov decision process) is defined in a similar manner, except at each state $u \in V$ instead of knowing it's current state, $F$ is given some observation data $O(u) \in S$, where $S$ is any set. $F$ then constructs a "belief state" $b \in \[0, 1\]^{\vert V \vert }$ based on that information, which is a set of probabilities associated with each node of how much it "believes" it is in that node.

Now we define $F$ in terms of what action it performs in a given belief state, where the belief state can change with time.

This all makes sense, my question it just that since there are a different set of actions for each node, how does $F$ know what actions $A\_u$ it has available without knowing what node $u\in V$ it is in?

# Answer
> 2 votes
The availability of action $ a $ can be understood as $P\_a(u, v) \> 0$ for some $ v $

If an action $ a $ is not available in $ u $ then it will have not effect, this means that $P\_a(u, v) = 0 $ for every possible $v$

---
Tags: automata, artificial-intelligence, markov-chains, agent-based-computing
---


title: Common data structure examples

text:
# Question
Title: Common data structure examples
I recently began working as a tutor with my college, helping younger students struggling in intro classes get their footing.

Many of my students particularly struggle with basic data structures (linked lists, heaps, binary \[search\] trees, hash tables, etc.); I'll call them DS's for short. I can often explain a DS where they make sense of it how it works (with a little help from Wikipedia). To further help them develop an understanding of these DS's, I'd like to provide simple examples for them to work through (think 3-layer binary search tree with 5-7 nodes), as well as some common applications of these data structures.

This leads me to my question. Do you know of a collection of basic data structure examples I could use for tutoring students? To clarify, I am not searching for implementations of these DS's, but specifically written/diagrammed problems of the common data structures such as the ones your professor might work through in lecture during the first two years in a university program.

# Answer
> 2 votes
If you want diagrammatic material on data structures like binary search trees etc. then Introduction to Algorithms by C.L.R.S. (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein) should do the job.

# Answer
> 1 votes
If you want real-world examples of data structures in action, perhaps check out some not-too-large open source project that turns out interesting to your students and have them look for use of data structures. One possible example is micro emacs, the (tiny!) editor famous for being Linus Torvalds' favorite.

A collection of small, useful programs (for Unix, in C) showing all sorts of techniques (including data structures) is Kernighan and Pike's "Software Tools" (Addison Wesley, 1976). Dated, but still relevant. Or you might look at Noel Kalicharan "C by Example" (Cambridge University Press, 1994), which looks relevant (haven't seen it, Google let's me peek at it and it looks relevant).

# Answer
> 0 votes
The Lempel-Ziv Encoding algorithm uses hashtable. It was my homework at college to write this algorithm to compress a text file.

I want to add that this is not a complete answer to your question. But you can find all these data structures if you search your everyday programs.

---
Tags: data-structures, reference-request, education
---


# Question
Title: Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?
Recall the standard argument for showing an AVL free is of size $\log n$:

> Let $n\_h = $ be the minimum number of nodes of an AVL tree of height $h$. Then we have:
>
> $$ n\_{h} \geq 1 + n\_{h-1} + n\_{h-2} \implies n\_h \> 2n\_{h-2}$$ $$ n\_h \> 2^{\frac{h}{2} } \implies h \< 2 \log n\_h $$
>
> so the height of the tree is $O( \log n)$.

I understand the recurrence but I just don't understand why we argue about:

> be the minimum number of nodes of an AVL tree of height $h$

maybe my intuition is wrong but I thought that we'd want to argue about as many nodes as we can fit in a tree of height $h$ and show that it still balanced and show its $\log n$. Why is that reasoning incorrect?

# Answer
> 2 votes
First of all AVL trees are binary trees so you can't argue `as many nodes as we can fit in a tree of height h` because the maximum nodes you can fit in a AVL tree with h is 2h+2h-1+...+20. Also the minimum number of nodes on an AVL tree with h is 1+2h-1+2h-2+..+20.

be careful for the first 1 at minimum number rather than 2h. If that plus one node would not exists, the AVL tree would be simply of height h-1, and we don't want that.

So you have to define n as `be the minimum number of nodes of an AVL tree of height h`. Because your algorithm has at least that much of nodes to traverse , and you do the analyze with that assumption

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


title: Robot lawyer algorithm

text:
# Question
Title: Robot lawyer algorithm
I have a background in physics and have taken some few classes online in Machine learning. But I really do not understand how this Robot lawyer can work:

A 19-year-old made a free robot lawyer that has appealed $3 million in parking tickets

I am very interested in this type of artificial intelligence but I have no idea what to start reading about the topic.

Have somebody any idea of what type of algorithm he is using?

Here is what the article says:

> Browder programmed his robot based on a conversation algorithm. It uses keywords, pronouns, and word order to understand the user's issue. He says that the more people use the robot, the more intelligent it becomes. Its algorithm can quickly analyze large amounts of data while improving itself in the process.

Can the same algorithm also make the answer based on law data?

# Answer
I'll join your potential downvote-fest with a speculation-filled answer.

Here are two Expert System algorithms I've worked with in industry.

**Rete Algorithm:**

https://en.wikipedia.org/wiki/Rete\_algorithm

IBM and Oracle both have large Rete systems.

From what I've experienced, these are rules and fact tables that can be exeucted as a single atomic rule, or a million rules all on the same problem. In my case we expressed these rules as tables of values, and IF/ELSE logic rules that can be grouped and managed and revised and controlled.

**General Problem Solver**

https://en.wikipedia.org/wiki/General\_Problem\_Solver

My impression is GPS is more flexible, and better handles the "fuzzy logic" cases and "precedence rules" (Where the answer changes when you reoder the precedence of the rules).

From my experience, I expressed these rules as small LISP functions where the tool could chose the "best" answer even if there still were unsolved values in the LISP functions.

**If I'm allowed to just blindly guess:**

My guess just from my gut feel, is that he's using Jess:

http://www.jessrules.com/
> 1 votes

---
Tags: reference-request, artificial-intelligence
---


# Question
Title: Average prefix code length of every 4-sized frequency vector is bounded at 2
I'm trying to show that for every frequency vector $(p\_1, p\_2, p\_3, p\_4)$ such that $\sum\_{i=1}^4 p\_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w\_1,w\_2,w\_3,w\_4)$ is the outputted code, then $\sum\_{i=1}^4 p\_i |w\_i| \le 2$.

I've tried looking at the tree that is generated by Huffman algorithm, but the thing is that several different tree structures match different 4-sized frequency vectors and I can't tell something general about all of them.

Also, is there a more general theorem for $k, n$ (here $k=4, n=2$)?

# Answer
> 1 votes
Hint: The code generated by Huffman's algorithm has the minimal average word length, and in particular is at least as good as any other code. Show that there is a "universal" code (of length $n=4$) whose average code length is *exactly* $2$ on *any* distribution.

The more general theorem states that the average word length for a code over an alphabet of size at most $2^a+b$ is at most $a + \frac{b}{2^a+b}$; to get the best bound for a specific $n$, write $n = 2^a+b$ with $a$ as large as possible. When $b=0$ there is even a universal code as in your particular case.

---
Tags: binary-trees, data-compression, coding-theory, huffman-coding
---