# Question
Title: Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (Just as the smallest upper bound is $n^7$)

The reason I say that the function is in the Omega class of functions larger than $n^5$ is because of the limit definitions of complexity \[Source\]: $\require{enclose}$

$$\begin{array}{c|c|c} \text{Big-}\mathcal O\ \text{notation} & \text{Comparison notation} & \text{Limit definition}\\ \hline f \in \mathcal o(g) & f \\; {\scriptstyle \enclose{circle}{\kern .07em \bbox\[6px\] \lt \kern .07em}}\ g & \lim\_{x\rightarrow\infty} \frac{f(x)}{g(x)} = 0\\ f \in \mathcal O(g) & f\\; {\scriptstyle \enclose{circle}{\kern .07em \bbox\[6px\]\le \kern .07em}}\ g & \lim\_{x\rightarrow\infty} \frac{f(x)}{g(x)} \< \infty \\ f \in \Theta(g) & f\\; {\scriptstyle \enclose{circle}{\bbox\[7px\]=}}\ g & \lim\_{x\rightarrow\infty} \frac{f(x)}{g(x)} \in \mathbb{R}\_{\>0} \\ f \in \Omega(g) & f \\;{\scriptstyle \enclose{circle}{\kern .07em \bbox\[6px\]\ge \kern .07em}}\ g & \lim\_{x\rightarrow\infty} \frac{f(x)}{g(x)} \> 0 \\ f \in \omega(g) & f\\; {\scriptstyle \enclose{circle}{\kern .07em \bbox\[6px\]\ge \kern .07em}}\\; g & \lim\_{x\rightarrow\infty} \frac{f(x)}{g(x)} = \infty \\ \end{array}$$

Using the limit definition of $\mathcal O$, we correctly identify that $n^5+n^7 \in \mathcal O(n^7)$ and $n^5+n^7 \notin \mathcal O(n^6)$

However, using the limit definition of $\Omega$ tells us that the function is in $\Omega(n^7)$! But isn't the largest lower bound for this function $n^5$?

# Answer
The function $n^5 + n^7$ is big-$Ω$ of both. However, it is little-$\omega$ of $n^5$.

It happens that $n^5 + n^7 \in \Theta(n^7)$. These asymptotic-notations only describe the behavior of the function $f(n) = n^5 + n^7$ for large $n$, aka "for all $n \> \textrm{some value}$". The function is a polynomial function, and the highest-degree term determines the order of growth.

From the definition of $Θ(g)$, it means that function $f$ is both big-$O$ and big-$Ω$ of $g$. The function is bounded by *some constant multiple* of $n^7$ for large $n$. Namely, the function is bounded above by $2n^7$ and below by $n^7$.

Nevertheless, $n^5 + n^7 \in \Omega{(n^5)}$; the function is of \[strictly\] greater order than a quintic. Equivalently, $n^5 \in O(n^5 + n^7)$.
> 3 votes

# Answer
Observe that $n^5+n^7 \> n^7 \ge n^5, ~~\forall n \ge 1$. Then clearly, the 'largest lower bound' is $n^7$. Therefore, $n^5+n^7 = \Omega(n^7)$ as well as $n^5+n^7 = \Omega(n^5)$ and also $n^5+n^7 = \Omega(1)$, but we generally choose the one that is largest and more tight.
> 0 votes

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


# Question
Title: Proof or disproof Fin = Fin-Complete $ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $
$ Fin = \\{ L \in \Sigma^\* : |L| $ is finite and greater than 0 $ \\} $ Proof or disproof Fin = Fin-Complete Where Fin-Complete means that for every $ L\_1,L\_2 \in Fin $ there exist a valid reduction $ L\_1 \leq L\_2 $

my trial:

Consider two languages $ L\_1 $ and $ L\_2 $ where $ L\_1 $ contains a single string s $ L\_1 = \\{ s \\} \ s \in \Sigma^\* $ and $ s \neq \epsilon $ a finite language of size 1. Let $ L\_2 = \emptyset $ the empty language, which is also finite by definition as it contains zero strings. By the definition of reduction, $ L\_1 \leq L\_2 $ there must exist a computable function $ f $ such that for any string $ w \in L\_1 $ if and only if $f(w) \in L\_2 $ however since $ L\_2 = \emptyset $ there are no strings in $ L\_2 $ for $ f(x) $ to map to construct such a function f that satisfies the condition for all $ w\in L\_1 $

# Answer
> 2 votes
The claim is correct. To see why, note that every language in $L\in Fin$ is non-trivial and regular. Indeed, $L$ is not empty, by the definition of $Fin$, and does not equal $\Sigma^\*$ as then it would be infinite. Now the claim follows from the fact that every regular language is decidable, and the fact that every non-trivial language is $R$-hard. Specifically, for every two languages $L\_1, L\_2 \in Fin$, we have that $L\_1 \in \text{REG} \subseteq \text{R}$ and $L\_2 \notin \\{ \emptyset, \Sigma^\*\\}$. Hence, we conclude that $L\_1\leq\_m L\_2$.

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


title: Deadlock in LockTwo Algorithm

text:
# Question
Title: Deadlock in LockTwo Algorithm
I was reading the Book: The Art of Multiprocessor Programming; Section 2.3.2. and I have a doubt regarding their $\texttt{LockTwo}$ algorithm mentioned in Page 26. The snippet of the algorithm is:

```
    class LockTwo implements Lock {
    private volatile int victim;
    public void lock() {
    int i = ThreadID.get();
    victim = i; // let the other go first
    while (victim == i) {} // wait
    }
     public void unlock() {}
     }

```

In the next page, they mention:

> The LockTwo class is inadequate because it deadlocks if one thread runs completely before the other. Nevertheless, LockTwo has an interesting property: if the threads run concurrently, the lock() method succeeds. The LockOne and LockTwo classes complement one another: each succeeds under conditions that cause the other to deadlock.

I dont understand why $\texttt{LockTwo}$ algorithm causes deadlock when threads are run sequentially. lets say thread0 is executing first and thread1 runs completely after the first thread first thread0 will set victim as 0 and will wait indefinitely. When thread1 comes, it will set victim as 1 hence thread0 will complete its execution and thread1 will wait indefinitely. Isnt it starvation rather than deadlock or am I making some mistake?

# Answer
I've recently been reasoning about this algorithm as well. I think its both. You pointed out the starvation case. Here is the author's definition of deadlock as given on page 24:

> **Freedom from Deadlock** If some thread attempts to acquire the lock, then some thread will succeed in acquiring the lock. If thread A calls `lock()` but never acquires the lock, then other threads must be completing an infinite number of critical sections.

It seems to requires an algorithm to guarantee two things:

1. that some thread will get the lock if a group of threads is waiting for it.
2. that a thread that waits forever for the lock CAN get the lock. I.E. that the thread is starving not stuck.

`LockTwo` satisfies the first case but not the second. The second thread will be stuck forever if the first thread never attempts to grab the lock again.
> 1 votes

---
Tags: operating-systems, synchronization, deadlocks, critical-section
---


# Question
Title: Turing Machine language, Undecidable, reductions
I have exam next week about automata theory, languages and computation. I struggle with reductions (Undecidability). For example for this two problems, and need to check first if the language is recursive, RE but no recursive or NOT-RE. After that to prove with reduction, okay for proving is easy I think, but to check what is language is my problem, please if someone can help me. For example how to decide in which category is this two languages?

1. $L = \\{ \langle M\rangle \mid |L(M)|\neq 17 \\}$
2. $L = \\{ \langle M\rangle \mid |L(M)|= 17 \\}$

# Answer
Before doing reductions, it is good to have some intuitions about decidability: that helps to find which reduction can succeed.

First, none of those two languages is recursive, because Rice's theorem states that nontrivial semantic properties are undecidable.

Second, since those languages are complement of each other, if one is RE, the other is not (otherwise, they would be decidable).

Another intuition that can help is reinterpreting $\langle M\rangle$, $L(M)$ and $L$: Turing machines are programs!

* $\langle M \rangle$ can be interpreted as the source code of a program;
* $L(M)$ can be seen as the set of inputs $x$ such that $M(x)$ terminates;
* $L\_2 = \\{\langle M\rangle \mid |L(M)| = 17\\}$ is the set of programs that have $17$ inputs terminating.

Back to the problem:

* $L\_1 = \\{\langle M\rangle \mid |L(M)| \neq 17\\}$ is the set of programs that don't have exactly $17$ terminating inputs. This cannot be decided, or even semi-decided, because you would need to test all inputs;
* $L\_2$ is the set of programs that have exactly $17$ terminating inputs. While this could seem semi-decidable at first, because you could find those $17$ inputs, the problem is that you have to test all other inputs, to be sure that there are not any more that are terminating.

That would mean that none of the language is RE.

Now for a real reduction: I will reduce $L\_{\in} = \\{\langle \langle M\rangle, x\rangle\mid x\in L(M)\\}$, which is a well-known non recursive language, to $L\_2$. For convenience purposes, I will consider only integer inputs, but it is easy to work with any set of countable inputs.

From an input $\langle \langle M\rangle, x\rangle$ of $L\_{\in}$, consider the following Turing machine $M'$, which on input $y$:

* simulates the computation of $M(x)$;
* if $M(x)$ accepts and $y\in \\{1, 2, …, 17\\}$, then $M'$ accepts $y$;
* otherwise, $M'$ rejects $y$.

Then $|L(M')| = 17$ if and only if $x\in L(M)$. This is a many-one reduction. Since $L\_{\in}$ is not recursive, nor is $L\_2$.

Also, since $L\_{\in}\leqslant\_m L\_2$, that proves that $\overline{L\_{\in}}\leqslant\_m \overline{L\_2} = L\_1$. Since $\overline{L\_{\in}}$ is not RE, nor is $L\_1$ (that works because the reduction is many-one).

Now, a bit more difficult, we will prove that $L\_2$ is not RE, by doing a many-one reduction from $L\_{\in}$ to $L\_1$ (which gives a many-one reduction from $\overline{L\_{\in}}$ to $L\_2$).

From an input $\langle \langle M\rangle, x\rangle$ of $L\_{\in}$, consider the following Turing machine $M'$, which on input $y$:

* Simulates $y$ steps of the computation of $M(x)$;
* If $M$ does not accept $x$ at the $y^{\text{th}}$ step, and $y\in \\{1, …, 17\\}$, then $M'$ accepts $y$;
* If $M$ accepts $x$ at the $y^{\text{th}}$ step, and $y \> 17$, then $M'$ accepts $y$;
* Otherwise, $M'$ rejects $y$.

Then:

* if $x\notin L(M)$, $M$ will never accept $x$ during the $y$ steps of computation, and $L(M') = \\{1, …, 17\\}$;
* conversely, if $x\in L(M)$, then:
    + if $M$ accepts $x$ in $k \leqslant 17$ steps, $L(M') = \\{1, 2, …, k-1, k+1, …, 17\\}$, so $|L(M')| \< 17$;
    + if $M$ accepts $x$ in $k \> 17$ steps, then $L(M') = \\{1, 2, …, 17, k\\}$, and $|L(M')| \> 17$.

This is indeed a many-one reduction from $L\_{\in}$ to $L\_1$.
> 2 votes

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


# Question
Title: Probability of overflow in a summation of fixed-size signed integers
How can I estimate the probability that the sum $S\_n$ of $n$ uniform random 48-bit signed integers overflows a 64-bit signed integer?

Edit: the overflow can occur at any step, not only on the final result.

Since this is a normal distribution, I guess that the cumulative sums more or less oscillate around zero, and that the probability that they ever exceed 64 bits is vanishingly small. I would like to formalise this intuition.

# Answer
Suppose the 48-bit signed integers are drawn uniformly randomly from $\[-2^{47}, 2^{47}-1\]$. To overflow, there must be at least $n = 2^{63}/2^{47} = 2^{16}$ integers drawn, so $n$ is large enough for the Central Limit Theorem to apply, so the result is approximately<sup>\[citation needed\]</sup> Normal but discretized.

For independent variables $X\_i$ with mean $\mu$ and variance $\sigma^2$, the resulting sum will be approximately Normal with mean $n \mu$ and variance $n \sigma^2$. For our uniformly random integers, the mean $\mu = -1/2$ is slightly biased negatively as ruakh notes, and the variance is about $(2^{48})^2/12 = 2^{96}/12 \approx 6.6e27$, so this means the resulting distribution is approximately $N(-n/2, 6.6e27 \times n )$.

Since the standard deviations are only about $8.1e13 \sqrt n$, even for $n=1e8$, $2^{63}$ would be more than 10 SDs away, but for $n=1e9$, it's only 3.6 SDs, so pick your $n$ based on z-score probabilities. (For SDs this large, the biased mean has little effect on the result.)
> 4 votes

# Answer
Calculate the average and variance of choosing a single signed 48 bit variable. Multiply by n to get the average and variance of choosing n 48 bit variables. The standard variation is roughly the square root of the variance.

Calculate how many standard deviations away from the average you need to be for an overflow. The probability of being more than k standard deviations away from the mean is about exp(-k^2).

Now that is the probability of overflow after summing n numbers. It ignores the possibility that the sum might overflow and then become smaller again. So the probability of overflow *at some point* within n steps is higher.
> 7 votes

# Answer
Hoeffding's inequality gives non-asymptotic probability bounds. If $X$ is on $\[a,b\]$ and $C\>b-a$ then $$P\left(\left|\sum\_i X\_i - \sum\_i E\[X\_i\]\right|\>t\right)\leq 2\exp\left(\frac{-2t^2}{nC^2} \right).$$

This gives qualitatively similar bounds to the CLT that @qwr used, but slightly more rigorous since the CLT statement is asymptotic and Hoeffding's inequality holds for all $n$ and $t$
> 1 votes

---
Tags: probability-theory, integers
---


# Question
Title: How do I prove that the Perceptron bound for mistakes is tight?
How do I prove that the Perceptron bound for mistakes is tight? I need to prove that for any amount of given data points, the total amount of updates (mistakes) that the algorithm will make is $\frac{1}{\gamma ^2}$, where $\gamma$ is the margin. I know that I'll have to make it such that for a given $m$ number of data points, I'll make it such that $\gamma = \frac{1}{\sqrt{m}}$, but I'm not really sure how to continue and would appreciate a hint in the right direction.

# Answer
This is also given as Exercise 9.3 in Shai Shalev-Shwartz and Shai Ben-David's *Understanding Machine Learning: From Theory to Algorithms*, where they provide the following hint: choose the dimension to be $d=m$ and the points to be $x\_i=e\_i$ (the canonical vectors $(e\_i)\_j=\mathbf 1\_{\[j=i\]}$).

Observe that all $x\_i$s have norm 1. You can first prove that there is a vector $w^\*$ with norm $\\|w^\*\\|^2=m$ such that $y\_i\langle x\_i,w^\*\rangle\geq 1$, realising the margin $\gamma=\frac 1{\sqrt m}$ and giving the Perceptron bound $m$. Finally, you can prove that at least $m$ updates are required.
> 1 votes

---
Tags: machine-learning, perceptron
---


# Question
Title: Repeated rules with more than three symbols for conversion to Chomskys Normal Form
I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \\;\vert\\; B b C$$ $$A \to A a B \\;\vert\\; B b C$$ $$B \to B b C$$ $$C \to x$$

I am trying to understand if the right converstion would result in this:

$$S \to A\_1B \\;\vert\\; B\_1C$$ $$A\_1 \to Aa,$$ $$B\_1 \to Bb,$$ $$A \to A\_2B \\;\vert\\; B\_2C $$ $$A\_2 \to Aa,$$ $$B\_2 \to Bb,$$ $$B \to B\_3C $$ $$B\_3 \to Bb,$$ $$C \to x$$

Or if it would be ok and accepted to condense the new variables into one (as they have the exact same rule):

$$S \to A\_1B \\;\vert\\; B\_1C$$ $$A \to A\_1B \\;\vert\\; B\_1C $$ $$B \to B\_1C $$ $$A\_1 \to Aa,$$ $$B\_1 \to Bb,$$ $$C \to x$$

Thanks, I've been trying to find examples online and follow them but none seem to follow the same issue so any help will be very much appreciated :)

# Answer
> 5 votes
Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences".

Note that your final result does not yet satisfy Chomsky normal form. Productions are either of the form $A\to BC$ or $A\to a$. That means that one cannot produce a nonterminal and a terminal symbol at the same time.

---
Tags: formal-languages, automata, context-free, formal-grammars, chomsky-hierarchy
---


title: The complement of a particular language

text:
# Question
Title: The complement of a particular language
We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not linear, but I can't prove it.

# Answer
The complement of the language $L = \\{a^nb^n : n \in \mathbb{N}\\}$ should actually be linear, if I'm not mistaken. Take some string $x \notin L$ over the alphabet $\Sigma = \\{a, b\\}$, since $L \subseteq a^\*b^\*$ one of three cases must be true:

* $x \notin a^\*b^\*$, or
* $x = a^nb^m \in a^\*b^\*$ and $n \> m$, or
* $x = a^nb^m \in a^\*b^\*$ and $n \< m$.

So the complement of $L$ (relative to $\Sigma$) can be expressed as $$\overline{L} = \overline{a^\*b^\*} \cup \\{a^nb^m : n \> m\\} \cup \\{a^nb^m : n \< m\\}.$$ Now, $\overline{a^\*b^\*} \in \texttt{REG}$ so $\overline{a^\*b^\*}$ must be linear. Using an induction argument over the rules of the linear grammar $G$ with rules $$S \to aS | aA$$ $$A \to aAb | \varepsilon$$ and start variable $S$, it can be shown that $L(G) = \\{a^nb^m : n \> m\\}$ is linear. Similarly, $\\{a^nb^m : n \< m\\}$ can be generated by a linear grammar with rules $$S \to Sb | Bb$$ $$B \to aBb | \varepsilon.$$ Since $\overline{L}$ can be written as the union of linear languages, and the linear languages are closed under union, it follows that $\overline{L}$ must be linear as well.

## Counterexample

I think I might've found a valid counterexample. The language $L = \\{a^nb^mc^k : n \neq m \land m \neq k\\}$ is well known to be context-sensitive.

Observe that $$\overline{L} = \overline{a^\*b^\*c^\*} \cup \\{a^nb^mc^k : n = m\\} \cup \\{a^nb^mc^k : m = k\\}.$$ It can be verified that the linear Grammars $$S \to Sc | A$$ $$A \to aAb | \varepsilon$$ and $$S \to aS | A$$ $$A \to bAc | \varepsilon$$ with start variable $S$ generate $\\{a^nb^mc^k : n = m\\}$ and $\\{a^nb^mc^k : m = k\\}$ respectively, and that $\overline{a^\*b^\*c^\*} \in \texttt{REG}$. So $\overline{L}$ is linear whilst $\overline{\overline{L}} = L$ is not, counterexample ↯
> 3 votes

---
Tags: formal-languages, context-free, linear-languages
---


# Question
Title: Closures break induction in correctness proof of interpreter
I'm trying to prove the correctness of an interpreter for a simple extension of untyped lambda-calculus with De Bruijn indices. The interpreter is *bounded*, i.e. in order to ensure its finiteness it has an additional parameter $n \in \mathbb N$ that decreases with each recursive call. The function returns $\bot$ when $n = 0$.

This is the signature of the interpreter: $\mathcal E : (\mathbb N, Env, E) \to (Val \cup \\{\bot\\})$

Where $Env$ is the set of environments, represented as lists of values accessed with De Bruijn indices, $E$ is the set of expressions and $Val$ is the set of values:

$$ \begin{aligned} E &::= \lambda E \mid EE \mid A \mid B \mid \texttt{if } E \texttt{ then } E \texttt{ else } E \mid x \in Var \mid V\\ A &::= \textit{integer operations...} \\ B &::= \textit{boolean operations...} \\ V &::= \texttt{True} \mid \texttt{False} \mid c \in \mathbb Z \mid \texttt{Closure} (\rho, E) \end{aligned} $$

#### Soundness theorem

$$\forall e, \rho, n, v . \mathcal E (n, \rho, e) = v \implies \langle e, \rho \rangle \to^\* v$$

I.e.: If $e$ evaluates to $v$ under the initial environment $\rho$ and in a finite number of steps, then there exists a finite proof that it does, which uses the rules of the small-step semantics I describe in the "appendix" of this post.

#### Proof Attempt Sketch

I tried to prove the theorem by induction on $e$.

##### Base Cases

The base cases are lambdas, values and variables. I managed to prove these cases with ease.

* **Lambdas**: Let $e = \lambda e'$. First off, the case in which $n = 0$ can be eliminated, since it makes the premise of the theorem false (ex falso...). If $n = Sm$, by the definition of the interpreter we get that the value $v$ must be $\texttt{Closure}(\rho, e')$. The case can be shown to work by applying the LAMBDA rule, some properties of the star closure and the VALUE rule.
* **Values**: trivial.
* **Variables**: Use rule VAR-KO to eliminate the case in which the variable is not in the environment. Then, it's a matter of applying the VAR-OK rule and the definition of the interpreter, plus some property of the star closure.

##### Inductive cases (problem is here!!!)

The most complex inductive case, and the one that is giving me problems, is the case of application: $e = e\_1e\_2$. The inductive HPs are: $$ \forall \rho, n, v . \mathcal E (n, \rho, e\_1) = v \implies \langle e\_1, \rho \rangle \to^\* v \quad \text{(IHe1)} $$ $$ \forall \rho, n, v . \mathcal E (n, \rho, e\_2) = v \implies \langle e\_2, \rho \rangle \to^\* v \quad \text{(IHe2)} $$

By applying these to the definition of $\mathcal E$ and doing some case checking (the evaluations of $e\_1$ and $e\_2$ cannot be $\bot$ by Hp), from the inductive hypotheses we obtain that for some $\rho'$ and $e'$:

$$ \forall \rho, n \langle e\_1, \rho \rangle \to^\* \texttt{Closure}(\rho', e') $$

and for some $v'$:

$$ \forall \rho, n, \langle e\_2, \rho \rangle \to^\* v' $$

At this point we use an auxiliary lemma:

> If $\langle e\_1, \rho \rangle \to^\* \texttt{Closure}(\rho', e')$ and $\langle e\_2, \rho \rangle \to^\* v'$, then: $$ \langle e\_1e\_2, \rho\rangle \to^\* \langle \texttt{Closure}(\rho', e') v', \rho\rangle$$

Which is easily shown by induction.

We thus obtain: $$ \langle e\_1e\_2, \rho\rangle \to^\* \langle e', \texttt{bind} (\rho', v') \rangle $$ and: $$ \mathcal E (S m, \rho, e\_1e\_2) = \mathcal E (m, \texttt{bind}(\rho', v'), e') = v $$

But we have no induction hypothesis on $e'$, of the form:

$$ \forall \rho, n, v . \mathcal E(n, \rho, e') = v \implies \langle e', \rho \rangle \to^\* v \quad \text{(Fake-Hp)} $$

which would allow us to conclude the proof. Do you have any suggestions on how I should finish the proof I sketched in this post?

### Appendix: Interpreter definition and semantics

What follows is a partial definition of the interpreter (leaving out the non-relevant portions..)

$$ \begin{aligned} \mathcal E (0, \\\_, \\\_) &:= \bot\\ \mathcal E (S n, \rho, \lambda e) &:= \texttt{Closure}(\rho, e)\\ \mathcal E (S n, \rho, v) &:= v &\text{$v \in Val$}\\ \mathcal E (S n, \rho, e\_1e\_2) &:= \begin{cases} \mathcal E (n, \texttt{bind}(\rho', \mathcal E(n, \rho, e\_2)), e) & \text{if } \mathcal E (n, \rho, e\_1) = \texttt{Closure}(\rho', e) \\ \bot &\text{otherwise} \end{cases} \\ \mathcal E (S n, \rho, x) &:= \begin{cases} \mathcal E (n, \rho, \rho\[x\]) & \text{if $\rho\[x\] \neq \bot$}\\ \bot & \text{otherwise} \end{cases} &\text{$x \in Var$}\\ \end{aligned} $$ Now for the small-step semantics: The intermediate values of the computation have form $\langle e, \rho \rangle$ where $\rho$ is the environment of evaluation. The termination values are the elements of the set $V' = V \cup\\{\bot\\}$, where $$V = \\{\texttt{True}, \texttt{False}, \texttt{Closure}(e, \rho), c \in \mathbb Z\\}$$

* Law for transforming lambdas into closures $$ \dfrac{}{\langle \lambda e, \rho \rangle \to \langle \texttt{Closure} (\rho, e), \rho \rangle}\label{redlambda} \quad \text{(LAMBDA)}$$
* For all values $v \in Val$: $$ \dfrac{}{\langle v, \rho \rangle \to v} \quad \text{(VALUE)}$$
* Laws for variables: $$ \dfrac {\rho\[x\] = v}{\langle x, \rho \rangle \to v} \quad \text{(VAR-OK)} $$ $$ \dfrac {\rho\[x\] = \bot}{\langle x, \rho \rangle \to \bot} \quad \text{(VAR-KO)} $$
* Laws for application: $$ \dfrac{\langle e\_1 , \rho \rangle \to \langle e\_1' , \rho \rangle} {\langle e\_1 e\_2, \rho \rangle \to \langle e\_1' e\_2, \rho \rangle}\quad\text{(APPLY-1)}$$

$$ \dfrac{\langle e\_2, \rho \rangle \to \langle e\_2', \rho \rangle} {\langle v\_1 e\_2, \rho \rangle \to \langle v\_1 e\_2', \rho \rangle}\quad\text{(APPLY-2)}$$

$$ \dfrac{} {{\langle (\texttt{Closure} (\rho', e)) v\_2, \rho \rangle \to \langle e, \texttt{bind} (\rho', v\_2) \rangle}}\quad\text{(APPLY-3)}$$

Where `bind` adds $v\_2$ to the environment, adding it "on top" of the list that represents it.

$$ \dfrac{}{\langle v\\, e\_2, \rho \rangle \to \bot} \quad\text{(APPLY-KO)} $$

# Answer
> 3 votes
You must strengthen the theorem to be proved by induction. In the $e\_1e\_2$ case, the current induction hypothesis just tells you that $e\_1$ reduces to a closure, but not anything more about how the enclosed expression reduces. Another hint that something is missing is that in the $\lambda x . e$ case (and the closure case which is hidden under "values"), you don't make use of the induction hypothesis on $e$, which is precisely about how $e$ reduces.

You will have more luck with a proof by induction on a recursive property like the following:

$P(e) = \`\`\forall n \rho v,\\; \mathcal{E}(n,\rho,e) = v \implies (\rho,e) \to^\star v \wedge (\forall \rho' e',\\; v = \mathbf{Closure}(\rho',e') \implies P(e'))"$

This creates new problems that you will have to figure out (Now it's too strong for the case of variables, how to weaken it a bit? Is this recursive property even well-defined? (if not, how to make it so?)). Hopefully this gets the ball rolling for you.

---
Tags: lambda-calculus, correctness-proof, software-verification, interpreters
---


title: Recursive formula for height of BST

text:
# Question
Title: Recursive formula for height of BST
Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum\_{i = 0}^{n-1}\left\[\text{max}(H(i), H(n-1 -i)) + 1\right\]$$ But I don't know how to prove this is correct. Can anyone help me or explain why this is incorrect?

Note proving it directly seems hard because you end up with E\[max(X, Y)\] where X is height of left subtree and Y height of right subtree. I'm not really sure how to deal with this if we're looking for an exact recursion, not just a bound.

# Answer
The formula is wrong.

Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$).

But: $$\frac13\sum\limits\_{i=0}^2(\max(H(i), H(2 - 1 - i)) + 1) = \frac13(H(2) + H(1) + H(2) + 3) = \frac53\neq\frac95$$

The reason is that in your formula, you do not weigh each $H(i)$ by the number of trees of size $i$.
> 2 votes

# Answer
In addition to the upper bound in https://cs.stackexchange.com/a/96451/12322

Lower bound

$\displaystyle E(Y\_n)= \frac{2}{n} \sum^n\_{i=0}(E\[2\max(Y\_{i−1},Y\_{n−i})\] + 1) \geq \frac{2}{n} \sum^{n-1}\_{i=0} E\[Y\_{i}\]$
> 0 votes

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


title: Size of tree decomposition

text:
# Question
Title: Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I found discuss only treewidth.

# Answer
Not a complete answer, but in T. Kloks *Treewidth* you have the following lemma:

> There always exists a *nice tree decomposition* of width $k$ and with at most $4n$ bags.

It is NP-complete to determine the minimum number of bags in a tree decomposition of width $k$.

---

At request of references:

> Lemma 2.2. Every graph $G$ with treewidth $k$ has a nice tree-decomposition of width $k$. Furthermore, if $n$ is the number of vertices of $G$ then there exists a nice tree-decomposition with at most $4n$ nodes.

Bodlaender, H.L. and Kloks, T. (1996) "Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs", Journal of Algorithms, 21(2), pp. 358–402. Available at: https://doi.org/10.1006/jagm.1996.0049.

They don't give a proof, but reference Kloks, T. (ed.) (1994) Treewidth. Berlin/Heidelberg: Springer-Verlag (Lecture Notes in Computer Science). Available at: https://doi.org/10.1007/BFb0045375.
> 3 votes

# Answer
Take any node $X\_1$ of your tree decomposition $T$. It contains at least 2 vertices from $G$. Let's call $T'\_1 = \\{X\_1\\}$, a new tree containing only this node. And $L\_1$, the cardinality of the subset of $G$ it contains, thus $L\_1 \ge 2.$

Then you add all the other nodes $X\_i$ of $T$, one by one, to grow this new tree incrementing the index $i$ of $T'\_i$ containing $L\_i$ vertices of $G$. The only rule is to pick a node which is connected to $T'\_i$, it is always possible as $T$ is connected.

Thus, the new node $X\_i$ is connected to $T'\_{i-1}$ by only one edge (either it would not be a tree anymore). Let's call $X\_j$, the other node of this edge.

Then $X\_i$ contains at least one vertex from $G$ which is not in $X\_j$ and not in any other node of $T'\_{i-1}$, because it would imply to put a new edge and not respect the tree statement. Then $L\_i \ge L\_{i-1} + 1$.

By induction you get $n \ge L\_k \ge 1+k$, with $k$ the number of nodes in $T$.

Then the tree decomposition can have at most $n-1$ nodes
> 0 votes

# Answer
The post is old but I think someone might find this piece of information helpful: in *Kleinberg and Tardos* (I have a translated version so the numbering might be different) in chapter 10.4 there is a proof of the following statement

> Every non-redundant tree decomposition of a graph with $n$ vertices has at most $n$ nodes/bags.

Moreover for every tree decomposition I can create a non-redundant tree decomposition (i.e. a tree decomposition T in which there is no edge (x,y) in T with corresponding bags $V\_x, V\_y$ s.t. $V\_x\subseteq V\_y$)
> 0 votes

---
Tags: graphs, reference-request, trees, treewidth
---


# Question
Title: How it possible given string belong to given grammar
Consider this context-free grammar:

$$G:\\\\;\\; S\to aSbb|aaSbbb|\lambda$$

Is the string $a^{2020} b^{4020}\in L(G)$?

I try to derive such a string but I can't, how it possible?

# Answer
> 4 votes
This is possible, provided there is a solution in nonnegative integers to the following pair of equations.

$$ \left\\{ \begin{array}{rcrc@{\qquad}l} x & + & 2y & = & 2020 \\ 2x & + & 3y & = & 4020 \end{array} \right. $$

---
Tags: formal-languages, context-free
---


# Question
Title: Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?
Is the time complexity of `for(int i=0;i<n;i++){i*=k;}` $O(\log\_k n)$?

The problem is number 8 from GeeksForGeeks:
https://www.geeksforgeeks.org/practice-questions-time-complexity-analysis/

I trace the program by hand and got stuck. I could not prove that the answer is $O(\log\_k n)$. I made a mistake somewhere.

Assume $k = 1$ and $n = 3$:

| n iteration | i = i * k | k = 1 |
| --- | --- | --- |
| 0 | i = 0 * 1 = 0 | 1 |
|  | i ++ |  |
|  | 1 |  |
| 1 | i = 1 * 1 = 1 |  |
|  | i ++ |  |
|  | 2 |  |
| 2 | i = 2 * 1 = 2 |  |
|  | i ++ |  |
|  | 2 + 1 = 3 |  |

The loop will stop because $i$ is no longer less than $n$.

In general, if $k$ is not known the loop will continue until $i \> n$ or $i = n$

What is $i$ if $k = 1$

$i = 0, 1, 2, 3, 4, 5, \cdots, = i + 1$

Replacing $i$ with $k$

$i = 0, 1, 2, 3, 4, 5, \cdots, = k + 1$

$i = k + 1$

Substituting the value of $i$ into the equation $i = n$

$k + 1 = n$

$k = n - 1$

$\log\_k (k) = \log\_k (n - 1)$

$1 = \log\_k (n - 1)$

$T(n) = \log\_k (n - 1)$

# Answer
If k=0 then i is set to 0 inside the loop, so it halts instantly if n \<= 1 and runs forever otherwise.

If k=1 then the multiplication has no effect. The loop ends instantly if n \<= 0 and after n iterations otherwise.

Let m be the number of iterations starting with m = 0. If k \>= 2 then i is set to 0 inside the loop during iteration #0, and to a value i \>= k^m during iteration #m. So the loop runs at most as long as k^m \< n or m \< log\_k(n).
> 0 votes

# Answer
In the incomplete GeeksForGeeks question #8, it is only correct when $k \> 1, k \in \mathbb{Z}$. The code is equivalent to `for(int i=0;i<n;i=1+i*k)`. We can work out the first few iterations and see:

Iteration #$1$: $i = 1 + 0k = 1$

Iteration #$2$: $i = 1 + 1k = 1 + k$

Iteration #$3$: $i = 1 + (1 + k)k = 1 + k + k^2$

Iteration #$4$: $i = 1 + (1 + k + k^2)k = 1 + k + k^2 + k^3$

Iteration #$5$: $i = 1 + (1 + k + k^2 + k^3)k = 1 + k + k^2 + k^3 + k^4$

Iteration #$x$: $i = 1 + k + k^2 + k^3 + \cdots + k^{x - 1} = (k^x - 1) / (k - 1)$

Now we want to solve $x$ for any given $n \in \mathbb{Z}$.

$(k^x - 1) / (k - 1) = n$

$(k^x - 1) = kn - k$

$k^x = kn - k + 1$

$x = \log\_k(kn - k + 1)$

$T(n) = O(\log\_k n)$

If we don't assume $k \> 1$, observe that multiplication by zero will induce infinite loop, and multiplication by one will do nothing, yielding $T(n) = \begin{cases} O(\infty) & \text{if } \lvert k\rvert = 0, k \in \mathbb{Z}\\ O(n) & \text{if } \lvert k\rvert = 1, k \in \mathbb{Z}\\ O(\log\_k n) & \text{if } \lvert k\rvert \> 1, k \in \mathbb{Z}\\ \end{cases}$
> 1 votes

---
Tags: time-complexity, asymptotics, proof-techniques
---


title: Bellman Ford algorithm relaxation

text:
# Question
Title: Bellman Ford algorithm relaxation
In the Bellman-Ford algorithm's relaxation part, I can't seem to understand why we need to use (d\[v\] = min{ d\[v\], d\[u\] + c(u, v) }), the (c(u,v)) part. This uses the original weight. Why can't it use the least cost(shortest) between (u,v) instead of c(u,v)?

# Answer
> 1 votes
You can't, because the length of the shortest path between $u$ and $v$ is not known. The purpose of the Bellman-Ford algorithm is to compute such lengths, so you can't assume they are already known.

---
Tags: algorithms
---


# Question
Title: What happens when two different nodes have the same Lamport clock ID
With Lamport clocks, each node keeps its own counter. Before sending a message, a node increments its counter by one: `LC(A)=LC(A)+1`, and sends `{1,msg}` to B. Upon receiving a message, B updates its counter using the following formula: `LC(B)=max(LC(B),LC(msg))+1=max(0,1)+1=2`.

This works as expected when A and B take turns: A sends a message to B and B reacts by sending a message to A (or another node entirely).

However, this is not always the case. For example, in a typical TCP connection:

* A sends a message to B ("SYN")
* B replies to A ("SYN/ACK")
* A replies to B ("ACK") and then sends an actual request, such as an HTTP GET.

What happens (assuming both A and B start with their logical clocks set to zero):

* A increments its counter: LC(A)=1
* A sends {1,SYN} to B
* B updates its counter: LC(B)=max(0,1)+1=2
* B increments its counter: LC(B)=2+1=3
* B sends {3,SYN/ACK} to A
* A updates its counter: LC(A)=max(1,3)+1=4
* A increments its counter: LC(A)=4+1=5
* A sends {5,ACK} to B
* B updates its counter: LC(B)=max(3,5)+1=6
* At this point, A has to send another message (e.g. "GET /"). It increments its counter: LC(A)=5+1=6 and sends {6, GET /} to B.

As a result, both nodes have the same logical clock ID: LC(A)=LC(B)=6.

Is this a valid result? What happens next?

I have read that

> Though there can be a case where both nodes have the same clock id for the key and if so we will have to rely on some external mechanism to resolve the conflict.

Source

But I'm not clear on the details. What kind of external mechanism could be adopted, if it is even needed?

# Answer
**tl;dr** As Lamport writes at the top of page 561 of Time, Clocks, and the Ordering of Events in a Distributed System:

> To break ties, we use any arbitrary total ordering $\prec$ of the processes.

To elaborate, ties are indeed possible and already anticipated by Lamport in the paper that introduced the concept. A somewhat minimal example would be one of two concurrent processes that each send a message to the other.

In the later literature, "process IDs" are often recommended to break those ties. Plain UNIX PIDs wouldn't necessarily work because those aren't necessarily unique across machines. Instead, one could combine a machine ID followed by a process ID.
> 2 votes

---
Tags: distributed-systems, partial-order, clocks, ordering
---


# Question
Title: How did the authors of Spice apply weakest precondition rule on their example car problem?
While reading the example given in \[1\]., I couldn't understand how the authors set up the logic to compute the weakest preconditions (*wp*) in their car example in section 4.2.

The dynamics of the problem are given by -

$x' = x + 0.1v$

$v' = v + 0.1a + \epsilon$

I don't see the authors working on the former equation, only the latter. In addition, while reading about *wp* from the book \[2\], I learned that one needs to come up with a suitable postcondition. I believe the postcondition here is $v \<= 1$. Why did the authors start the *wp* computation using $v\_1 \<=1 \land v\_2 \<= 1$? Also, in the next step they do $v\_1\<=1 \land v\_1 + 0.1a\_1 + \epsilon\_1 \<= 1$. Why did they only expand the equation on the right of the conjunction?

Here is how I imagined it should have been done (based on my very limited knowledge of *wp* computations -

We have the equation $v' = v + 0.1a + \epsilon$ and we have a horizon of 2. Therefore, we write this equation 2 times (because that's how RL algorithms are unrolled) -

$v\_1 = v\_0 + 0.1a\_0 + \epsilon\_0$

$v\_2 = v\_1 + 0.1a\_1 + \epsilon\_1$

Now we set up a postcondition on $v\_2$ such that $v\_2\<=1$ and then work backwards. My understanding is probably wrong, but I'd like the reader to see where I am getting confused.

Please let me know if any clarification from my side is needed.

---

Regarding the relation between $x'$ and $x$ and also $v\_2$ and $v\_1$: My understanding here is that $x'$ represents the subsequent state of the variable $x$. This is because of the following line in the paper - "A policy, in interaction with the environment, generates trajectories (or rollouts) $x\_0,u\_0, x\_1,u\_1, \ldots, u\_{n-1}, x\_n$ where $x\_0 \sim p\_0$, each $u\_i \sim \pi(x\_i)$, and each $x\_{i+1} \sim P(x\_i, u\_i)$." Here we can see that each state can be obtained from the subsequent state except the initial state.

---

\[1\]. Anderson, Greg, Swarat Chaudhuri, and Isil Dillig. "Guiding Safe Exploration with Weakest Preconditions." International Conference on Learning Representations. 2023.

\[2\]. Pierce, Benjamin C., et al. "Software foundations." Webpage: http://www. cis. upenn. edu/bcpierce/sf/current/index. html (2010).

# Answer
> 2 votes
Let's address your questions/confusions in order:

1.

> I don't see the authors working on the former equation, only the latter.

That's because $x$ doesn't matter:

* it does not occur in the postcondition ($v \leq 1$) investigated here
* it does not occur in the RHS of the equation for $v$

2.

> Why did the authors start the *wp* computation using $v\_1 \leq 1 \wedge v\_2 \leq 1$?

They state that their *safety horizon* is $2$, that is, they want to express that the safety condition holds both after $1$ step and after $2$ steps. In their notation, where $v\_i$ refers to the value of $v$ after $i$ steps, that's exactly expressed by the condition $v\_1 \leq 1 \wedge v\_2 \leq 1$.

3.

> Also, in the next step they do $v\_1 \leq 1 \wedge v\_1+0.1 a\_1 + \epsilon\_1 \leq 1$. Why did they only expand the equation on the right of the conjunction?

Because the 2nd iteration of the step function affects the variables subscripted with $2$. The LHS of the conjunction has only a $1$-subscripted variable, $v\_1$. It is thus invariant under the substitution $\[v\_2 \mapsto \_1+0.1 a\_1 + \epsilon\_1\]$ performed to compute the weakest precondition.

4. (from your 1st reply comment)

> Why didn't the authors include $v\_0$?

(a) They state in the example that $v\_0 = 0.9$, trivially satisfying $v\_0 \leq 1$ and (b) $v\_0$ is not affected by the dynamics.

5. (from your 2nd reply comment)

> Why did the author then work on both sides in the next step.

Because both sides refer to $v\_1$, which is assigned to in that step. Whence the substitution applies meaningfully to both.

---
Tags: machine-learning, programming-languages, formal-methods, hoare-logic
---


# Question
Title: Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage
Suppose $L=\\{ww^r:w\in\Sigma^\*\\}$. Already, we know that we can draw a PDA for $L$ such that accept each $w\in L$ with space complexity at least $|w|$.

My question is how is it possible to draw a PDA that accepts or rejects $w$ with space complexity $\frac{w}{C}$ for some constant $C$? Any help or hint will be appreciated.

Just one thing comes to my mind, maybe it's possible to partition $w$ into $\frac{w}{C}$ parts but at this I get stuck.

# Answer
It is (obviously) possible if $|\Sigma| = 1$ or $C = 1$.

It is also possible for $|\Sigma| \> 1$ and $C\>1$. The idea is that you can use a bigger stack alphabet to encode multiple letters at once.

For example, if $\Sigma = \\{a, b\\}$, the following PDA recognizes $L$, and the stack is at most $\frac{|w|}2$ for an input $w$. Here, $\Gamma = \\{Z\_0, A, B, C, D, E, F\\}$, and $X$ designates any stack symbol.

The idea is that stack symbols $C$, $D$, $E$ and $F$ represent $aa$, $ab$, $ba$ and $bb$ respectively.
> 3 votes

---
Tags: formal-languages, context-free
---


# Question
Title: algorithm to categorize courses into academic degree requirements?
In most US universities, undergraduate students must satisfy the requirements of a degree program in order to graduate. The general rules are:

* The university has a minimum number of total credits needed, and a series of subject-based baskets (e.g. sciences, humanities, writing, etc) with their own minimum credit counts.
* A program (e.g. biology, art history, etc) has a list of required courses, plus one or more baskets of degree-related topics with their own minimum credit counts.
* Each course counts for a fixed number of credits and fits in one or more of the above categories (e.g. some could potentially be counted in more than one degree-related and/or subject-based basket).
* Each course can only be counted towards a single basket at a time (cannot be shared or divided to satisfy multiple requirements, but could be moved to another basket if eligible).

Given students completing arbitrary lists of courses, is there a fast (O(n^2) or lower) deterministic algorithm to find when a given student first completes enough courses to satisfy their degree requirements (i.e. efficiently arrange the completed courses to fill all baskets while minimizing the number of credits exceeding the minimums)? If not, is there a commonly-used algorithm believed to reduce the number of cases where its basket-filling choices are inefficient?

1. If a course only satisfies one basket, put it there.
2. ?
3. Graduate!

# Answer
> 1 votes
I'm assuming we're testing if a student satisfies the requirements for a specific degree, not whether it satisfies *any* degree.

If so, we can immediately calculate the total number of credits, and whether all required courses have been satisfied with a single loop over the completed courses, using a hashset of required courses that we remove from the set when completed, checking that it is empty after the loop.

The only interesting question is allocating courses to baskets. Unfortunately, this problem is very much NP-hard in general. Even if we remove the limitation that some courses can only be put into certain baskets, and even if each basket required the same number of credits you'd still have a decision variant of the bin covering problem.

---
Tags: algorithms, classification, packing
---


# Question
Title: Find minimum of a function only knowing the ordering of a set of input points
Suppose I have a function $f: \mathbb{R}^n\rightarrow\mathbb{R}$. All I know about the function is, I have a set of pairs of vectors ($\vec{v}\_a$, $\vec{v}\_b$) for which I know which one is greater (i.e. I know that $f(\vec{v}\_a)\>f(\vec{v}\_b)$). I want to find the minimum of the function (or at least a good approximation). What is a way in which I could compute an approximation for the input for which the function is minimal, only given a set of pairs of vectors for which I know the ordering?

Edit: As a lot of people have pointed out, $f$ is not constrained enough. With the "All I know about the function" line, I've kind of overgeneralized my problem. I'm pretty much certain my mystery function is both continuous and differentiable. I'm willing to just assume that about my function.

# Answer
> 6 votes
You can't. The function could be anything. For example, consider

$$f(x) = \begin{cases} g(x) &\text{if }x \ne \alpha\\ -10^{100} &\text{if } x = \alpha \end{cases}$$

where $\alpha \in \mathbb{R}^n$ is some obscure point (maybe very far from the origin). Then any reasonable algorithm might never evaluate $f$ on $\alpha$ and in that case will have no hope of finding the minimum.

You need additional structure on the function (e.g., that it come from a particular class of functions with nice properties) to be able to say anything. The best algorithm will depend on the specifics of that structure. (Just saying "somewhat well-behaved" is not specific enough to allow a good solution.) There is no free lunch.

---

Another approach might be to use Bayesian optimization. In this approach, we try to fit an inferred function $f^\*$ that seems consistent with the observations, and then apply optimization to $f^\*$. More precisely, we infer a conditional distribution on $f^\*$, conditioned on the observations, and then use that distribution to figure out what is the best next value of $x$ to evaluate $f$ on.

The existing methods for Bayesian optimization assume that you have a way to observe the value of $f$ at specific points $x$, not just to compare pairs of outputs, so those methods can't be applied directly to your problem. It might be possible to extend existing methods to handle observations of the form you have. The Bradley-Terry model might also be helpful: you might be able to learn a model $g:\mathbb{R}^n \to \mathbb{R}$, e.g., a neural network, such that $f(x\_1)$ is predicted by this model to be larger than $f(x\_2)$ with probability $e^{g(x\_1)}/(e^{g(x\_1)}+e^{g(x\_2)})$, and then fit $g$ to maximize the likelihood of the observations.

This all sounds terribly speculative, and it will probably easier to find a way to gather more data, e.g., to observe the actual value of $f(x)$, rather than just obtaining pairwise comparisons.

# Answer
> 2 votes
The answer by @D.W. is correct that any search space will need *some* structure in order to make progress. However, I think it would be pessimistic to conclude that the No Free Lunch theorems apply; since they assume uniform sampling from the space of all functions, which is unrealistic.

For example, it seems reasonable to limit ourselves to solving *computable* functions; and at least those are enumerable! It also seems reasonable to bias in favour of simple functions rather than complex ones (to avoid over-fitting, etc.), although there's lots of room to argue about the details of this.

My first thought is to Universal Search, which is about the best we can do for *inverting* a black-box function $f$ on a given output $y$. It searches for an $x$, in order of increasing complexity, until it finds one such that $f(x) = y$. Your problem has more structure than this, but a naive approach could use Universal Search to find an approximation of your function, e.g. a program $p$ such that $\bigwedge\_{(a,b) \in V} eval(p, a) \> eval(p, b)$ for the given set of constraints $V$. Note that your choice of language for $p$ (and corresponding implementation of $eval$) determines what counts as "simple", as the complexity measure being minimised is $length(p) + log(\sum\_{(a,b) \in V} time(eval(p, a)) + time(eval(p, b)))$. Traditionally Universal Search uses a Turing-complete programming language (e.g. Binary Lambda Calculus, if you want a "nothing up my sleeve" language); but that is usually impractical for real workloads, and can be weakened to some less-expressive (and hence more structured) model, like ANNs, polynomials, etc. making the approach more like Minimum Description Length.

Once an approximation has been found, you can try minimising *that* using standard (white-box) optimisation procedures, and use that value as a (very!) approximate minimum for your original, unknown function. Note that your choice of optimisation method may also impose more assumptions on your search space (e.g. continuity, differentiability, etc.).

---
Tags: optimization, gradient-descent, topological-ordering
---


title: Is the $L'$ regular or not?

text:
# Question
Title: Is the $L'$ regular or not?
Suppose $L$ is regular and we define $L'=\\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\\}$. Could we conclude that $L'$ is regular or not?

I think it's not regular because if $L=a^\*b^\*c^\*$ then $L'$ could be $a^nb^nc^n$ so it can't be regular.

# Answer
> 1 votes
I think it's actually regular. Suppose $L$ is recognised by the DFA $A = (Q, \Sigma, \delta, q\_0, F)$, define the NFA $A' = (Q, \Sigma, \delta', q\_0, F)$ s.t.

$$\delta'(q, a) = \\{\delta(q, a)\\} \cup \\{q\\}$$

for all $q \in Q, a \in \Sigma$. Intuitively, you can think of $A'$ as being the same as $A$ with the addition that each state can reach itself using any character. It is easy to see, that $$(q, x) \vdash\_{A'}^\* (q, \varepsilon)$$ for all $q \in Q, x \in \Sigma^\*$ and $$(q, ax) \vdash\_{A'} (q', x) \iff (q, ax) \vdash\_A (q', x)$$ for $q' \neq q \in Q, a \in \Sigma$. Using these properties it can be verified that $$w = w\_1w\_2...w\_n \in L(A)\iff a\_0w\_1a\_1w\_2...w\_na\_n \in L(A')$$ for some $a\_i \in \Sigma^\*$. Thus $L' = L(A')$ must be regular.

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


# Question
Title: Strange notation in the article about sparse self-attention
While reading an article devoted to the sparse self-attention, I came across a notation that was not very clear:

$$ Attend(X, S) = \Big( a(x\_i, S\_i) \Big)\_{i∈{\\{1,...,n}\\}} $$

What means $\Big( \space \space \Big)\_{i∈{\\{1,...,n}\\}}$ ?

It would be great to describe this in more detail.

Link to the article (page 4): https://arxiv.org/pdf/1904.10509.pdf

Please Help!

Thank You for your answers.

# Answer
The notation

$$(x\_i)\_{i \in \\{1,\dots,n\\}}$$

is short-hand for

$$(x\_1,x\_2,\dots,x\_n).$$

Just two different ways to write the same thing.

It is analogous to the relationship between $\sum\_{i \in \\{1,\dots,n\\}} x\_i$ and $x\_1 + x\_2 + \dots + x\_n$. Two different ways to write the same thing.
> 1 votes

---
Tags: machine-learning, linear-algebra, natural-language-processing
---


# Question
Title: Big-O time complexity for this code snippet
```
public void m1(int n) {
   sum = 0;
    for (int i = n/2; i <= n; i++) {
        for (int j = 1; j <= n; j = 2 * j) {
            for (int k = 1; k <= n; k = k * 2) {
                 sum++;
            }
        }
    }
}

```

So, I know that the innermost loop and second loop are $\log(n)$ and the outermost loop is essentially $O(n)$, so that means $O(n\log(n)\log(n))$. But I am lost on what to do next. I am between $O(n^2 \log(n))$ and $O(n \log^2(n))$. Can someone tell me which is right and explain why?

# Answer
You are right, the two innermost loops perform $\Theta(\log n)$ iterations each, so we have a total of $\Theta(\log^2 n)$ iterations, which are repeated $\Theta(n)$ times in the outer loop, which implies that we have a total of $\Theta(n\log^2 n)$ iterations.

You just have to multiply the number of iterations of each loop since they are nested and all the iterations are performed without interruptions (we just increase a variable inside the loop). So we can not only give an upper-bound ($O(n\log^2 n)$ ) but also a lower-bound ($\Omega(n\log^2 n)$), which implies a complexity of $\Theta(n\log^2 n)$.
> 5 votes

---
Tags: complexity-theory, time-complexity, asymptotics, java
---


# Question
Title: Is a Convolutional Neural Net a special case of DNN? If so, how can the convolutional layer be modelled?
In literature, Convolutional Neural Nets (CNNs) are presented as a special case of Deep Neural Nets (DNNs) (e.g., here). I do not understand how the convolutional layer can be implemented through a layer of neurons though. As far as I understand, a $n \times m$ kernel is used to calculate a single output feature over a combination of $n \cdot m$ input features in a certain stride. I see how this could be implemented as a layer in a Deep Neural Network, where basically $n \cdot m$ input features are the inputs for one output neuron, respectively. However, how would we ensure during training, that all the output neurons corresponding to the same kernel have the same weights for their inputs?

Is it not the case that CNNs are a generalization of DNNs rather than the other way around?

# Answer
> 0 votes
You're reading too much into the phrasing 'special case'. You already accurately understand the sense in which a CNN can be considered as a special case of a DNN; it is a DNN where many of the weights are repeated. Here people are probably referring to the model that is produced by the training procedure: every CNN could be expressed as a DNN with a particular pattern of repeated weights. This means that any function that can be computed by a CNN, can also be computed by a DNN. Don't worry about the rest, no one means anything more than that.

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


# Question
Title: How do I go about creating a mapping reduction?
So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated questions trip me up such as the following...

A and B are computable languages where B is non trivial give a mapping reduction from A to B.

So my thought process with this question is that the reduction must have something to do with the fact that B is non trivial, but I'm not sure.

Any help understanding mapping reductions and this question would be appreciated!

# Answer
Language C is non-trivial if both C and its complement are non-empty. If A is non-trivial and B is trivial, there cannot be a reduction from A to B.
> 0 votes

---
Tags: reductions
---


title: smoothness test

text:
# Question
Title: smoothness test
An integer is $k$-smooth if its prime factors are at most $k$. In the case where $k$ is not tiny (say $10^8 \< k \< 10^{10}$), are there algorithms to test for $k$-smoothness, other than trying every prime up to $k$?

Context:

(1) The largest component $p^a$ of an odd perfect number is known to be greater than $10^{62}$.

(2) The largest prime of an odd perfect number is known to be greater than $10^8$.

Does (1) imply something stronger or weaker than (2)?

Let $LPF(n)$ denote the largest prime factor of $n$ and let $\sigma(n)$ denote the sum of the divisors of $n$.

I am interested in the minimum of $\max(p,LPF(\sigma(p^a)))$, where $p$ is prime and $p^a \> 10^{62}$. We may also assume that $a$ is even since it should not be too hard to show that on odd perfect number has a component greater than $10^{62}$ that is distinct from the special component. Here is an inefficient PARI code.

forprime(p=3,10^9,a=2; while(p^a \< 10^62, a+=2); while(p^a \< 10^90, f=factorint(sigma(p^a),1); s=vecmax(f\[, 1\]); if(s \< 10^9, print(\[p, a\])); a+=2);)

# Answer
The standard approach is to use a factoring algorithm designed to find small factors. The state-of-the-art algorithm for that is elliptic curve factoring (ECM). Its running time is a function of the size of the smallest factor, so it is particularly useful when trying to find small factors. I expect you should be able to find all 10-digit factors efficiently using the ECM algorithm.

Trial division is another option, and is very simple to implement. Pollard's p-1 factoring algorithm is better than trial division at finding small, but ECM is even better still.
> 1 votes

---
Tags: algorithms, arithmetic
---


# Question
Title: Why can't we prove closure under concatenation using DFA?
I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to determine that we now have to transition from string of one language to another language. I still don't have a clear understanding of this statement.

# Answer
> 2 votes
My only copy of Sipser is the third edition. Here is the relevant quote, after Theorem 26, closure under concatenation of the regular languages.

> To prove this theorem, let’s try something along the lines of the proof of the union case. As before, we can start with finite automata $M\_1$ and $M\_2$ recognizing the regular languages $A\_1$ and $A\_2$. But now, instead of constructing automaton $M$ to accept its input if either $M\_1$ or $M\_2$ accept, it must accept if its input can be broken into two pieces, where $M\_1$ accepts the first piece and $M\_2$ accepts the second piece. The problem is that $M$ doesn’t know where to break its input (i.e., where the first part ends and the second begins). To solve this problem, we introduce a new technique called nondeterminism.

There is not much to add here. To verify that string $w$ is in the concatenation $A\_1\cdot A\_2$ of two regular languages that are specified by their automata $M\_1$ and $M\_2$ we have to find a split $w=x\cdot y$ such that $x$ is accepted by $M\_1$ and $y$ is accepted by $M\_2$. For the first part we simulate $M\_1$ for the second $M\_2$. As we do not know where to split, nondeterminsim can be employed: at some point in $w$ when we are in a final state of $M\_1$ we move to the initial state of $M\_2$.

So nondeterminism is a suitable tool. However that does *not* mean we cannot prove closure under concatenation using deterministic automata. We can use a deterministic simulation, not keeping track of a single split $w=x\cdot y$ that was nondeterministically chosen, but in parallel simulating *all* those splits. Technically that would mean keeping a set of states of $M\_2$ in memory along with a state of $M\_1$.

Although possible, this is not a feasible approach for a didactical book: such a proof incorporates the construction that turns a nondeterministic automaton into a deterministic one.

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


# Question
Title: What is wrong with this finite tape attack on the folklore proof of the halting problem?
Crank disclaimer: I don't doubt the undecidability of the halting problem, but one proof confuses me.

We have seen this folklore proof of the halting problem on several occasions.

Assume a HALTING SOLVER ($HS$) exists with argument program $P$ and it returns true iff $P$ halts.

Let SMART PROGRAM ($SP$) do the following: call $HS$ with argument its source and do the opposite of the answer, i.e. if $HS(SP)=True$, $SP$ returns immediately, contradicting the correctness of the $HS$.

We believe this proof if false, because it doesn't need infinite tape of the turing machine and the halting problem with finite tape is decidable.

Attack on the folklore proof.

Apply the proof to a machine with finite tape, it implies the problem is undecidable, but it is known that the HP problem for finite tape is decidable and we have contradiction.

> Q What is wrong with this contradiction?

In the real world, antivirus programs try to recognize computer viruses and some of the viruses try to circumvent being analyzed, e.g. if they are run in a debugger or a virtual machine they exit, not showing malicious behavior.

# Answer
Your confusion comes from not being careful enough with the quantifiers regarding the tape bound.

Let's keep track of memory requirements in the construction. Let's assume that $HS$ uses up to $M(s)$ many cells of the tape for inputs of size $s$, and moreover, let us assume that the code of $HS$ has size $h$. Then $SP$ uses about $M(h)$ cells (which doesn't depend on its input), and $HP$ gets it wrong.

This tells us the following: For every potential Halting decider $H$ there is a TM $M$ using constant memory $C$ (ie not depending on $M$'s input, but depending on $H$!) such that $H$ is wrong on input $M$.

On the other hand, decidability of the bounded Halting problem is the following: For every memory bound $C$ there is a potential Halting decider $H$ that gets all inputs correct which use no more than $C$ cells of the tape.

The first statement has the logical form $\forall H \ \exists C \ \neg \Psi(H,C)$, the second has the logical form $\forall C \ \exists H \ \Psi(H,C)$. There is no contradiction here.
> 2 votes

---
Tags: halting-problem
---


# Question
Title: Is bitonic sort order preserving on keys with the same value?
We are all familiar with Bitonic Sort. The computations are predetermined and data-independent.

Let's say we have a table `A = [ 1,3,2,5,6,3,3,21 ]`. The output after performing the sort is: `A [ 1,2,3,3,3,5,6,21 ]`.

Observe that we have three entries with value `3` in indexes `1,5, and 6`. My question is: After bitonic sort, is this ordered preserved? Meaning the element from index `1` will always appear before the other two, etc.?

# Answer
> 1 votes
No.

Consider an input of $n$ ones followed by $n$ zeroes to the bitonic network. This input is only affected by the network in the middle stage, where the order of elements is flipped. Thus the elements do not keep their relative order. Rather, for this input, the order is flipped.

However, the order is not flipped in general. If the input is all zeroes, the entire network is a no-op and the output is equal to the input, preserving the order of bits. Hence the bitonic sorting network cannot be considered stable.

---
Tags: algorithms, algorithm-analysis
---


title: How fast can we make generalized k-SAT?

text:
# Question
Title: How fast can we make generalized k-SAT?
Suppose a generalized version of k-SAT where the usual clauses (disjunctions of literals) are generalized to arbitrary Boolean functions of k variables. (For example, $(x \oplus (y \land z)), ((x \land z) \lor (y \land z))$ and $(x \implies z)$ could be generalized clauses for k = 3.)(Just a note: there are $2^{2^k}$ Boolean functions of k variables, and only $3^k$ of them are disjunctions of literals.)

My question is how fast can we solve the satisfiability for such formulas? Would you Provide an research paper that gives an algorithm for this problem and also gives us proof an upper bound on its running time . If, we can use randomness, (i) for example, k = 3, (ii) any arbitrary k.

# Answer
> 3 votes
Worst-case bounds on running time are usually not very informative for SAT solvers. In particular, on problem instances that arise in practice, often SAT solvers run a lot faster than the bounds would suggest. And the bounds are not very informative at helping us choose between two solvers or two algorithms, or identify which improvements are likely to help the most in practice.

In practice, the pragmatic approach is probably going to be to convert each "generalized clause" (i.e., each formula of k variables) to CNF using the Tseytin transform, then form a CNF formula $\varphi$ via the conjunction of all of the formulas obtained in this way, and solve $\varphi$ with an off-the-shelf SAT solver. This allows you to take advantage of all of the engineering in SAT solvers, which often make a big difference in practice, rather than starting from scratch.

---

If you care about worst-case running time bounds, a natural approach is to apply the method suggested by Emil Jeřábek. Specifically, convert each "generalized clause" to a CNF formula without introducing any new variables, then consider the conjunction $\varphi$ of those formula, and apply any existing SAT algorithm with worst-case running time bound to $\varphi$. This way, any worst-case running time bounds for SAT transfer immediately to your problem, too. Each "generalized clause" $C$ on $k$ variables can be converted to a CNF $\psi\_C$ containing at most $2^k$ clauses. Each of those clauses has at most $k$ variables in it. Therefore, $\varphi = \land\_C \psi\_C$ is a $k$-CNF formula with $n$ variables, and can be solved with any algorithm for $k$-SAT.

For instance, 3SAT can be solved in $O^\*(1.308^n)$ expected time using the PPSZ algorithm, so for $k=3$ it follows that your problem can be solved in $O^\*(1.308^n)$ time, too. See

3-SAT faster and simpler---Unique-SAT bounds for PPSZ hold in general. Timon Hertli. SIAM J. Computing, vol 43 no 2, pp.718-729.

---
Tags: complexity-theory, satisfiability, 3-sat, constraint-satisfaction, sat-solvers
---


# Question
Title: Covering a graph with M cliques maximizing total edges weight
I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes negative interactions between the supplements. Each interaction between the supplements is known beforehand (positive, neutral or negative: see the image below).

I'm seeking advice on the mathematical formulation of this problem and potential algorithms or tools that could be used to solve it. Here's what I came up with:

* We can build a graph G from table of compatibility, with edges 1/0/-1 for positive, neutral and negative interactions correspondingly
* Then we can remove -1 edges completely
* Now we have modified graph G' with 0/1 edges only (see the image below)

* And we want to cover it with M cliques (bc clique in this graph will guarantee no 'bad' connections), finding a coverage with maximum number of +1 green edges

This method is not very good because:

* it doesn't consider using -1 red edges at all while building meals
* it has a very big time complexity (hours or days for 1 calculation on ~20 supplements)

I'm open for any suggestions. Maybe there are existing algorithms for solving this problem, or tools (like solvers)? Or is there a name for this problem I could search algorithms for?

# Answer
> 1 votes
One approach is to solve this with tools from operations research and combinatorial optimization, and specifically, to view this as an instance of ILP or SAT.

Let $x\_{c,i}$ be a variable that will be true (i.e., 1) if supplement $i$ is assigned to meal $c$, or false (0) otherwise. Let $y\_{c,i,j} = x\_{c,i} \land x\_{c,j}$. Let $r\_{i,j}$ be the reward if supplements $i,j$ are used in the same meal ($+1$ if they interact positively, $0$ if there is no interaction, $-1$ if they interact negatively). Then your goal is to maximize $\sum r\_{i,j} y\_{c,i,j}$, subject to constraints that require $x$ to be a valid solution.

These constraints can be expressed in SAT or ILP pretty easily:

* Exactly one of $x\_{c,i}$ is true, for each $i$. (In ILP: $\sum\_c x\_{c,i} = 1$. In SAT, this is a 1-out-of-M constraint.)
* $y\_{c,i,j} = x\_{c,i} \land x\_{c,j}$. (In ILP: see Express boolean logic operations in zero-one integer linear programming (ILP). In SAT, this is $(x\_{c,i} \lor \neg y\_{c,i,j}) \land (x\_{c,j} \lor \neg y\_{c,i,j}) \land (\neg x\_{c,i} \lor \neg x\_{c,j} \lor x\_{c,i,j})$.)

Then you can use a SAT solver that supports pseudo-boolean constraints (e.g., Z3) or an ILP solver (e.g., Cplex, Gurobi) to solve this system. If you use a SAT solver, you might want to use binary search over the target value of the objective function, using the SAT solver to search for a solution that achieves that target.

(Optionally, you can add some additional constraints for symmetry breaking, e.g., WLOG you can force $x\_{1,1}$ to be true, force $x\_{1,2} \lor x\_{2,2}$ to be true, etc.)

If $N,M$ are big enough, this won't work, but it might be a simple to implement approach if $N,M$ aren't too big.

---
Tags: algorithms, graphs, optimization, combinatorics, partitions
---


title: Proof that $NP \cap coNP = P$

text:
# Question
Title: Proof that $NP \cap coNP = P$
Suppose I want to prove that $NP \cap coNP = P$. Since clearly $P\subseteq NP \cap coNP$, I need to prove the opposite direction, i.e., *every* problem in $NP \cap coNP$ has a polynomial-time algorithm. Is there a shorter way to prove this equality than arguing about *all* problems in $NP \cap coNP$?

One obvious way would be to find a polynomial-time algorithm for SAT, since this would imply $P=NP$ and therefore also $NP \cap coNP = P$. But I am looking for an easier way.

In particular, **is there a problem $X$ that is not NP-complete, but complete for $NP \cap coNP$?** If such a problem exists, then an algorithm for $X$ would imply $P\subseteq NP \cap coNP$.

# Answer
As mentioned by D.W., asking for a complete problem for $\mathrm{NP} \cap \mathrm{coNP}$ is going to be messy. However, for the purpose of *"Can I work on a polytime algorithm for this concrete problem in an attempt to prove $\mathrm{NP} \cap \mathrm{coNP} = \mathrm{P}$?"*, we do have options available to us. We just need to look beyond total decision problems.

For example, consider the following computational problem $A$: Given two $\mathrm{SAT}$-instances $\phi\_0,\phi\_1$ subject to the promise that exactly one of them is satisfiable, decide which one is.

Or, if you prefer multivaluedness over partiality, we can consider the problem $B$ defined as: Given two $\mathrm{SAT}$-instances $\phi\_0,\phi\_1$, compute some $i \in \\{0,1\\}$ such that if $\phi\_{1-i}$ is satisfiable, then so is $\phi\_i$.

**Claim:** A total decision problem is polytime many-one reducible to $A$ if and only if it is polytime many-one reducible to $B$ if and only if it belongs to $\mathrm{NP} \cap \mathrm{coNP}$.

So, a polytime algorithm for $A$ (or equivalently, $B$) implies $\mathrm{NP} \cap \mathrm{coNP} = \mathrm{P}$, and in some sense, is not much stronger than it.
> 5 votes

# Answer
So far we don't know of any problem that can be proven to be complete for $NP \cap coNP$. See https://cstheory.stackexchange.com/q/49/5038 and https://mathoverflow.net/q/34889/37212 for extended discussion of some of the challenges, related results, and a few entry points into the literature.

Related: What do we know about $NP \cap co-NP$?, Complete problems in NP∩coNP.
> 3 votes

---
Tags: np-complete, co-np
---


# Question
Title: Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic programming since most of the time we are recursively calculating a function $f$.

Let's suppose this function $f$ has $3$ parameters. This function $f$ represent all the subproblems of the problem we want to solve.

Moreover we have a nice recursive definition of $f$, so we are able to link the subproblems between each other and understand how a certain subproblem can help calculating an other subproblem.

Now suppose that the first parameter of our function $f$ can't take a value larger than $n\_1$, the second also can't take a value larger than $n\_2$ and the third parameter can't take a value larger than $n\_3$. Supposing that calculating $f(i,j,k)$ takes $\mathcal{O}(m)$ then the complexity of our program is : (since it's essentially means we have $ n\_1 \cdot n\_2 \cdot n\_3$ subproblems and each of these takes $m$ operations of constant cost to calculate)

$$\mathcal{O}(m \cdot n\_1 \cdot n\_2 \cdot n\_3)$$

Now here comes my problem. If my program wants to calculate the maximum value of something then I can for example do the following :

$$f(i,j,k) = \max\\{ f(i+1,j,k) + 1, f(i+1,j,k)\\}$$

The problem is that this is not tail recursive. So in order to make the program tail recursive an idea could be to add a forth paramters to the function $f$, hence now we have :

$$f(i,j,k,l) = \max\\{f(i+1,j,k,l+1), f(i+1,j,k,l)\\}$$

This way the function $f$ is tail recursive.

Yet, my question is : making the function $f$ tail-recursive adds a $4$-th paramaters and hence increase the number of subproblems, so the complexity of our function is now increased (see what I said above about the complexity of a dynamic program), and hence tail recursion is bad on dynamic programs ?

Thank you.

# Answer
> 0 votes
I can tell yes... It is not working fine but you can go for some work around that I may not be preferable with. But recently I was working with 0/1 knapsack problem where If I go with the tail recursion approach or the head recursion approach that result it gives is correct. But If I try to apply DP(Dynamic Programming) in it. It is failing in the scence giving the wrong answer. let me give a sample input here

```
int n = 7;
vector<int>  weight = {6, 5, 1, 5, 6, 5, 9};
vector<int>  value = {5, 3, 4, 9, 6, 1, 1};
int maxWeight = 13;

```

If I use 2-D vector as my DP array to optimise it. I will paste the code below but here is now the function call and the values in DP are getting stored for this example I am taking the index of the weight vector and the maxWeight values f(0,13)-\>f(2,7)-\>f(2,2)-\>f(3,1)-\>f(4,1)-\>f(5,1)-\>f(6,1) and when returning back it start to store in dp like dp\[6,1\] = 12-\>dp\[5,1\] = 12-\>dp\[4,1\] = 12-\>dp\[3,1\] = 12-\>dp\[2,2\] = 12..... But it should not get stored in this way this is the problem with tail recursion where the result is also passed with the function so that the state changes are not captured correctly If you work out the full example we will get a clear clarity.

where as in the head recursion the ans or the result is not going to be returned that value will get added up as you can see in the below code so these mismatch of state won't occur.

```
#include <bits/stdc++.h>
using namespace std;

int kps_tail_rec(vector<int> &weight, vector<int> &value, int i, int &n, int maxWeight, int ans, vector<vector<int>> &dp) {
     cout<<"start of func - > i= "<<i<<", maxWeight= "<<maxWeight<<endl;
    if (i == n || maxWeight == 0)
        return ans;

    if (dp[i][maxWeight]){
        cout<<"i= "<<i<<", maxWeight= "<<maxWeight<<" , dp[i][maxWeight] = "<<dp[i][maxWeight]<<endl;
        return dp[i][maxWeight];
    }

    int taken = 0, nottaken = 0;

    if (weight[i] <= maxWeight) {
        taken = kps_tail_rec(weight, value, i + 1, n, maxWeight - weight[i], ans + value[i], dp);
    }

    nottaken = kps_tail_rec(weight, value, i + 1, n, maxWeight, ans, dp);
    cout<<"for this i and maxWeight"<<i<<", "<<maxWeight<<"taken= "<<taken<<", nottaken= "<<nottaken<<endl;
    return dp[i][maxWeight] = max(taken, nottaken);
}
int kps_head_rec(vector<int> &weight, vector<int> &value, int i, int &n, int maxWeight, vector<vector<int>> &dp) {
    cout<<"start of func - > i= "<<i<<", maxWeight= "<<maxWeight<<endl;
    if (i == n || maxWeight == 0)
        return 0;

    if (dp[i][maxWeight]){
        cout<<"i= "<<i<<", maxWeight= "<<maxWeight<<" , dp[i][maxWeight] = "<<dp[i][maxWeight]<<endl;
        return dp[i][maxWeight];
    }

    int taken = 0, nottaken = 0;

    if (weight[i] <= maxWeight) {
        taken = value[i] + kps_head_rec(weight, value, i + 1, n, maxWeight - weight[i], dp);
    }

    nottaken = kps_head_rec(weight, value, i + 1, n, maxWeight, dp);
    cout<<"for this i and maxWeight"<<i<<", "<<maxWeight<<"taken= "<<taken<<", nottaken= "<<nottaken<<endl;
    return dp[i][maxWeight] = max(taken, nottaken);
}

int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) {
    vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0));
    cout << kps_tail_rec(weight, value, 0, n, maxWeight, 0, dp)<<"  , ";
    cout<<" now going for the 2nd approch\n";
    vector<vector<int>> dp1(n + 1, vector<int>(maxWeight + 1, 0));
    cout << kps_head_rec(weight, value, 0, n, maxWeight, dp1);
    return 0;
}

int main() {
    int n = 7;
    vector<int>  weight = {6, 5, 1, 5, 6, 5, 9};
    vector<int>  value = {5, 3, 4, 9, 6, 1, 1};
    int maxWeight = 13;
    int result = knapsack(weight, value, n, maxWeight);
    return 0;
}

```

Summary : In recurrsion both tail and head gives the same value but when we Optimise with DP going with Head recursion is a better option. enter code here

---
Tags: algorithms, algorithm-analysis, runtime-analysis, dynamic-programming, tail-recursion
---


# Question
Title: prove that in binary heap buildheap function does at most 2N-2 comparison
prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks.

buildheap procedure: we have n element and we build a heap at first and then we start from the first node which is not leaf(floor of n/2) and for each step we have 2 comparison(each node should be compared with min of children and to find min also there is 1 comparison) so we compare this node and we go back until we get to root(and all of these steps are recursive and keeps continuing till we reach the node or right place of node)

```
buildheap():
    for i ← size / 2 till i > 0
        Max-Heapify(i)
        i ← i-1

Max-Heapify(A, i):
    left ← 2×i
    right ← 2×i + 1
    largest ← i

    if left ≤ length(A) and A[left] > A[largest] then:
        largest ← left

    if right ≤ length(A) and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
        Max-Heapify(A, largest)

```

I wrote number of comparisons:

```
node          comparison
 1                 0
 2                 1
 3                 2
 4                 3
 5                 6
 6                 7
 7                 8
 8                 11
 9                 14

```

I think the worst case is when we have new level with one node(3,5,9,.. node because it has 2 less than the most we have)

but I have another idea:

we have n/2 node which don't move down

n/4 moves one level down

n/8 moves 3 level down

and each moving from level to level needs 2 comparison so we have

$\frac{n}{2} \times 0 + \frac{n}{4} \times 1 + \frac{n}{8} \times 2 + .... = n \times (\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$

sum of $(\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$ is $1$ and it will be multiplied by 2(because of 2 comparison for each move) but we have 2n here not 2n-2

did I make a mistake or the idea is wrong?

# Answer
> 2 votes
Floyd's method of constructing a heap consists of applying *heapify* on all non-leaf nodes. Running heapify on a node $v$ costs twice the height of the subtree rooted at $v$ (where the height of a leaf is 0), with only one exception: if the unique deepest path terminates at an only child, then the cost is twice the height minus 1.

Consider now a heap on $n$ elements, and suppose that $2^h \leq n \< 2^{h+1}$. Let us first compute the total number of comparison when ignoring the very last level. In other words, we are considering the case of a complete binary tree with $h$ levels, containing $2^h-1$ nodes in total. The total sum of heights is $$ (h-1)2^0 + (h-2)2^1 + (h-3)2^2 + \cdots + 1\cdot 2^{h-2} + 0\cdot 2^{h-1} = \\ (2^0 + 2^1 + \cdots + 2^{h-2}) + (2^0 + \cdots + 2^{h-3}) + \cdots + (2^0) = \\ (2^{h-1} - 1) + (2^{h-2} - 1) + \cdots + (2^1 - 1) = \\ 2^h - h - 1. $$ The total number of comparisons is twice that.

The actual heap contains $m = n - 2^h + 1$ nodes at level $h+1$. These increase the sum of heights by 1 for each node which contains one of these $m$ nodes as a descendant. At depth $d$ (where the root is depth zero), there are $\lceil m/2^{h-d} \rceil$ such nodes. This shows that if $n$ is odd, the number of comparisons is exactly $$ 2(2^h-h-1) + 2\sum\_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil. $$

If $n$ is even, then there are some nodes in which the unique deepest path terminates at an only child. To determine how many, let us denote by $x$ the odd leaf. The node $x$ is always the unique child of its parent. Going one level up, $x$ is the unique node at depth 2 iff $n$ is divisible by 4. Continuing in this way, it is not hard to check that if $2^r$ is the largest power of 2 dividing $n$, then the number of such nodes is $r$, and so we have to subtract $r$ from the above formula: $$ 2(2^h-h-1) + 2\sum\_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil - r. $$ We can simplify this formula using $2^h/2^{h-d} = 2^d$, to get $$ 2\sum\_{d=0}^{h-1} \left\lceil \frac{n+1}{2^{h-d}} \right\rceil - 2h - r. $$ Replacing the ceiling with a floor and changing the order of summation, this simplifies to $$ 2\sum\_{d=1}^h \left\lfloor \frac{n}{2^d} \right\rfloor - r. $$ This is always at most $$ 2\sum\_{d=1}^h \frac{n}{2^d} \< 2n, $$ and so at most $2n-1$. In fact, the same argument shows that the sum itself is less than $n$, and so at most $n-1$, hence the number of comparisons is at most $2n-2$.

We can also get a more explicit expression for this quantity. Let the binary expansion of $n$ be $b\_h b\_{h-1} \ldots b\_0$, where $b\_h = 1$. The sum equals $$ (b\_h \ldots b\_1)\_2 + (b\_h \ldots b\_2)\_2 + \ldots + (b\_h)\_2 = \\ b\_h (2^{h-1} + \cdots + 1) + b\_{h-1} (2^{h-2} + \cdots + 1) + b^0 (0) = \\ b\_h (2^h - 1) + b\_{h-1} (2^{h-1} - 1) + \cdots + b\_0 (1 - 1) = \\ n - (b\_h + \cdots + b\_0). $$ Thus, if we denote by $\sigma$ the sum of all digits in the binary representation of $n$, then we get $$ 2n - 2\sigma - r, $$ a formula also appearing on Wikipedia. Since $\sigma \geq 1$, this is always at most $2n - 2$.

# Answer
> 0 votes
we're focusing on the final step of the process. At this point, we assume that the two child heaps are already built and properly organized. The cost to "fix" the heap at this stage is given as 2logn -2 (the last 2).but Additionally, we need to include the cost of the two children. total :T(n)=2T(n/2)+2(log(n)-1) -\> 2n-log(n)-2 here: Solving T(n) = 2T(n/2) + log n with the recurrence tree method

```
                             root 2((logn)-1)
          fixed heap(2(logn/2)-1)         fixed heap(2(logn/2)-1)

```

---
Tags: algorithms, data-structures, binary-trees, heaps, heap-sort
---


title: What does empty string ε actually mean?

text:
# Question
Title: What does empty string ε actually mean?
I came across this weird expression while learning about regular expressions.

$R^+ \cup \varepsilon = R^\*$

why does doing union with an empty string makes this regex go from 1 or more to 0 or more?

# Answer
> 6 votes
Regular expressions represent sets of strings, so $\varepsilon$ in that expression represents the set that contain only the 0 length string, $\\{\varepsilon\\} $. This of course is not the same as the empty set $\emptyset$, so the union will add the empty string to the set that does not contain an empty string ($R^+$) , hence the regular expression $R^\*$ is the set of strings that contains 0 length (empty) string and non-zero length string.

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


# Question
Title: Proving the correctness of a sorting algorithm that contains a whole loop
I am preparing for my algorithm and data structures exam. In the code below, I need to prove the correctness of tripSort for arrays of a size \>=3. I am trying to do that by using loop invariants. The subarray A\[n-2j+1,n\] is the loop invariant I chose, where j refers to the iterations of the while loop. Is this the correct way to prove the correctness?

```
 public static boolean threeSort(int[] arr) {
    boolean changed = false;
    if (arr[0] > arr[1]) {
        swap(arr, 0, 1);
        changed = true;
    }
    if (arr[0] > arr[2]) {
        swap(arr, 0, 2);
        changed = true;
    }
    if (arr[1] > arr[2]) {
        swap(arr, 1, 2);
        changed = true;
    }
    return changed;
}

public static void tripSort(int[] A) {
    boolean done = false;
    while (!done) {
        done = true;
        for (int i = 0; i < A.length - 2; i++) {
            if (threeSort(new int[]{A[i], A[i + 1], A[i + 2]})) {
                done = false; // something changed
            }
        }
    }
}

```

# Answer
Assuming the input has at least length 3, you can do it in two steps:

1. Prove the outer loop terminates. You can do this by an argument that the total number of inversions is always non-negative, and strictly decreasing in each iteration where `done = false`, and thus the loop must terminate.
2. Prove that when the outer loop terminates, the array is sorted. You can do this with a loop invariant that while `done = true`, after the `i`th iteration you have $a\[0\] \leq \cdots \leq a\[i+1\] \leq a\[i+2\]$.
> 1 votes

# Answer
You can not prove this sorting algorithm as correct because it is not correct. Hint: what happens if the input contains two elements?
> 0 votes

---
Tags: algorithms, correctness-proof
---


# Question
Title: can a model of computation with infinitely many states be nontrivially decidable?
i'm trying to make a game in which the player faces an infinite (finitely specified) series of enemies and has to specify a strategy that provably defeats all of them (ie defeats enemy n in finite time for all n). i'm intending to do it by having the player describe their strategy in a decidable language, which is then incorporated into a larger program in that decidable language that runs the strategy against each enemy in turn, halting if the player loses. it should then be possible to determine whether that program halts.

if the language is straighforwardly a PDA then this seems like it should work, but my understanding is that a PDA only fails to halt by getting into an infinite loop. i'd like it to be possible for each enemy to be different, say, the nth enemy has n health. but in that case a winning strategy will never loop because each new enemy introduces a never-before-seen state (and also i believe a PDA struggles to represent arbitrarily large numbers, you can have one on the stack as unary or whatever but you can't compare it to others because you lose information about it by reading it? - and the specified strategy is just a fragment of a larger program that may be run repeatedly forever, so it can't read from input, this all has to be on the stack with $\epsilon$-transitions). so i'm looking for a model of computation that's nontrivial and decidable but can have a counter that goes up forever.

# Answer
A one-counter automaton is a finite-state machine that is augmented with a single counter. The finite-state machine can issue a command to increment or decrement the count, or to test whether the counter is zero or not.

The halting problem for one-counter automata is decidable, and there is an efficient algorithm to decide it, by translating the automaton to a PDA. So that might be one option, if it is expressive enough for your needs.

As a rough rule of thumb, in my experience, if you start from such a model and add a little more expressivity, the halting problem quickly becomes undecidable.

---

Possibly also of interest: Petri nets.
> 2 votes

# Answer
If you want a really interesting logic to work with, take a look at Description Logics. They're an astonishingly large fragment of first order logic. They have three major components:

* Individuals - objects to talk about. There can be infinite numbers of individuals. Your fights might be individuals.
* Concepts - concepts are properties that individuals might have. For example, one might have a concept specifying that the player will use a particular tactic. Or there might be a concept indicating that this is a boss fight.
* Roles - Roles connect individuals. You don't have to just have a collection of independent fights. Fights can relate to eachother. Use a tactic too many times, and the boss learns of it and can change their tactics.

There's many description logics. Some are easy to provide proofs. Some are very hard. But they're all *decidable*. The description logics we study are all decidable logics.

In the Description Logic way of thinking, your user provides an ontology describing what they will do. You, as the developer, provide an ontology describing what the computer will do. Description Logics can naturally be concatenated together, so their concatenation says exactly what will happen. Once you have that, you can ask questions like "Can you prove that the player wins all battles."

I recommend either taking an easy one like $\mathcal{AL}$ or a popular one like $\mathcal{SHION}^{(D)}$. The simple ones you can code yourself, but the more expressive ones are extremely hard. $\mathcal{SHION}^{(D)}$ in particular is extremely difficult, but you can find open source implementations that prove statements in it (e.g. HermiT or Pellet). $\mathcal{SHION}^{(D)}$ is decidable in DEXPTIME, which means its incredibly slow in the worst case. But it's an intriguingly powerful language with a lot of extremely intuitive features.
> 2 votes

# Answer
@D.W. gives a good answer to the question as asked which doesn't quite work for my application. the solution i've settled on is to use *non-erasing deterministic stack automata*.

a stack automaton is a PDA with the additional ability to move up and down the stack in read-only mode, introduced in Ginsberg, Greibach & Harrison (1967) for modelling compilers. Hopcroft & Ullman (1967) proved that a deterministic non-erasing version (ie. pushes to the stack but never pops) is equivalent to an $nlog\_2n$-bounded turing machine, so about as powerful as you can get while remaining decidable (albeit in exponential time). the proof, incidentally, is lovely - the principle is that although there are infinitely many possible stack configurations, because it can't push while reading down the stack it's effectively a finite automaton for the duration, so there are only finitely many equivalence classes of stack configurations a given machine can distinguish.
> 1 votes

---
Tags: decidability, infinity
---


# Question
Title: Grammar where the precedence of condition operators are asymmetric with regard to assignment operators
In Unix shell programming, there's the ideom:

```
program1 && program2 && program3

```

where successful completion of `program1` and then `program2` will lead to the execution of `program3`.

In Perl, there's 2 set of condition operators - punctuation styles `&&`, `||`, etc., which binds more closely; and keyword style `and`, `or`, etc., which binds more loosely (precedence below assignment operators).

Yesterday, I write this in C:

```
yesno && pointer += offset;

```

trying to achieve this: if `yesno` is true, `pointer` is advanced by an offset, otherwise, no action is taken. Of couse this failed because condition operators binds more closely than assignments and the expression became:

```
(yesno && pointer) += offset;

```

which is invalid since the left-side of the assignment is no longer an lvalue.

Question:

Of course, if there's a programming language with grammar that makes it legal, it would create whole lot of problem designing a compiler for it and write correct and efficient codes in it.

But for curiosity, I'd like to know is it possible to define a grammar such that make it possible to do:

* advance `pointer` by an offset with:

```
yesno && pointer += offset;

```

and

* assign boolean predicate to a variable:

```
cond = input_ready && output_ready;

```

# Answer
What you seem to be asking for is for assignment and `&&` to have *different* relevant precedence depending on which occurs on the left or the right -- `=` has higher precedence when it is to the left of the `&&` and lower when it is to the right.

This turns out to be remarkably hard to do with a traditional "pure" CFG, but fairly straight-forward to do with yacc's precedence declarations. The key to that is to realize that "precedence" in yacc really isn't about operations, it is about rules and tokens -- whenever a shift/reduce conflict occurs, it compares the precedence of the token to be shifted with that of the rule to be reduced and it does whichever is higher.

To have different precedence for on-the-left vs on-th-right, you just need difference precedences for the rule and the token, which you can do with a `%prec` directive. For your example, something like:

```
%nonassoc ASSIGN_LOW
%left ANDAND
%right '='

%%

expr: expr '=' expr %prec ASSIGN_LOW
    | expr ANDAND expr
    | primary
    ;

```

This gives a higher precedence to an `=` token than an `&&` (or the rule with `&&` which gets that precedence by default), so when an `=` appears to the right, it has higher precedence. But the full `expr '=' expr` *rule* has lower precedence, so the `=` on the left will be lower precedence.

This has a side effect that `=` will always be right recursive, even if you used `%left` or `%nonassoc` for it, as the `=` *rule* has lower precedence than the `=` *token*. I used `%right` here for clarity. If you did something where a rule had higher precedence that its token, that would always be effectively left-recursive.

---

To address the comment in the other answer, this still has issues with something like

```
A && B = C && D = E

```

which will be parsed as

```
A && (B = (C && (D = E)))

```

which might not be what you want. There's not a good way of dealing with that as it would require looking at more context to determine the precedence.
> 0 votes

# Answer
No. At least not unambiguously with context-free grammar.

Take the following grammar fragment as an example:

```
## preliminary
def assign-op # assignment operator
: ...
;

def unary-expr # uniary expression
: ...
;

## main grammar

def arith-expr # arithmetic expression
: ...
;

def logic-expr # logical expression
: arith-expr
| logic-expr ( "&&" | "||" ) arith-expr
;

def assign-expr # assignment expression
: logic-expr
| unary-expr assign-op assign-expr
;

```

In `assign-expr`, the lvalue is already defined as an unary expression. The problem with compiler issuing error is that, `yesno && pointer += offset` is parsed as:

```
yesno && pointer      +=        offset
vvvvvvvvvvvvvvvv      ||        ||||||
(  logic-expr  )      vv        vvvvvv
(expecting:unary-expr assign-op assign-expr)

```

where the assignment expression is expecting an unary expression but a logical expression was present.

Also, consider:

```
cond1 && ptr1 = buf && ptr1 += offset;

```

where the expected behavior is

> set `ptr1` to `buf + offset` if `cond1` is true and `buf` is not `NULL`.

If the proposed asymmetric precedence is realized, this expression would become essentially nonsense.

These can all be worked around with either a more complex grammar, or a non-conventional parser, but as explained in the question, this would make writing correct and efficient programs very difficult
> -1 votes

---
Tags: formal-grammars, programming-languages
---


title: Amortized cost for Stack Operations

text:
# Question
Title: Amortized cost for Stack Operations
> In this problem we consider two stacks $A$ and $B$
> manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):
> PushA($x$): Push element $x$ on stack $A$.
> PushB($x$): Push element $x$ on stack $B$.
> MultiPopA($k$): Pop $min(k;n)$ elements from $A$.
> MultiPopB($k$): Pop $min(k;m)$ elements from $B$.
> Transfer($k$): Repeatedly pop an element from $A$ and push it on $B$,
> until either $k$ elements have been moved or $A$ is empty.

I need to find the amortized cost for the each operation using accounting method.

# Answer
> 0 votes
I have assumed amortized cost for Push A and B as - 2 for remaining operations it will be zero except for Transfer - 2n

Can this costs be possibee ?

---
Tags: algorithms, algorithm-analysis, amortized-analysis, stacks
---


# Question
Title: How to put the given context-free grammar into Chomsky Normal Form?
I have questions about how to put the grammar below in CNF - Chomsky Normal Form:

S -\>aAa | bBb | ВВ;

A -\> C;

B -\> S | A;

C -\> S | ε;

I did it like this:

1. I eliminated empty productions:

S -\>aAa | aa | bBb | bb| ВВ;

A -\> C;

B -\> S | A;

C -\> S;

2. I eliminated unit productions:

S -\>aAa | aa | bBb | bb | ВВ;

A -\> aAa | aa | bBb | bb | ВВ;

B -\> Aa | aa | bBb | bb | ВВ;

C -\> Aa | aa | bBb | bb | ВВ;

3. I eliminated the useless variables (C), but it only becomes inaccessible after removing the unitary production of A -\>C). Can anyone help me and tell me if this is right?

# Answer
> 0 votes
It is the case that $C$ becomes inaccessible, but your grammar isn't in normal form (yet). Rules like $S \to aAa$ or $S \to bb$ aren't allowed in CNF.

Also your grammar isn't equal to the original, since you forgot that $S$ is nullable when removing the $\varepsilon$ production (e.g. you could derive $S \Rightarrow BB \Rightarrow^\* AA \Rightarrow^\* CC \Rightarrow^\* \varepsilon$ which isn't possible in your last grammar).

When bringing a grammar in CNF it's often a good idea to remove all $A \to B$ transitions first, and then remove the $\varepsilon$ transitions. So first start off by adding a new start variable $S'$

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to C$$ $$B \to S' | A$$ $$C \to S' | \varepsilon$$

then remove the $A \to C$ and $B \to A$ transition

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to S' | \varepsilon$$ $$B \to S' | \varepsilon$$

$C$ is now inaccessible, so we'll ignore it. Remove $A \to S'$ and $B \to S'$

$$S \to S'$$ $$S' \to aAa | aS'a | bBb | bS'b | BB | S'B | BS' | S'S'$$ $$A \to \varepsilon$$ $$B \to \varepsilon$$

remove the $\varepsilon$ transitions

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S' | S'S' | \varepsilon$$

remove $S' \to \varepsilon$ and $S' \to S'$

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S'S'.$$

This can now be brought into CNF

$$S \to S' | \varepsilon$$ $$S' \to AA | AX | BB | BY | S'S'$$ $$A \to a$$ $$X \to S'A$$ $$B \to B$$ $$Y \to S'B$$

as you should verify :\]

---
Tags: formal-languages, automata, context-free, normal-forms
---


# Question
Title: Is the language L = {<M> | There exists an M' that stops on the same input words, but L(M) ≠ L(M')} in RE or R?
Is the language $$L = \\{M | \exists M' \text{ that stops on the same input words but L(M)} \neq L(M')\\}$$ in RE or R?

I suspect that it's not in RE, since you'd have to first know for M all the inputs for which it halts, which you can't do in a finite time.

I wanted to show that $\overline {HP} \leq L$, and so because $\overline {HP} \notin RE$, also $L \notin RE$, but I can't seem to find a reduction function.

Thanks in advance

# Answer
> 5 votes
Notice, that all machines $M$ that don't halt on any input accept the same language, $\emptyset$. Thus if $M$ doesn't halt on any input then also $\langle M \rangle \notin L$.

Now define the TM $M'$ for some TM $M$ such that on input $x$

* $M'$ runs $M$ on $x$
* $M'$ rejects if $M$ halts accepting
* $M'$ accepts if $M$ halts rejecting

It's easy to see, that $$M \text{ halts on } w \iff M' \text{ halts on } w$$ and that $L(M) \neq L(M')$ for all machines $M$ that halt on some input. From this it follows that, if $M$ halts on some input, then $\langle M \rangle \in L$.

With this we have shown that $$L = \\{\langle M \rangle : M \text{ halts on some input}\\}.$$ This language is known to be in $\texttt{RE} \setminus \texttt{R}$.

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