# Question
Title: Language of Turing machines that loop on all inputs, recognizable?
Prove that the language Loop Turning Machine = { \< M \> | M is a TM that loops on all inputs} is recognizable.

I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or reject. Do I need to establish a decider?

EDIT:

Can I say that a halting Turing Machine $M$ is a machine for which exists a word $w$ such that $M$ halts on $w$? This makes the language recognizable but the machine may go on forever if executed.

# Answer
> 5 votes
$L$ isn't recognizable. We'll first establish a couple of preliminary results

**I. $\overline{L}$ is recognizable**

The complement of $L$, $$ \overline{L}=\\{\langle M\rangle\mid M \text{ halts on at least one input}\\} $$ is recognizable. Define a recognizer TM as follows:

```
R(<M>) =
   for n = 1, 2, 3, ...
      for each x in {x_1, x_2, ... , x_n}   // in some canonical order
         run M on x for one move
         if M halts
            return accept

```

It should be clear that $R$ accepts all and only those $\langle M \rangle$ for which $\langle M \rangle\in \overline{L}$ and so $\overline{L}$ is recognizable. Now if $L$ were also recognizable, then we could use the two recognizers to make decider for $L$, which brings us to our second result.

**II. L is undecidable**

If $L$ were decidable, then $\overline{L}$ would also be, and conversely. If that were the case, we could define a reduction from the known undecidable language $$ HALT = \\{(\langle M\rangle \mid M \text{ halts on input }w\\} $$ to $\overline{L}$ by the mapping $$ (\langle M\rangle, w)\rightarrow M\_w $$ where, as babou has already noted,

```
M_w(y) =
   erase the input y
   write w on the input tape
   simulate M on w

```

Now observe that $M$ halts on $w$ $\Longleftrightarrow$ $M\_w$ halts (on every input $y$, in fact) $\Longleftrightarrow$ $M\_w\in \overline{L}$. In summary, if $L$ were decidable, then we could $L$'s decider (reversing the roles of accept and reject) to decide the halting problem, a contradiction.

---

Now we can show that $L$ is not recognizable. If it were, then, using (I) we could conclude that $L$ was decidable, a contradiction to result (II).

# Answer
> 3 votes
*Note: obviously, here, "loops" must be understood as "does not halt".*

Consider a machine $M$ and an input $w$. From that you can build a machine $M\_w$ that, given any input, will just erase this input, replace it by $w$, and then will simply mimic $M$ on input $w$. Obviously $M$ loops on input $w$ iff $M\_w$ loops on all inputs.

If the language $L\_{\bar h}$ is recognizable, then we have a semi-decision procedure to know whether $M\_w$ loops, hence whether $M$ loops on $w$. Since we also have a semi-decision procedure to check whether $M$ halts on $w$, by simply running it, we have a decision procedure for $M$ running on input $w$. This being true for any $M$ and any $w$, we have solved the halting problem.

So there seem to be a good chance that $L\_{\bar h}$ might be there incognito. *(I mean $L\_{\bar h}$ is not recognizable)*

# Answer
> 2 votes
Here's a different proof that this language isn't recognizable, this time using self-referential TMs and the recursion theorem.

Suppose that your language is recognizable. Let $R$ be a recognizer for it. We'll assume that $R$ never rejects - we can do this by replacing any rejecting states of $R$ with states that loop infinitely. Therefore, if we run $R$ on a TM encoding $\langle M \rangle$, then $R$ accepts if $M$ loops on all inputs and $R$ loops of $M$ halts on any input.

So consider this self-referential TM:

> $M$ = "On input $w$:
>
> Use the recursion theorem to obtain $\langle M \rangle$.
>
> Run $R$ on $\langle M \rangle$.
>
> If $R$ accepts, accept $w$."

Now, either $M$ always loops or $M$ halts at least once. If $M$ always loops, then $R$ will accept $\langle M \rangle$, causing $M$ to halt - a contradiction! Otherwise, $M$ halts at least once. But that means that $R$ will loop on $\langle M \rangle$, causing $M$ to always loop - a contradiction!

The only bad assumption we made is that we had a recognizer for $L$, so our assumption was wrong and $L$ is not recognizable.

Hope this helps!

# Answer
> 1 votes
A machine that necessarily loops (for all inputs) is a machine whose final states (accepting or rejecting) are *unreachable*.

There are two kinds of machines that behave this way: those that use a finite amount of tape (and repeat configurations forever), and those that don't. Encodings of the first kind form a language that is recognizable: you just have to keep track of the recurrence of configurations.

If you combine these two types of machines in one class, any language of their encodings will not be recognizable - as the other answers have shown.

For further discussion, check out this other question: Does a never-halting machine always loop?

---
Tags: turing-machines, decision-problem
---


title: Proof on tree size using Isabelle

text:
# Question
Title: Proof on tree size using Isabelle
I'm trying to learn a little bit about Isabelle and proofs in general, and it's uses in Programming Language Theory. I'm following a book, "Concrete Semantics with Isabelle/HOL". I'm still in the beggining.

I was able to do the first exercises, but I got to a point where I noticed I just don't know what I'm doing. I just solved a question where I spent some time failing to prove something, than tried changing one little thing and it magically worked. Can someone explain what exactly is happening?

Ok, so here is what the question is basically about:

We had to make a simple tree structure with no data, like:

```
datatype tree0 = Tip | Node "tree0" "tree0"

```

The question ask us to make a function `nodes t` that count the number of nodes and leafs on the tree. Then, it provides a function:

```
fun explode :: "nat ⇒ tree0 ⇒ tree0" where
"explode 0 t = t" |
"explode (Suc n) t = explode n (Node t t)"

```

And ask us to provide an equation for the number of elements (nodes t) of the exploded tree, based on N and T, and prove that this equation is correct.

The equation I found was: `nodes(explode n t) = (2^n)*(nodes t + 1) - 1`

Which I tried proving using induction on "n" alone.

```
lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n)
apply(auto)
apply(simp add: exp_grow)
apply(simp add: algebra_simps)

done

```

After "apply(auto)", the goal changed to:

```
goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0 ⟹
         nodes (explode n (Node t t)) = 2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

```

So, I thought that proving `nodes(explode n (Node t t)) = 2*nodes(explode n t) + 1` would solve it. So I made a lemma for it, proved it and added the next two "simp"s.

But the proof failed, with:

```
goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + nodes t * 2 ^ n - Suc 0 ⟹
         Suc (2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc (Suc 0)) =
         2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc 0

```

I don't quite get why this doesn't end the proof. I wondered if I was just proving the wrong thing, or maybe I'm just mixing everything up.

After this, I removed the simplification based on exp\_grow, and tried generalizing the proof for "t". So I got:

```
lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n arbitrary: t)
apply(auto)
apply(simp add: algebra_simps)
done

```

Which worked! And I just couldn't understand what happend. I tried following this proof step by step. After auto, the goal is:

```
goal (1 subgoal):
 1. ⋀n t. (⋀t. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0) ⟹
           2 ^ n + (2 ^ n + 2 ^ n * (nodes t + nodes t)) - Suc 0 =
           2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

```

And it's proved on algebra\_simps. I don't understand what happened, and why it didn't work on the first time. I think I'm misunderstanding everything. It has been a while since I took an Algebra course, and maybe I'm doing the proof by induction wrong. I was able to do the other questions, but this one left me a little lost :(

So, can someone help me on this? What am I getting wrong here?

# Answer
Your first goal is provable, but is somewhat non-trivial arithmetic. I believe that the issue is essentially Isabelle not knowing that $$S(x - 2) = x -1$$ is true for arbitrary $x$, and indeed, this property is false in general, if $x\<2$! This is because $x-2=0$ in Isabelle for $x=1$.

Here this doesn't occur, because $x=2\cdot 2^n$, so $x\geq 2$ for all $n\in\mathbb{N}$. But the simplifier doesn't know this. Adding a lemma along those lines, or making sure `2*nodes(explode n t) + 1` doesn't get simplified to `S(2*nodes(explode n t))` should solve your issue.

Alternately, you could re-cast your whole proof in $\mathbb{Z}$, where subtraction behaves more sanely.
> 3 votes

---
Tags: proof-techniques, induction, proof-assistants, isabelle
---


# Question
Title: Extended version of the theory of reals and its decidability
It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,\<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More formally, is the theory $(\mathbb{R},\\{\underline{r} \mid r \in \mathbb{R}\\} +,\cdot,\<,=)$ evaluated in the standard model of the reals decidable? Here, the symbol $\underline{r}$ is such that its interpretation in the standard model is exactly the real $r$.

I guess that the extended version is still decidable, essentially because two reals are different if and only if there exists a rational number between them. Rationals, on the other hand, can be expressed in the usual Tarski fragment.

Can anyone help?

# Answer
Turing machines, in the classical sense, decide languages of finite strings over finite alphabets. Your logical language has uncountably many constant symbols so you can't even write down all the formulas as strings, let alone ask a Turing machine to decide things about the collection of formulas.
> 5 votes

---
Tags: logic, decision-problem, real-numbers
---


# Question
Title: How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?
How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ?

I've seen it stated that one can apply a maximum flow algorithm to compute a minimum $s$-$t$ cut in an undirected graph. However, trying to adapt the Edmond-Karp algorithm this doesn't make much sense, or does it ?

I know a graph can be viewed as an undirected graph with $(u,v)$ and $(v,u)$ replacing $\\{u,v\\}$...

# Answer
You don't *need* to adapt the algorithm, any maximum flow algorithm for directed graphs works by replacing the edges with a forward and backward arc as you suggested. Denote this directed graph $D=(V,A)$. Take the capacities $C(u,v)=C(v,u)$ of *both* arcs equal to the original edge. Then, let $F(u,v)$ be the maximum flow returned by your algorithm on the directed graph.

To find the cut you need the (directed) *residual* graph $G\_f$ which can be constructed explicitly from the flow by taking $D$ with capacities $C\_f(u,v) = C(u,v) - F(u,v)$. Now find the set $S$ of vertices reachable in $G\_f$ from $s$, where you can only cross arcs with positive capacity, and let its complement be $T=V\setminus S$. Then $(S, T)$ gives a minimum $s-t$ cut.

To see why this works, note that the capacities in the residual graph give the additional amount of flow in each direction that can be sent over an edge. That is, given the flow already in place, and if you assume that opposite flows cancel each other out. This means a saturated edge has 0 residual capacity in the direction of the flow and double its original capacity in the reverse direction (as $F(u,v)=-F(v,u)$).

Any vertex reachable from $s$ in $G\_f$ can receive more flow. Since $F$ is a maximum flow, $t$ cannot be in $S$. Similarly any edge between $u \in S$ and $v \in T$ must be saturated with flow in that direction, otherwise $v$ would be reachable from $s$. Now suppose the capacity of the cut-set is larger than the $s-t$ flow, then the flow from $S$ to $T$ is larger than the flow from $S$ to $t$, which means there must be flow back from $T$ to $S$ which is a contradiction. Since any $s-t$ cut is at least as large as the maximum $s-t$ flow it follows $(S,T)$ is a minimum $s-t$ cut.
> 2 votes

---
Tags: graphs
---


title: Determine if the language is $R$

text:
# Question
Title: Determine if the language is $R$
Consider the following language:

$$L = \\{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \\}$$

> determine whether or not the language is in $R$.

Now, from my understanding an $\langle M \rangle \in L$ doesn't necessarily returns the right answer but rather halts for every $\langle P, x \rangle$ where $p$ is a program (=TM) and $x$ is an input for the program.

I am guessing the language isn't decidable and can be showed as such by some reduction, but couldn't think of something useful.

I'll be glad for help.

# Answer
> 2 votes
comments summary:

The language $L$ is decidable.

Hint:

> $L$ is in fact empty! It contains all the machines that decide the halting problem. But, the halting problem is undecidable =\> there are no machines that decide it.

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


# Question
Title: Computational complexity of function $U^V$
Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is this an NP-hard problem?

# Answer
> 6 votes
One way to do this is by **repeated squaring**. First, express $V$ in binary, $$ V = b\_0+2^1b\_1+2^2b\_2+2^3b\_3+\dotsm+2^nb\_n $$ where each $b\_i$ is either zero or one. Having done this, repeatedly square $U$ to get $U, U^2, (U^2)^2 = U^4, (U^4)^2=U^8, \dotsc, U^{2^n}$. Then $$\begin{align} U^V&=U^{b\_0+2^1b\_1+2^2b\_2+2^3b\_3+\dotsm+2^nb\_n}\\ &=(U^{b\_0})((U^2)^{b\_1})((U^4)^{b\_2})\dotsm((U^{2^n}))^{b\_n}) \end{align}$$ For example, to compute $3^{21}$ we would get the binary expansion of $21=16+4+1$ and then repeatedly square the $3$s:

$$\begin{align} 3^1 &=3\\ 3^2 &=9\\ 3^4 &=81\\ 3^8 &=81^2=6561\\ 3^{16} &= 6561^2=43046721 \end{align}$$ So we'll have $$ 3^{21}=3^{16+4=1}=(3^{16})(3^4)(3^1)=(43046721)(81)(3)=10460353203 $$ Consider the worst case, with $V=2^n-1$, and let $d$ be the number of bits in the representation of $U$. This will require $n-1$ squarings. Let's use the grade-school multiplication algorithm, for which the product of two $k$-bit numbers will take $O(k^2)$ primitive operations. We'll then have $$\begin{array}{ccc} \text{product}& \text{factor size} & \text{ops needed}\\ U^2 & d & d^2\\ U^4 & 2d & 4d^2\\ & \dotsc & \\ U^{2^{n-1}} & 2^{n-2}d & 4^{n-2}d^2 \end{array}$$ So the total number of operations needed to precompute the squares will be $$ (1+4+4^2+\dotsm+4^{n-2})d^2 = O((2^n)^2d^2) = O(V^2\log^2U) $$

Now since we chose $V$ so that it involved all of the squares we computed, we'll have the final product $(U)(U^2)(U^4)\dotsm(U^{2^{n-1}})$. Mirroring the construction above, we find that the final product will also take $O(V^2\log^2U)$ operations, so to compute $U^V$ by repeated squaring will take time $(2^nd^2)$ where $n, d$ are the number of bits in $V$ and $U$, respectively. Unfortunately, this means that this construction is not polynomial in the size of $V$.

**Notes**.

1. In your original question, strictly speaking, the classes P, NP, Np-complete and NP-hard are generally applied to *decision problems*, which this isn't.
2. There are faster ways to compute the product of two integers, so you can actually do better than $O(V^2\log U)$.
3. While this (as it turns out) is actually *less* efficient than the naive algorithm of computing $U^V$ by successive multiplications, $U, U^2, U^3,\dotsc$, it works very well when computing modular powers, $U^V\pmod W$, since none of the intermediate products will ever be larger than $W$.

---
Tags: complexity-theory
---


# Question
Title: How to interpret these asymptotic runtime bounds for discrete logarithm algorithms?
I am trying to compare asymptotic runtime bounds of a few algorithms presented in this research paper, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. The functions are,

$L(\alpha) = \exp(O(\log(n)^{a}(\log\log(n))^{1-\alpha}))$,

which I'd like to plot for $\alpha = 1/3, 1/4+O(1)$, and $1/4 + O(n)$,

and $O(n^{\log n})$

> Where n is the bit-size of the input. ... Such a complexity is smaller than any $L(\epsilon)$ for any $\epsilon \> 0$

I would like to plot each of these functions together to compare their growth. The problem is that the second function grows much faster than the first, which implies I am misinterpreting something.

So what is the correct way to interpret and compare these functions?

# Answer
The confusion is that in the expression for $L(\alpha)$, $n$ is size of the field, whereas in $n^{O(\log n)}$, $n$ is the size of the input. The correct comparison is between $L(\alpha) = \exp O((\log n)^\alpha (\log\log n)^{1-\alpha})$ and $(\log n)^{O(\log\log n)} = \exp O((\log\log n)^2)$, which is indeed much smaller.

Note that your suggestion to plot $L(\alpha)$ for $\alpha = 1/4 + O(1)$ and $\alpha = 1/4 + O(n)$ doesn't make much sense; you should think of $\alpha$ as a constant. It could make sense to consider $\alpha = 1/4 + o(1)$ (or $\alpha = 1/4 + \epsilon$, where $\epsilon$ is understood to be "small"), though it's not clear how exactly you'd plot it. Indeed, there is no reason to plot, and a plot wouldn't make too much sense without knowing the hidden big O constant. In practice you just do experiments.
> 4 votes

---
Tags: asymptotics
---


title: Lambda Calculus Reduction

text:
# Question
Title: Lambda Calculus Reduction
I am a little confused to reduce these lambda calculus expressions. I am instructed to give applicative and normal order reductions for these expressions.

$(a):$ $$(\lambda x. (\\,(\lambda y.(\* 2 y)\\,) (+ x y)\\,)\\,)\\,y $$

$(b):$ $$(\lambda x. \lambda y. (x y)\\,) \\,(λz. (z y)\\,)\\,$$

Here are the steps I took in my first attempt at $(a)$:

$$(\lambda x. (\* 2 (+ x y)))y $$ $$(\lambda x. (\* 2 (+ x z)))y \thinspace $$

(substituting $y$ with $z$) $$(\* 2 (+ y z))$$

I'm unsure if I even reduced that correctly and how I would reduce in applicative order. Any help is appreciated, thanks!

# Answer
Applicative order: The leftmost, innermost redex is always reduced first.

Normal order: The leftmost, outermost redex is always reduced first.

1. Applicative order: $(λx.((λy.(∗2y))(+xy)))y$, the leftmost innermost redex is $(λy.(∗2y))(+xy)$. It is reduced first. Then we get $(λx.(∗2(+xy)))y$. Here $y$ is a free variable, renaming is not needed. Then the result is $(∗2(+yy))$.

Normal order: $(λx.((λy.(∗2y))(+xy)))y \rightarrow ((λy.(∗2y))(+yy)) \rightarrow \*2(+yy)$.
2. Applicative order: $$\begin{align\*}(λx.λy.(xy))(λz.(zy)) &\rightarrow\_\alpha (λx.λw.(xw))(λz.(zy))\\ &\rightarrow\_{\phantom{\alpha}} λw.((λz.(zy))w) \\ &\rightarrow\_{\phantom{\alpha}} λw.wy\end{align\*}$$ The first $y$ is bound, the second $y$ is free. When $x$ is substituted by $(λz.(zy))$, name capture occurs, so the bound y is renamed by $w$.

Normal order reduction is same as the applicative order.
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Amortized analysis of binary counter with increment and resetting operations
I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation.

First, 9th line of increment sets $\max\[A\]$ to -1 if $i \le \max\[A\]$ because for example going from 100 to 101 would set $\max\[A\]$ to $-1$ which does not make much sense.

Then, "if max\[A\] increases place 1 dollar as a credit on a new high-order 1." - when the high-order 1 has been set, 2 coins were given for this operation in increment - one for actually setting the bit to 1 and one for for the future, hence eventual reset to 0 would be covered by it. Why do we need to put yet another coin?

# Answer
> 2 votes
> First, 9th line of increment sets $\max\[A\]$ to -1 if $i \le \max\[A\]$ does not make much sense.

It does not make sense because it is *wrong*. This part of code has been wrongly aligned. It should be

```
5. if i < length [A]
6.   then A[i] = 1
7.       if i > max[A]
8.         then max[A] = i
9.   else max[A] = -1 // the array A overflows; A is effectively reset to 0. So max[A] = -1.

```

> Why do we need to put yet another coin?

As explained in the article, the amortized costs of `INC` and `RESET` are $\\$$4 and $\\$$1, respectively.

* $\\$$4 for `INC` is composed of

+ pay $\\$$1 to set 0 to 1;
    + place another $\\$$1 on the same bit as credit. *The credit on each 1 bit will pay to reset the bit during `INC`* (not by `RESET`);
    + pay $\\$$1 to update `max[A]`
    + place an additional $\\$$1 of credit on the new high-order 1 (If max\[A\] does not increase we just waste that one dollar). *The credit will pay to reset the bit during `RESET`*.
* $\\$$1 for `RESET` is

+ pay $\\$$1 to reset `max[A]`. Note that the resetting of bits `From i = 0 to max[A]` is paid for by the credit stored on the bits (each bit reset here has a credit on it due to the last $\\$$1 for `INC`).

***Added:*** For your specific question on "another $\\$$1 on bit 1", note that the first $\\$$1 credit on each bit 1 put by `INC` is consumed by the "resetting" part in `INC` itself (just as in the binary counter without the `RESET` operation). That is why you need another $\\$$1 on each, to pay for the `RESET` operation (i.e., the code `From i = 0 to max[A] A[i] = 0`). The charged $\\$$1 for `RESET` operation is only for the update of `max[A]`.

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


# Question
Title: Formula for returning the size of a circular array
I've come across a way of implementing a circular array that represents a double ended queue.

Let the circular array have the following instance variables:

```
int[] array;
int front = 0;
int rear = -1;
int size = 0;
int capacity = x;  // where x is a parameter in the constructor

```

The operations of the queue are:

dequeue - return array\[front\], increment front by 1,

enqueue - increment rear by 1, set array\[rear\] = value.

I have come to the conclusion that it is not possible to get the size of this queue by using the formula (front - rear + 1) % capacity. However, it is said that it's possible to get the size of the array using the same formula if we let the constructor set the capacity by:

```
BoundedQueue(int capacity) {
    this.capacity = capacity + 1;
}

```

With this technique the array will never actually get full and the formula for giving the size of the queue should work (it is said).

However I can't figure out how these modifications to the queue would result in the formula returning the correct size of the queue? We're only making the array one size bigger than it actually is, and we're always leaving at least one element unused. Could someone with a better insight explain to me why these modifications will lead to (rear - front + 1) % capacity giving the correct size of the queue?

Thanks in advance!

# Answer
I've not checked if your formula is correct but the point appears to be that $x\\%y$ can only give answers in the range $\\{0, \dots, y-1\\}$, whereas you're performing a calculation where the answer could be anything in the range $\\{0, \dots, y\\}$, including $y$. This means that any formula of the form `blah%capacity` is necessarily wrong.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Standard problem sets for metaheuristics
I'm wanting to dabble with metaheuristics and am interested to know what the "hello world" problem sets are.

In other words, what are the common problems (e.g Traveling Salesman, Vehicle Routing Problem, Maze Solving) to test various algorithms against in order to compare algorithm design?

# Answer
> 1 votes
are these any good to you?

Binary Welded Tree (BWT). To ﬁnd a labeled node in a graph

BooleanFormula(BF). To evaluate a NAND formula

ClassNumber (CL). To approximate the class group of a real quadratic numberﬁeld

GroundStateEstimation(GSE). To compute the ground state energy level of a particular molecule

QuantumLinear Systems(QLS). To solve a linear system of equations

UniqueShortest Vector (USV). To choose the shortest vector among a given set

Triangle Finding(TF). To exhibit a triangle inside a dense graph

---
Tags: optimization, machine-learning, artificial-intelligence, simulation
---


# Question
Title: How to expand 2D graphic and functions to 3D?
So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D.

I want to expand the 2D objects and functions to 3D which I don't expect to be too difficult, but still difficult enough that I don't want to reinvent the wheel.

> What is the process of migrating 2D to 3D algorythms called in computer engineering? And of course the follow-up question, if there is nothing on the web for that search term: What's it called in everyday computer engineering? Are there general concepts how best to expand a set of 2D-algorithms and -objects to 3D at all?

# Answer
> 2 votes
In most 3D graphics pipelines (e.g., OpenGL) points and direction vectors are represented with 4D homogeneous points `(x, y, z, w)` and their respective transformations are stored as 4x4 matrices. We can use the same representations for 2D and treat the z-value as the "stacking order" of our 2D shapes.

For example, for a 2D CW rotation about the origin we can use a 3D rotation about the z-axis:

```
       _                               _
      | cos(angle)  -sin(angle)  0   0  |
  M = | sin(angle)   cos(angle)  0   0  |
      |    0             0       1   0  |
      |    0             0       0   1  |
       -                               -

```

So to rotate a 2D point *(x,y)* about the origin we simply compute

```
  M * [x, y, 0, 1]^T

```

With 2D geometry we simply perform a orthographic projection into the rectangular region we wish to view. The pipeline is already designed to sort objects by their z-value for hidden-surface removal so defining a stacking order of 2D objects is trivial with the machinery in place.

Making the jump to 3D is a matter of generalizing the geometry and transformations with the added dimension. All of the usual affine transformations (rotation, scale, translation, shear, ...) generalize in a very simple way.

The biggest new concepts in 3D is setting up a virtual camera (defined by a simple affine view matrix) and you now have to project your 3D geometry down to 2D to create an image -- this can be done using parallel or perspective projections. Perspective projections require perspective foreshortening based on distance from the camera -- we can make very clever use of the homogeneous representation and a division by z to pull this off. This is standard material for most introductory graphics textbooks / courses.

Anyway, there's a start....

# Answer
> 1 votes
The 3D computer graphics manipulates with 3D objects, represented by data structures, which you won't meet in the 2D world. Also 3D algorithms (projections, ray tracing etc.) simply aren't needed in the 2D world.

So, there are no way to expand 2D graphics into 3D space, actually there is an opposite way - only at the last step, after you have calculated projections of all your 3D scene on a viewing plane, you'll need some 2D algorithms to generate a picture.

Please see here for more info.

---
Tags: terminology, computational-geometry, discrete-mathematics, graphics, mathematical-foundations
---


# Question
Title: When is a permutation k-wise independent?
I am a bit confused about what it means for a permutation to be k-wise independent.

If I pick a permutation uniformly at random from $\sigma \in S\_n$ then isn't it true that for any $k$ integers, $i\_1,i\_2,..,i\_k$ $\in \\{1,2,..,n\\}$, the numbers $\sigma(i\_1),\sigma(i\_2),..,\sigma(i\_k)$ are k-wise independent?

# Answer
> 3 votes
A permutation cannot be $k$-wise independent. A *distribution* of permutations is $k$-wise independent if for $\pi$ sampled according to the distribution and any $k$ different indices $i\_1,\ldots,i\_k$ and $k$ different values $j\_1,\ldots,j\_k$, the probability that $\pi(i\_1)=j\_1,\ldots,\pi(i\_k)=j\_k$ is $1/n(n-1)\cdots(n-k+1)$. (An earlier version of this answer contained a different definition that, while interesting, is not the standard one.)

A $k$-wise independent distribution is $\ell$-wise independent for any $\ell \leq k$, and the uniform distribution over all permutations is trivially $n$-wise independent. A $k$-wise independent distribution is a distribution which "looks like" the uniform distribution when considering at most $k$ points at a time.

It is easy to see that any $k$-wise independent distribution needs to have support $n^{\Omega(k)}$, and conversely, Alon and Lovett construct such distributions with support $n^{O(k)}$.

Here is a simple example of a $1$-wise independent distribution: it is the uniform distribution over the permutations $\pi\_1,\ldots,\pi\_n$ given by $\pi\_t(x) = (x+t) \pmod{n}$. It is easy to check that for all $1 \leq i,j \leq n$, the probability that $\pi\_t(i) = j$ is exactly $1/n$.

---
Tags: permutations
---


# Question
Title: How to read this inductive language definition?
A language $L$ is defined recursively according to the following rules:

* $λ ∈ L$
* If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$

I am not sure if strings from this language should mix from this definition. Would strings only consist of $bbbb$ and $aaaa$, or can it also consist of $bbaa$, $aabb$, and so on?

# Answer
The recursive definition implies that a word $w$ is in $L$ if there is a sequence $w\_0,\ldots,w\_n=w$ such that $w\_0$ is the empty word and for each $i=1,\ldots,n$, either $w\_i = bw\_{i-1}$ or $w\_i = w\_{i-1}aa$. This, in turn, implies that $L = b^\*(aa)^\*$.
> 1 votes

---
Tags: formal-languages, induction, mathematical-foundations
---


title: Union of two languages

text:
# Question
Title: Union of two languages
If I have these languages:

$$\begin{align\*} S&=\\{a,b,c,d,e,f,g,h\\}\\ A&=\\{b,g\\}\\ B&=\\{a,b,c,d,f,h\\}\\ C&=\\{a,c,g\\}\\,, \end{align\*}$$

Writing $X'$ for the complement of a set $X$, what would B'∪ C consist of? Would the elements of this language then be C = {c g}?

Also if I have B ∩ (A ∪ C'), would the elements of this language then be {ab bb cb db fb hb}? Since A ∪ C' would = {b} then combined with B we have {ab bb cb db fb hb}

# Answer
Union, intersection and complement have their usual meanings from set theory.
> 1 votes

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


title: A many-to-many mapping data structure

text:
# Question
Title: A many-to-many mapping data structure
What would be a good way representing: i. Given a key, return all the data values associated with that key AND ii. Given a data value, return all the keys that are associated with that data.

So far, all I can think of is to maintain all keys in a sorted linked list where each "key" node has a key value and a vector of pointers to data nodes (in addition to linked list bookkeeping). Likewise, maintain all data values in a sorted linked list and each "data" node has a data value and a vector of pointers to the relevant keys.

Could you please offer me a hint for a more appropriate solution to this problem?

# Answer
> 2 votes
Use two indices: the first index allows you to map a key value to the corresponding tuples that contain that key value; the second index allows you to map a data value to the tuples that contain that data value. Each index can be implemented as a hash table, binary tree, or any other data structure you like that provides fast lookups.

For instance, databases implement ideas like this to enable fast lookups and searches.

---
Tags: data-structures, dictionaries
---


# Question
Title: How is the Varshamov-Tenegolts code decoded?
For $0 \leq a \leq n$ the VT code $VT\_a(n)$ consists of all tuples $(x\_1,x\_2,..,x\_n) \in \\{ 0,1\\}^n$ such that $ \sum\_{i=1}^{n} ix\_i = a (mod (n+1))$

For example $VT\_0(4) = \\{ 0000,1001,0110,1111 \\}$

---

* Say someone has $x = 1001$ and deletes the first zero and transmits $x' = 101$. Now is the claim that a receiver who only has access to say $101$ string will be able to decode back to $1001$?
* Searching on the net what I see being called as "decoding algorithm" seems to me to assume that the receiver at least has access to the sums $\sum\_{i=1}^{n} ix\_i$ and $\sum\_{i=1}^{n-1} ix'\_i$ and also knows stuff like number of 1s and 0s to the left and right of the deleted position. This doesn't make sense to me since I thought that the idea is that the receiver doesn't know anything about $x$!

# Answer
Right, the code $VT\_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion. Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent.

Decoding can be done in several ways:

*The naive approach:* since the edit-distance is large, if only a single deletion occurred there is only a single codeword that could have been sent. To decode we can just go over all the codewords until we find the one that leads to the received word. More efficiently, we can start with the received word and try to insert 0 or 1 in all the possible position until we get a codeword. We are guaranteed that we will get only one code word. However, this still may take a lot of time/computation.

*The more efficient approach* is an observation that appeared in Levenshtein's original paper\[1\] and then also re-explained in Sloan's manuscript on single-deletion correction codes\[2\]. I'll repeat the essence of it, but you can find it there as well.

1. Assume each of the codewords $x=x\_1\ldots x\_n$ satisfies $$ \sum\_{i=1}^n ix\_i = a \mod n+1$$
2. If there was only a single deletion we will get the word $y=y\_1\ldots y\_{n-1}$. we can compute the value $$a' = \sum\_{i=1}^{n-1} i y\_i$$
3. The key observation is the following. Let's assume the index $j$ was deleted. That is $y\_1=x\_1, \ldots, y\_{j-1}=x\_{j-1}$ and $y\_j=x\_{j+1}, \ldots y\_{n-1}=x\_n$. Denote with $R\_0$ the $\\{x\_i\\}\_{i\<j}$ that are a $0$, and with $R\_1$ the ones that are a $1$. similarly, let $L\_0=|\\{ x\_i =0 \mid i\>j\\}|$ and $L\_0=|\\{ x\_i =1 \mid i\>j \\}|$. Now let's look at $a'-a \mod n+1$. (below all computations are $\text{mod } n+1$.)

3.1. Let $w=L\_1+R\_1$ the weight of $y$ (the number of $1$'s).

3.2. If $x\_j=0$, then $$\begin{align\*} a'-a &= \sum\_{i=j}^n i(y\_i-x\_i) = \sum\_{i=j}^n i(x\_{i+1}-x\_i) \\ &= ix\_{j+1} + (i+1)(x\_{j+2}-x\_{j+1}) + \dotsb + (n-1)(x\_n - x\_{n-1}) - nx\_n\\ &=-x\_{j+1} - x\_{j+2} - \dotsb - x\_n = -R\_1 \end{align\*}$$ (note that $R\_1\<n$ so the mod $n+1$ is good enough; I also virtually set $y\_n=x\_{n+1}=0$ so it adds nothing to the sum but make them well defined)

3.3. But if $x\_j=1$, then $$\begin{align\*} a'-a &= \sum\_{i=j}^n i(y\_i-x\_i) = \sum\_{i=j}^n i(x\_{i+1}-x\_i) \\ &= i(x\_{j+1}-1) + (i+1)(x\_{j+2}-x\_{j+1}) + \dotsb + (n-1)(x\_n - x\_{n-1}) - nx\_n\\ &= -R\_1 -i = -R\_1 - L\_0 -L\_1 -1 = -w -L\_0 -1 \end{align\*}$$

3.4. Forget about the minus sign (that is, look at $a-a'$ instead). If we get something which is $\<w$ then we must be in the first case (since $R\_1\<w$), and we learn two things: (1) that a zero was deleted, and (2) we learn $R\_0$, which means that we know where to put the zero back: before this deleted zero there are exactly $R\_1$ ones!
if what we get from $a-a'$ is $\>w$ we know we are in the second case. Now we learn that: (1) a one was deleted from the codeword, and (2) we learn $w+1+L\_0$ but we know $w$ so we get $L\_0$, and we can restore the deleted 1: to the left of this deleted one there are exactly $L\_0$ zeroes.

See also

\[1\]: V.I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, 1966. \[2\]: N.J.A Sloan, On Single-Deletion-Correcting Codes, 2002.
> 4 votes

---
Tags: coding-theory, error-correcting-codes, edit-distance
---


# Question
Title: Parallel shortest path in directed acyclic graphs
Finding the shortest path in a DAG is extremely easy:

See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

However, I cannot find a way of parallelising this code. Is there a way of doing that?

# Answer
> 1 votes
In complexity theory, the notion of *P-complete* (wiki) denotes the problems that are (widely believed) difficult to parallelize effectively. (*Note:* I am not good at this area. Please correct me if I am wrong.)

One typical P-complete problem is

> **Circuit Value Problem (CVP):** Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.

The "shortest path in DAG" problem is similar to CVP. I think it is not hard for you to find a reduction in the literature with, for example, the paper A Compendium of Problems Complete for P as a starting point.

---

A positive side: Of course you can layer the nodes in DAG and parallel the computation layer by layer to some extent.

---
Tags: graphs, parallel-computing, graph-traversal
---


# Question
Title: Is a 2 address machine more likely to follow a RISC or CISC design?
**The Problem:** If I have a 3 address machine, is my machine more likely to follow RISC or CISC design? 2 addresses? 1 address? 0 address.

To solve this problem I first looked up the different terms.

* RISC is a microprocessor architecture that has smaller/simpler set of instructions
* CISC is a microprocessor architecture that has larger/more complex set of instructions
* 3, 2, 1 address machines just mean how many addresses are in an instruction

When first investigating the relationship between RISC vs CISC and n-address machines, with the help of the slide below, I was able to quickly associate 3 address with CISC and 0 address with RISC.

I saw that 3 address instructions were much more complicated than 0 address and therefore would make sense for CISC design. Similar reasoning for 0 address machine and RISC design. How would you make the distinguish for CISC and RISC with the address sizes in the middle - 1 and 2?

# Answer
> 9 votes
The problem is that the terms *RISC* and *CISC* are marketing terms, not science or engineering terms. The terms are supposedly acronyms for "Reduced Instruction Set Computing" and "Complex Instruction Set Computing." Your assumption that 3 addresses is much more complicated than 0 addresses is *logical*, but there is no logic here, and typically 3-address instructions are associated with RISC and 2-address instructions are associated with CISC (and 1-address and 0-address instructions aren't very common any more, so aren't associated with either RISC or CISC).

The term *RISC* is generally associated with instruction sets that have the following characteristics:

1. Fixed width instructions. Usually 32-bits or 16-bits. This makes it easier for the instruction decoder to find the boundaries between instructions. In CISC machines, by contrast, the different instructions can range in length from 8-bits to as much 64-bits. This makes the job of the instruction decoder somewhat harder in CISC machines, but can result in programs consuming less memory.
2. Fewer operand addressing modes. In a RISC machine typically each *operator* (`add`, `sub`, `jmp`, `load`) has only one available *addressing mode* for its *operands* (the `a`, `b`, `c`, `d`, and `e` in your picture.) Typically for *arithmetic* type instructions (`add`, `sub`, `xor`, ...) the only available addressing mode is *register direct*. The source operands are found in registers, and the result of the computation can only be placed in a register. `Load` and `store` type instructions typically have one operand that is register direct and the other operand is *register indirect plus offset*. `Jump` and `branch` type instructions will typically have a *target operand* that is *pc relative*. There will typically also be a few `jump` and `branch` type instructions with a register indirect target, and sometimes a `jump` instruction with an *absolute* target operand. *The smaller number of operand addressing modes is typically the only way in which "RISC" instruction sets are actually **reduced*** (compared to "CISC" instruction sets). The reasoning, again, has to do with trying to keep the instruction decoder as simple as possible in RISC machines. The simple operand addressing modes are easier to implement in a simple pipeline, and so the decoder in modern CISC machines often has to do extra work to *crack* instructions with complex operand modes into sequences of micro-operations that are more like RISC instructions.
3. There is a tendency for RISC architectures to have more register names available. Many RISC architectures have 32 registers, while many CISC architectures have only 8 or 16. This again has to do with making it somewhat simpler to exploit instruction-level parallelism with a simple pipeline. Having more available register names makes it possible for the compiler to use different register names for unrelated computations, without requiring the hardware to do register renaming.
4. RISC architectures tend to have "3-address" instructions, while CISC architectures tend to have mostly "2-address" instructions. The notion of "3-address" vs. "2-address" is also somewhat fuzzy (and somewhat mis-named). Every `add` instruction has 3 operands, 2 source operands and 1 destination operand. The real distinction is whether those operands are *explicit* or *implicit*. In a so-called "3-address" instruction you make all 3 operands explicit. In a so-called "2-address" instruction you make the destination operand explicit and one of the source operands explicit. The third source operand is *implicit*: it is always the same address as the destination operand. In a so-called "1-address" instruction only one of the source operands is explicit. The other source operand is implicitly either an accumulator register or the top of the stack, as is the destination operand. Finally in a "0-address" instruction all the operands are implicit (usually the two source operands are the top two values on the stack and the destination goes back on the top of the stack.)

To sum up: these are all marketing terms, and don't really mean much. The important concepts have to do with the relationship between different instruction-set design choices and how those choices make it easier or harder to implement hardware pipelines.

# Answer
> 3 votes
To understand the technical aspects which survive (as @WanderingLogic said marketting aspect dominated quite quickly), of the RISC/CISC dichotomy you need to consider four points:

* it is not really a dichotomy but more a continuum
* history is important: RISC came as a reaction to tentative to close the so called *semantic gap*. Don't look at how simple arithmetic is done, that will give you about no information, look for instructions like polynomial evaluation or function entry with automatic display setting and register savings. Those are the complex instructions which are absent in RISC and present in CISC. They introduced complications in the processor and their function could often be implemented more rapidly with a sequence simpler instructions, especially when not needed in their full generality. RISC is somewhat the result of a *quantitative approach*(1) to ISA design, trying to make the cost of the inclusion of an instruction justified by its benefit and its frequency of execution.
* history is important: RISC became popular at a time when implementing a 32-bit RISC on a single chip was just possible while for implementing a 32-bit CISC you either had to use several chips or space saving techniques which had an impact on performance. You can nearly define RISC as the answer to the question "how to get an high performance 32-bit CPU on that area?" When the space available on a chip increased, the RISC cpus became more CISCy.

Now, how to get an high performance 32-bit CPU on a small area?

* You can't rely on having cache on chip, so lot of registers to benefit from the locality of data access. Thus not an accumulator nor stack architecture. (Aspect carried over with the register windowing).
* Pipelining. That means overlappable instructions, thus again 2 or 3 operands or you'll have trouble to have independent instructions.
* Simplify decoding. Fixed width instruction. Thus wide enough to have 3 operands and as the cost of implementing 3 operands is mostly instruction width, you get that most RISC are 3 operands ISA.

Delayed jump is more or less the result of pipelining with decoding simplified to the extreme.

---

1) See Hennessy and Patterson.

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete?
Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ EXPTIME or NEXPTIME complete? I.e. If a problem of exponential size relative to a NPC problem is of linear size in another problem, is the other problem exponential time complete? (I think there needs to be an upper bound on the complexity of translating, but I'm not entirely sure what that would be.)

# Answer
> 1 votes
I am not 100% sure that I understand the question but here is an attempt where I reformulate your problem.

You have $A,B\subseteq \\{0,1\\}^\*$ and know that $A$ is NP-complete. Furthermore you have a reduction $f$ such that $f(x)\in B$ iff $x\in A$ and such that $|f(x)|$ is in $\log(O(|x|)$. Does that make $B$ NEXPTIME-hard?

Well, since $A$ is NP-complete, I can translate any question $y$ of the the form "*does a nondet. TM $M$ halts in time $n$*?" into an equivalent question $g(y)$ for $A$, using the reduction that establishes the NP-hardness of $A$. It is thus possible to translate an NEXPTIME-hard question $y$ of the form "*does $M$ halts in time $2^n$?*" into an equivalent $g'(y)$ for $A$. That reduction is very simple to describe but it produces instances of exponential size. If we could compute $f(g'(x))$ efficiently, we would have a reduction showing that $B$ is NEXPTIME-hard. This is possible in many cases --remember that $g'$ is very simple and that $|f(g'(x))|$ is in $O(|x|)$-- but this depends on knowing $f$ and how nicely it interacts with $g'$.

So I'd say that in general you cannot say that $B$ is NEXPTIME-hard but in many specific cases you'll manage to show it is.

(Final note: the above is about lower bounds. You cannot provide upper bounds for the complexity of $B$ from the assumptions. They only talk about the part of $B$ that is in the image of $f$).

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


# Question
Title: Algorithm for Dynamic Client Side Throttling
**Problem**

I am trying to come up with an algorithm that will dynamically throttle a client's number of outstanding requests based on the response times of completed requests. Response times are unpredictable and can be between 7 and 90 seconds. The response times are greatly affected by the total of outstanding requests, if the server is flooded it bogs down and times increase to very long times.

**My specific scenario**

My client application has several http requests it needs to send to a server (actually 3 servers that are load balanced and use a round robin distribution, *the number of servers and the code running there are out of my control*). Each request is a flat object containing 25 parameters. The server uses the parameters to do several look ups which may or may not trigger other look ups and calculations, this is where the server processing time is variable. The server returns a list of corresponding results which can be 0 to approximately 25 in length for most results.

**What I have tried**

I created a rolling average class that keeps the response times of the last X number of responses and can give the average at any point. Then when each response is received I compare its response time to the average. If the response time is equal or less than the average I increase the number of allowed outstanding requests. If the current response time is greater than the average I decrease allowed outstanding requests.

This approach worked somewhat in scaling up but I had cases where the average just grew over time and allowed more and more outstanding requests which brought everything to a crawl.

I have an implementation question on stackoverflow if you want more details on how I am doing this in code minus the rolling average part.

https://stackoverflow.com/q/30263716/1168353

I have been using a mocked out version of the server that just sleeps a thread before returning a response. I pick a "bestWaitSeconds" that is the fastest time it can return and a "MaxRequestsBeforeDegradation" that determines the maximum number of requests before times increase, anything below that returns bestWaitSeconds. The degradation formula looks like the below and only applies when "currentRequests" is more than MaxRequestsBeforeDegradation.

secondsToWait = (currentRequests - MaxRequestsBeforeDegradation) * (r.NextDouble() + .5) * bestWaitSeconds;

The random is just a way to apply the unknown return time stated in the problem. Times do go well above 90 seconds when the server is overloaded. This formula isn't exactly what the server does but it conveys the idea I think.

So basically the algorithm needs to get as close to MaxRequestsBeforeDegradation as possible. In the real case that MaxRequestsBeforeDegradation would change over long amounts of time so the algorithm also needs to adapt and explore up and down to continually know where the best number of outstanding requests is. Hope this helps.

**Summary**

How can I dynamically find the optimal number of outstanding requests allowed at a given moment to get the greatest throughput, given only a history of response times?

# Answer
this is a fairly basic problem in control theory and there are "design patterns" in this area to handle this type of system, and think there is probably an example right out of a control theory book very close to your question. basically the theory involves a concept somewhat like the way a thermostat regulates temperature in a house. if the house is too hot, the heater shuts off, if is too cool, it turns on. you want something like the opposite where more delay ("throttling") is applied when there is greater load, however the principle is the same.

a basic solution is something like this. keep track of the minimum response time, this is a "baseline". now measure the current instantaneous difference between the minimum response time and current response time, this is roughly proportional to "load". now one does not one long-past load to influence current load readings. but neither does one want a large current spike in load to effect the throttling too much. the immediate idea here is to use a exponential running/ moving average of the load measurements to determine the throttling (this metric is used a lot in stock trading algorithms). exponential averages have a tunable continuous parameter (0..1) that basically weights between current and past values, at one end the past values are weighted lighter, at the other end the current value is weighted heavier.

my suggestion is to try this algorithm for different weighting values and then graph the results. notice a lot of web load problems vary over daily rates where midday or midweek have highest load. in that case a changing weight value might be more optimal. a basic strategy to figure out the general trend of cycles in input load would be to have no throttling and then just look at daily or weekly loads.

note that some round-robin routers are automatically doing something like basic load balancing because they do not route to already busy connections.
> 4 votes

# Answer
Only the server can accurately determine what its current load is, and thus how much more work it can handle or when it might be able to handle more work in the future. This is why load balancing and throttling is usually handled server-side. A client can't know why its requests are failing; it could be an overloaded server, a overloaded network or even a rat patiently gnawing the shielding off a cable behind a wall somewhere, sending bursts of noise down the line. A fancy adaptive backoff algorithm isn't going to dissuade the rat or make things work better if the problem is that routes are flapping between the client and the server. Clients should use a simple backoff algorithm when requests start failing and let the server, network and anything else in between manage its own load.

The HTTP spec says that a server may send a Retry-After header along with the 503 response to indicate how long the service is expected to be unavailable. The client can use this as a best guess when to retry the request. Of the possible ways to manage server load, this seems the best place to start:

1. Have each server assess its own load and hand out reasonable Retry-After headers when overloaded.
2. Have the clients (or the load balancers) honor those headers.
> 2 votes

---
Tags: algorithms, computer-networks, communication-protocols
---


title: Formal Languages and Automata Theory

text:
# Question
Title: Formal Languages and Automata Theory
How can I show that $L = \\{a^m b^n \mid (m \> n \text{ or } m \< n) \text{ and } m, n ≥ 1\\}$ is not a regular language.

# Answer
Use the fact that compliment of a regular grammar is regular. So assume this language is regular. Then its complement is also regular that is $$\\{{a^{m}b^{m}}\\}$$ Now using pumping lemma you can show that this is not a regular language.
> 0 votes

---
Tags: formal-languages
---


# Question
Title: How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?
When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge `(i, j)` just stored in the list of edges of `i` or on the list of edges of `j`. Other times, it's important to have an `(i, j)` on `i` and a `(j, i)` on `j`.

I was wondering how do you call graph representations of one type and graph representations of the other type? Without concrete names to give to each one of them, code or even conversations about certain algorithms get confusing really fast.

# Answer
Your second kind of representation is simply called the adjacency list representation. It's a standard representation for graph data structures.

To my knowledge, there is no standard name for your first kind of representation; it's a weird and non-standard kind of representation. That's probably because it's not sufficient for most algorithms on undirected graphs (most algorithms require more), whereas the adjacency list representation *is* sufficient for most algorithms on undirected graphs. So, it would be rare to find situations where your first kind of representation is sufficient and useful.

You say that your first kind of representation is sufficient for Kruskal's algorithm, but this might be a bit misleading. In fact, Kruskal's algorithm is fine with something even more minimal: merely having a list of all edges is sufficient for Kruskal's algorithm. In other words, Kruskal's algorithm does not require the edge `(i,j)` to be associated with either `i` or `j` (it's OK if it's not associated with either, as long as you have a list of all edges).

In general, your first kind of representation does not seem like a natural choice for any graph algorithm that I can think of right now, so it's not surprising if it doesn't have a standard name.
> 2 votes

---
Tags: terminology, graphs, data-structures, weighted-graphs
---


# Question
Title: (operationalizable) Cost measure for small problems
For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they would all be solved in about the same time.

Yet, I turn out to be interested in some cost measures for small problems. For instance, although both `12 + 14` and `123503 + 589034` can be solved in the blink of an eye by today's computers, there seems to be a sense in which `123503 + 589034` is still more "costly" than `12 + 14`.

So **my question is** : do you know of any such cost measures that would be appropriate for such small size problems?

**Note 1** : I am interested in rather general answer for all kinds of problems, the addition one being just an example.

**Note 2** : the best I have found so far is Kolmogorov's complexity, but for what I understand of it, it seems awfully hard to operationalize. *First* it appears to be dependent on the reference language, and *second*, once a language is chosen, it seems really hard to prove that a description of a string is of minimal length.

* Do you know of any measure which would be easier to implement?
* Am I missing something about Kolmogorov's complexity and is it easier to implement than I suggest?

# Answer
> 2 votes
When we talk about complexity in computer science we are usually talking about asymptotic complexity. We are interested in characterizing the complexity of a process as the size of its inputs increase. This is useful because it abstracts away implementation-specific characteristics, such as processor speed or architecture or available memory. So while asymptotic analysis does, in this sense, concern itself with "large problems," its intent is not so much to treat large problems as it is to provide a meaningful metric for comparing algorithms in terms of time and space efficiency.

Kolmogorov complexity does not, to my knowledge, find applications in the practical analysis of programs or computational processes. It is an information-theoretic measure concerned with the minimal length of data as represented in a computational system. In so far as using it in any sort of "operational" analysis like those you've proposed, the big roadblock is that the Kolmogorov complexity of an arbitrary string is not, in general, computable!

It's difficult to pin down exactly what you're asking for, but it sounds more akin to counting CPU cycles required to execute a series of instructions. Back in the old days, when assembly language on punch-cards was the state-of-the-art, this was a fairly common technique used for optimization.

As it applies to your example, adding two numbers would involve loading them, bitwise, into registers, performing the addition, and storing the result. If the addends required more bits to represent than the size of the registers, you'd have to do it piecewise, loading and storing intermediate results as needed. You can count the cycles needed to execute tasks of varying 'difficulties' (adding two 1-byte numbers vs. adding two 2-byte numbers, for example) and compare them to give some sense of how much more or less 'complicated' the execution of a given sequence of instructions is.

It's not complexity in the traditional CS sense, but it would be a quantifiable, implementable metric. Donald Knuth has a program here that counts the cycles required to execute MMIX programs, as an example of such an implementation.

---
Tags: complexity-theory, kolmogorov-complexity
---


# Question
Title: Is there any published paper about automated planning software used in the ESA Rosetta mission?
The Rosetta spacecraft has reached a comet in August 2014 and sent a lander on its surface. It was one of the greatest science news of the year.

Automated Planning and Scheduling techniques are really important in the operations of these kinds of missions. At the last ICAPS there was even an invited talk by one of the staff members involved in the automated planning technologies used in the spacecraft.

Is there any published paper on the planning technologies used in the spacecraft? I've only found this one, but it does not appear to have been published in conferences or journals. Has it or something similar been published somewhere?

# Answer
> 6 votes
Well, as far as I can tell, there was no specific automated planning tool for the Rosetta mission *as we understand automated planning systems in ICAPS*, which is the most prominent conference on Automated Planning and Scheduling.

The hardest part was to plan the journey from earth to a common location where both the spacecraft and the comet could meet and this was done mainly in two stages: one making the spacecraft orbit around some bodies to save energy (cruise phase) and this was mainly done with astronomical computations; after hibernating for a good number of years, it had to wake up and fly (now using its own power) to meet the comet. There was, additionally, another scheduling problem in the final landing operation of Philae. The last two operations were self-automated.

I asked someone with a better knowledge of Rosetta and this person told me (right now) that there were mainly scheduling systems (as they are also called in the paper you mention) and that most of the operations were self-automated (ie., the main difficulty was that Rosetta was so far that it had to be able to take some decisions on its own, but still it received orders from the ground segment chiefs in ESTEC, Germany).

This said, I do not think we will ever see a paper about how to use PDDL (Planning Domain Definition Language) for Rosetta, or how to use LAMA, Fast-downward, FF (or any temporal PDDL planner) or anything of the kind (I mean, the kind of research we all do at ICAPS) but something instead far more domain-dependent.

On the other hand, it is rather unusual for engineers and scientists at ESA to publish papers at scientific venues such as ICAPS, ECAI (European Conference on Artificial Intelligence), AAAI (Association for the Advancement of Artificial Intelligence), IJCAI (the International Joint Conferences on Artificial Intelligence). They instead submit their papers to the SpaceOps symposium. I found a number of papers there:

Geurts K., Fantinati C., Ulamec S., Willnecker R. Rosetta lander: On-comet operations preparation and planning. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Haddow, CR., Werner D. Mission planning framework - Building the rosetta and bepicolombo planning systems. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Moussi, A. Fronton JF., Gaudon P., Hallouard D., Mangeret M., Delmas C., Lafaille, V., Durand J. PHILAE lander: A scheduling challenge. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Eiblmaier MG., Blake R., Williams A., Lodiot S., Godfrey J., Bartesaghi M. Automating ESA's planetary missions: From concept to conclusion. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Hope this helps,

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


# Question
Title: Algorithm deciding if a radius of a graph is two
Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?

# Answer
> 1 votes
Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.

---
Tags: algorithms, graphs
---


# Question
Title: Are deterministic and nondeterministic Cellular Automata equivalent?
It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.

I haven't even found a definition anywhere. It feels like NCAs can't be equivalent to CAs (not in the same lattice at least), even though I can convert a NFSM to a FSM the possibly exponential growth of the required states doesn't fit to the CA definition, it would need a higher dimensional lattice (i.e. more local neighbours).

So, are NCAs and CAs equivalent ? Are there papers or books discussing this ?

# Answer
I think you should define precisely what you mean by equivalent, and possibly what kind of CA you are willing to consider, with what communication grid. So I will just assume the simplest interpretation.

Given that it is fairly easy to build deterministic cellular automata with Turing power (even with a 1 dimemsional grid), and that according to the current wisdom of the Church-Turing Thesis, we have little chance to improve on that, my best bet is that non-deterministic cellular automata cannot be more powerful than deterministic ones. Given that adding non-determinism can only increase the computational power, i.e. a deterministic automaton is a special case of non-determinism, whe should not expect non-deterministic cellular automata to be less powerful than deterministic ones.

Hence, in terms of computational power, deterministic and non-deterministic cellular automata are equivalent.
> 4 votes

# Answer
I gave it a little more thought, this part of my question:

> "NCAs can't be equivalent to CAs \[..\] possibly exponential growth of the required states doesn't fit to the CA definition"

is false. The number of states doesn't matter, It would still be the same lattice. E.g. Let $A$ be a CA on $Z$. The state of a cell $q$ is either $0$ or $1$, all cells are $0$ at first. Each cell sees only it's direct neighbours. Then consider this state transition function $\delta$:

```
+---------------------------------+
| $q_l$ | $q_t$ | $q_r$ | $q_{t+1}|
|-------+-------+-------+---------|
|   0   |   0   |   0   |   0     |
|   0   |   0   |   1   |   1     |
|   0   |   1   |   0   |   1     |
|   0   |   1   |   1   |   1     |
|   1   |   0   |   0   |   0     |
|   1   |   0   |   1   |   0     |
|   1   |   1   |   0   |   0     |
|   1   |   1   |   1   |   0     |
+---------------------------------+

```

It doesn't matter whether I would describe this as a DFSM or NFSM, as long as both accept the same input string, e.g. $q\_lq\_tq\_r$. Here is a NFSM and a DFSM version describing $\delta$, both accept the same string, accepting means $q\_{t+1}$ will be 1, else 0.

Not drawn input combinations end in a rejecting state. While this is no proof I think it intuitively shows that CAs and NCAs are equivalent.
> 2 votes

# Answer
Nondeterministic CAs seem not studied very much in comparison to CAs, and don't seem to be cited on wikipedia. But they have been touched on, there is a natural way to define them. Analogously to all other automata or machine models, nondeterminism is just multiple or nonunique "next states" in the state table. Here is an example of study of them. The proof of equivalence in computations proceeds as with other machine models. The nondeterminism just allows multiple deterministic computational paths so to speak. However, they have different computational complexity capabilities as described in this paper.

> If we consider a multifunction instead of A , we obtain the definition of a nondeterministic cellular automaton (NCA). Generally speaking, evolutions of NCA are not uniquely determined by initial configurations. A behaviour of NCA may be described by a state transition network (look at \[4\]). It is a graph, each of whose nodes represents some configuration.
> 1 votes

---
Tags: closure-properties, computation-models, nondeterminism, cellular-automata
---


title: AMAT question cache here

text:
# Question
Title: AMAT question cache here
Suppose that the processor reads cache memory in one clock cycle.In case of cache miss the processor needs 5 clock cycles to read the information in the main memory.What should be the value of Cache hit rate so that AMAT=2?

We know that

AMAT=Hit time+ (Hit rate)\*(Miss penalty)

Hit rate= (AMAT-Hit time)/Miss penalty= (2-1)/6=1/6

I am not sure if miss penalty is 6.I know that miss penalty is the sum of the time taken to read the cache memory and the time needed to read the information from the main memory.Which means that Miss penalty=5 +1=6 .Still something feels off here.

# Answer
> 1 votes
Two things are clear from the statement of the quesiton: The hit access time is 1 cycle, while the miss access time is 5 cycles.

But you are not sure if the "miss penalty" is just a different name for the "miss access time", or is it in fact the "miss access time" minus the "hit time", right?

So let's think about this together.

What is this AMAT thingy you are trying to compute?

it is the *Avarage* access time. (i'd guess AMAT stands for Avarage Memory Access Time, right?).

Let's assume the miss-rate is 1/6. It means that 5/6 of the times, we have a hit, but 1/6 of the times it's a miss. In this case the average access time would be: $$ \frac56 \times 1 + \frac16 \times 5 = 1 \frac23$$ BUT OH NO! that's not what you got. Note that your formula for AMAT is **not**

> AMAT = (hit-rate)\*hit-time + (miss-rate)(miss-time)

but it is (fixing the typo you have there, *miss-rate${}=(1-{}$hit-rate$)$*)

> AMAT = hit-time + (miss-rate)(miss penalty)

But AMAT is just AMAT, which can mean only one thing: for hit you pay "hit-time", and for miss you pay "hit-time + miss-penalty". Again: you always pay the hit, and only if it is a miss, you pay an *extra* of the miss-penalty. Make sure you see that this is exactly what your AMAT formula says. Therefore, the miss-penalty must be defined as the miss-access-time *minus* the hit-access-time.

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


# Question
Title: Why is T not a minimum spanning tree of G?
**The Problem:** Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.
a. True of false: T is a spanning tree of G?
b. True of false: T is a minimum spanning tree of G?

I read from Single source shortest paths problem is a problem "in which we have to find shortest paths from a source vertex v to all other vertices in the graph." I read from Partial Solutions that only one of the options is true.

From my intution and the statements above, I reasoned that *a* is true while *b* is false. This is because if T is a minimum spanning tree of G, be definition it should also be a spanning tree of G. I am trying to show that *b* is false with a counterexample but I can't find/draw a graph in which T isn't a min spanning tree.

Can anyone show me a counterexample to *b*? To me, Dijkstra's algorithm is similar to Prim's algorithm to find MSt, so in the end T should be a min spanning tree.

# Answer
> 4 votes
Vertices: {A,B,C}

Edges: (undirected) {A,B,4} {A,C,3} {B,C,2}

So basically it's a triangle with the given weights. Starting from A, Dijkstra's algorithm will give you (A,B) and (A,C) but the minimum spanning Tree will give you (A,C) and (C,B).

# Answer
> 1 votes
Well, what if you have negative edge weights? Are you sure that you'll get the MST in that case? What if your graph looks like this:

```
Vertices:

{A, B, C}

Edges:

(A, C, 2)
(A, B, 1)
(B, C, -2)

```

Where an edge is represented as `(vertex1, vertex2, weight)`.

Wouldn't the tree returned be only the edge `AC`?

---
Tags: algorithms, graphs, proof-techniques, weighted-graphs
---


# Question
Title: What is the name for the complexity class $O(n^{1+\epsilon})$
Sometimes problems can be solved in $O(n^c)$ time for any $c \> 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive constant. I want to know the terminology for describing this complexity class.

For example, I would call a $\Theta(n)$ algorithm "linear". I would call a $\Theta(n^2)$ algorithms "quadratic". I would call a $\Theta(n \cdot log^c(n))$ algorithm "nearly linear". (Note that nearly linear is better than $O(n^{1+\epsilon})$.)

What do I call algorithms that are in $O(n^{1+\epsilon})$?

# Answer
> 1 votes
The term I've seen in use is *superlinear*, as in "Are there super-linear time complexity lower bounds for any natural problem in NP?"

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


# Question
Title: How to draw a graph to disprove this statement?
**The Problem**: Indicate whether the following statements are true or false:

* a. If *e* is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
* b. If *e* is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph
* c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree
* d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree

I read from Min Edge that every MST must contain the minimum weighted edge and from Partial Solutions that two of the assertions are true while the rest of the two are false.

From those two statements, I concluded that the first two statements(a, b) are true while the last two statements(c,d) are false.

Here is the diagram I used to illustrate that the last option, d, is false.

The edge weights are not distinct(two twos) and there is only one minimum spanning tree.

Can anyone give a counterexample graph to choice option c? I tried some examples(too many to include in here) but each time with distinct weights, using Prim's algorithm, I only found one MST.

# Answer
You have made a mistake interpreting the wording of the question compared to the Stackoverflow question (link in case of later editing).

Notice that in options (a) and (b), the phrasing is ***a*** minimum weight edge, whereas in the Stackoverflow question the phrasing is ***the*** minimum weight edge. In your question, there's no guarantee that the edge is the only edge with that weight, in the Stackoverflow question, there is exactly one edge with the lowest weight.

Thus the mistake is assuming that (b) is true, when in fact it is false. The two true options are (a) and (c), which is why you can't find a counter example to (c).

In both (a) and (c) however, the proof is very similar to that in the Stackoverflow question. In fact (c) is given by applying that proof inductively. (a) is given by basically the same argument, but you show that the tree made by adding the given edge and removing some other edge from the cycle can't have higher weight (because the new edge has minimum weight).

To see that (b) is false, just take the graph $K\_{n}$ where all edge weights are the same. Any spanning tree is a minimum spanning tree.

For (d), consider the following graph; take a tree on $n$ vertices, give all these edges weight $1$. Then add all non-edges, give these new edges weight $2$. Clearly there's only one MST, but there's $\binom{n}{2} - n + 1$ edges with the same weight.
> 3 votes

---
Tags: algorithms, graphs, proof-techniques, weighted-graphs
---


# Question
Title: What is the standard notation for introducing syntactical formalism in a paper
Suppose you want to introduce a format for a language, commands, ... etc. (Specially in the filed of computer science) in a paper

for example something like below:

```
X | Y = [ Z ] <W> [ / ] $P

```

By this, I mean, `X` or `Y` could be at the left side of an equation, `Z` is an optional argument at the right side, `<W>` is another syntax for something and it is followed by an optional slash and `$P` is another argument...

What is the standard way to introduce such formalism?

For another example suppose you are

* The first one who want to introduce XML synatx
* Someone who want to introduce a syntax near or derived from XML

However I am the case two.

# Answer
There is no general standard way. It depends to some extent on what is customary in the community you are addressing, on the size and syntactic complexity of the language you are defining, on the amount of formality required, and on whether the formalism is intended for practical use or only for theoretical work.

Typically, if you are defining a programming language, You are likely to decompose the presentation into a lexical and syntactic part. The lexical part defines elements of your language such as identifiers and literals (numbers, strings, or other), usually by means of regular expressions. The syntactic part defines the various constructs of your language, often with a Context-Free grammar. In the case of programming languages, the most common way of defining a context-free syntax is with the Backus-Naur Form (BNF) which is a metalanguage for syntax definition.

I you a creating a shell command for the Unix system, you will use a presentation that is quite close to your example.

If you are defining an algebraic formalism, you may define a tree syntax, or possibly a string syntax based on a context-free formalism, possibly not caring for syntactic ambiguity issues.

It is up to you to be knowledgeable enough to determine what is appropriate in your specific case. Existing similar literature should help you.

Two questions you want to ask yourself when choosing a notation are:

1. what is sufficient to convey my intent with enough precision, given the purpose and use of the language?
2. Will it be clear for my readers, given the kind of experience and knowledge they are supposed to have.

Your specific example of being the first to introduce XML syntax, is difficult to answer because the is not really a first. The XML formalism was derived from predecessors such as HTML and SGML, and probably other mark-up languages. One is seldom first, and it is usually wise to restart from the shoulders of those who came before. This applies both to what we define, and to the definitional tools. However, the intended community of users may change, and choices that may be best for a very general public may not be so good for computer specialists, or for theoretical work, the converse being also true. On the other hand, people prefer things close to what they already know.

If you want to introduce a syntax near or derived from XML, the above applies, and you should probably use the same definitional tools But you should probably make sure that your variations are necessary. In such a case, you may also rely on what people may already know of XML, which is fairly widely known, and insist on the differences, on the ways your language departs from XML.
> 3 votes

---
Tags: notation
---


# Question
Title: Can DFA with output (definition?) match expressiveness of NFA with unique output?
For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of outputting a word lower-case, or upper-case, depending on a control sequence included in the input. So the task

* `l:aNNa` should become `anna`
* `u:aNNa` should become `ANNA`

(where aNNa could be an arbitrary long word) seems to be quite easy for a DFA with output. The task in the reverse direction

* `aNNa:l` should become `anna`
* `aNNa:u` should become `ANNA`

however seems to be impossible for a DFA with output, at least for the commonly encountered definitions of DFA with output. On the other hand, a nondeterministic finite automaton (NFA) with unique output has no problems doing a task in the reverse direction, if it can do it in one direction.

1. Is the observation correct that a DFA with output can't do the task in the reverse direction, if it is forced to consume its input one symbol at a time?
2. Would it be possible to relax the restrictions for DFA and NFA, such that a NFA (with unique output) would not gain any additional expressiveness from the relaxed restrictions, but the DFA with output (for the relaxed restrictions) would be able to match the expressiveness of a NFA with unique output?

# Answer
> 1 votes
An interesting definition can be found in an old survey article by J. Berstel and J. Sakarovitch

> A *plurisubsequential function* is a finite union of subsequential functions having pairwise disjoint domains. A *subsequential function* is a function realized by a gsm equipped with an additional partial output function $\rho$ defined on the states of the gsm. ...1

The finite union with pairwise disjoint domains covers cases like above, where more than one output makes sense, but we know only later which. An reasonable implementation could first scan the input once, determine the relevant subsequential function, and then compute that function by a second scan over the input.

The survey proves that addition of one is a plurisequential functions if the digits of the number are given in low-ending order, but not if the digits are given in big-endian order. So the observation from the question about the reverse direction is correct.

---

Interesting, J. Berstel also wrote a book which contains an answer to the question whether it is possible to relax the restrictions for DFA with output such that it matches expressiveness of NFA with unique output. From J. Berstel, *Transductions and context-free languages* Chapter IV, 5 Bimachines

> **Definition** A *bimachine* $\mathfrak B = \langle Q, q\_-, P, p\_−, \gamma\rangle$ over $A$ and $B$ is composed of two finite sets of states $Q,P$, two initial states $q\_− \in Q$, $p\_− \in P$, of two partial next state functions $Q \times A \to Q$ and $A \times P \to P$ denoted by dots, and a partial output function $\gamma : Q \times A \times P \to B^∗$.

The output of such a machine is naturally partitioned into as many parts as the input has symbols, some of these parts can be empty. To compute the $i$-th part, $Q$ processes the first $i-1$ input symbols forward, $P$ processes the last $n-i-1$ input symbols backward, and $\gamma$ computes the output from the $i$-th input symbol $a$ and the current states $q$ and $p$ of $Q$ and $P$ as $\gamma(q,a,p)$.

A partial function is rational if and only if it is realized by a bimachine. Bimachines were introduced by Schützenberger in 1961. In 2006, J. Rhodes organized a P vs NP Workshop, and where Pedro V. Silva gave an introduction to bimachines.

---

A bimachine has only a finite number of states and is deterministic, but in general it needs $O(n)$ forward and backward scans over the input. The *plurisubsequential functions* (or slight extensions of this idea) are attractive, because they only need two forward scans over the input.

---

> 1 ... If a computation in the gsm ends in some state, then the word associated with that state by the function $\rho$ is concatenated at the end of the output, provided p is defined for this state. Otherwise, it indicates that the computation is unsuccessful, and therefore that the function realized by this transducer is undefined for the given input.

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


title: purpose of supercomputers

text:
# Question
Title: purpose of supercomputers
Last fall I went on a tour of the Blue Waters supercomputer at the University of Illinois. I asked whether anyone ever used the entire computer. I was told that it was always working on multiple projects. That made me wonder about the usefulness of supercomputers. Perhaps Blue Waters is unusual in that it has to be shared by industry and the university - I don't know. I assume there's some overhead in managing the processors and memory of a single supercomputer. Would it be more cost effective to build smaller computers? Can anyone help me to understand the value of supercomputers? Or is it that sometimes they are dedicated to single projects?

# Answer
> 10 votes
A typical job on Blue Waters is using about 10% of the machine and consumes a total of 75 *node hours*. Blue Waters has about 27500 nodes, so that means some of those "75 node hour" jobs are running in just a couple of minutes. That allows scientists to use the machine somewhat interactively. (You can see the moving averages here: http://xdmod.ncsa.illinois.edu/#tg\_usage:group\_by\_Jobs\_none)

Supercomputers are just large collections of smaller computers. The main reason we collect them together in one place is that we can share the cost most efficiently that way. You are trying to create a computer that can do a lot of work, and for which the *total cost of ownership* (the total cost of the computer, the power, and the maintenance), is minimized over the lifetime of the computer.

There are several factors involved in the total cost of ownership: The cost of the equipment is one. To minimize the cost of ownership you want the equipment to be doing useful work as large a percentage of the time as possible (ideally 100% of the time, realistically somewhat less, like 95% would be considered good), until the equipment burns out or becomes obsolete. In contrast, the computer in your laptop or your phone is probably actually in use less than 10% of the time you own it (you are asleep 33% of the time, you are eating and relaxing about half the time you are awake, and even when you are "using" the computer, the processor is idle most of the time.)

The second is the cost of power. There are several parts of this: the first is the cost of the power itself. Part of that cost is consumed in transporting the power from the power plant to the computer. Part of it is lost in the computer's "power supply" (which is just converting AC power into DC power). A larger AC-\>DC converter can usually be made more efficient. Additionally computers turn useful electric power into waste heat. So you also need to pay to remove the heat. Again, larger air conditioners can usually be made more efficient than multiple small air conditioners.

The third is the cost of maintenance. By putting together a bunch of computers and designing them so that when one goes down the rest keep running you can amortize the cost of maintenance staff over a much larger number of computer nodes than you could if the nodes were all different and placed in different buildings (or cities).

The details: Blue Waters has 288 cabinets. Each cabinet has 96 "nodes". Each node is a pretty normal high-end computer. Most nodes have 2 AMD Opeteron 6276 processors running at 2.3GHz, and 64GByte of DRAM. About 1/6 of the nodes instead have a single AMD Opteron 6276, an NVidia K20 GPU, and 38GByte of DRAM. If you wanted, you could buy something similar to a "node" for about \\$3000 or \\$4000 and put it in your living room to play video games. Blue Waters has about 27648 nodes. https://bluewaters.ncsa.illinois.edu/hardware-summary

Each node probably consumes a bit more than 500 Watts, and turns that power into heat. If you had a node in your living room to play video games it wouldn't be a particularly big deal. It would consume some electricity from the wall socket and generate about as much heat as a small personal space heater. In the winter that would be kind of nice and cozy. In the summer you'd have to run your air conditioner more frequently to keep your house comfortable. If you had it running full power all day every day, your electricity bill would go up considerably, perhaps double what you are consuming now.

But when you put 27648 of them together it consumes about 15 Megawatts, and generates a correspondingly large amount of heat. The true engineering marvel of Blue Waters, like any large data center, is the building itself. It's an enormous refrigerated box. The Blue Waters building is particularly interesting because it is a fantastically efficient. About 85% of the power going into the building is actually used to run the nodes. I believe I read somewhere (can't find it at the moment) only 15% is lost in power conversion and removing waste heat. That's a lot better than what you'd get from the 500Watt gaming computer in your living room. You'd probably need a 750Watt "power supply" and another couple hundred Watts to run the air conditioner.

**TL; DR**

Let's put it all together. By putting together thousands of smaller computers and spreading the usage among many many people, we keep those computers running most of the time, sharing the resources in a very efficient way. It costs a *lot* of money to give people computers that sit idle most of the time. The best way to save money on computation is to have people share the computers so the computers are busy most of the time.

Blue Waters is much more than just the computers inside it. It is specially designed to be as power efficient as possible. Part of that involves putting it near power plants to reduce power losses in power transmission lines. Here's a satelite picture of the part of Champaign IL containing Blue Waters to demonstrate:

# Answer
> 4 votes
supercomputers are extremely important in modern research. they are not always used at total capacity depending on a supply/ demand/ management dynamic, and a continual upgrade/ replacement cycle. there are massive supercomputers used in the defense industry for weapons simulations (matching one of the early rationales/ impetuses for the invention of the computer in WWII, computing projectile trajectories). this use is not highly publicized. the modern weapon simulations are for nuclear weapons and are highly classified. the simulations allow new weapons designs to be "tested" accurately via computational simulations only. the US even rejects export of advanced computing technology to other countries eg China for this reason, because supercomputing has national security implications if another country can do effective supercomputing simulations.

there are many other uses. they can be used to simulate product design dynamics. for example the Tide company needed to figure out how to mix different ingredients in their laundry soap in an optimal way, and supercomputers were used to help compute the optimum mix.

most supercomputers involve running multiple different projects. they are used as shared resources and the management has strategies for choosing projects based on their overall load, research value, etc.

the basic value of supercomputers is that very large scale computations simply cannot be run on "smaller" computers with less overall CPU capacity. but in the last decade there has been a major shift toward building supercomputers with "commercial off the shelf" technology (aka COTS) which decreases their price and they still have very high performance.

wikipedia mentions basic uses of supercomputers, this is a partial list.

* 1970s / Weather forecasting, aerodynamic research (Cray-1).\[83\]
* 1980s / Probabilistic analysis,\[84\] radiation shielding modeling\[85\] (CDC Cyber).
* 1990s / Brute force code breaking (EFF DES cracker).\[86\]
* 2000s / 3D nuclear test simulations as a substitute for legal conduct Nuclear Non-Proliferation Treaty (ASCI Q).\[87\]
* 2010s / Molecular Dynamics Simulation (Tianhe-1A)\[88\]

---
Tags: computer-architecture
---


# Question
Title: Split in AVL tree with complexity $O(\log n)$
Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.

The split operation divides the AVL tree into two derived AVL trees, based on key. One of the derived trees should contain all the vertices in which all keys less than the original key, and the second the rest.

I know this can be done in $O(\log^2 n)$ time. Here's a link to implementation with complexity $O(\log^2 n)$: https://code.google.com/p/self-balancing-avl-tree/

I also know how to merge two AVL trees, such that the keys of one tree are all smaller than the keys of the other, in $O(\log n)$ time. Here's an implementation with complexity $O(\log n)$:

```
def Merge(l, r) {
    if (!l || !r)
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}

```

# Answer
Yes, this is possible.

You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.

One of the key insights is that the merge function you mention is, with more careful accounting, $O(h\_1 - h\_2)$, where $h\_1$ is the height of the taller tree and $h\_2$ is the height of the shorter tree. As such, merging a list of trees that have descending or ascending heights costs only $O(h\_{\max} - h\_{\min})$, since the sum telescopes.
> 7 votes

# Answer
Let us define a function `split(T,v)` that takes in a tree, `T` and a value to split at, `v`. Suppose that each node of the tree stores its left child and right child in addition to the value at that node. Use the following algorithm:

1. First we check to see if the input tree is simply a leaf or not.
2. If `T` is not a leaf, compare the value of its root node, `v'` with `v`.
3. If `v' < v` then recursively call split on the left subtree. Store the values of the recursive call as `L'` (returned left tree), `R'` (returned right tree), and `r` (option type indicated if the value `v` was found or not). Construct the new right tree, `newR = Node(R',v',R)`, and return `(L',r,newR)`.
4. Else if `v' > v` then recursively call split on the right subtree. Store the values of the recursive call as `L'` (returned left tree), `R'` (returned right tree), and `r` (option type indicated if the value `v` was found or not). Construct the new left tree, `newL = Node(L',v',L)`, and return `(newL,r,R')`.
5. Else if `v' = v`, return `L, SOME(v), R`.
6. If `T` is a leaf, we must have reached the root of the tree without finding the input value v to split at. Return that you couldn't find the leaf by passing back `NONE`.

Why is this logarithmic? Well, you only ever traverse one root-to-leaf path of the tree, at most. We can easily reconstruct nodes in constant time since we're just re-assigning $O(\log n)$ references (in an imperative language) or reassigning $O(\log n)$ values that take a constant time to generate (in a functional language).

Here's the corresponding code for the algorithm. It's written in SML, but I'd be willing to clarify what anything means in the comments.

`fun split(T,v) =
 case T of
 Leaf => (Leaf, NONE, Leaf)
 | Node(L,v,R) =>
 case compare(v, v') of
 LESS =>
 let
 val (L',r,R') = split(L,k)
 in
 (L',r,Node(R',r,R))
 end
 | GREATER =>
 let
 val (L',r,R') = split(R,k)
 in
 (Node(L',v',L),r,R')
 end
 | EQUAL => (L, SOME(v), R)`

See this document for more details. It provides a more thorough explanation of the above.
> -1 votes

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


# Question
Title: Can Reduction for Undecidability/Decidability Problems Go Both Ways?
This Problem sparked my question: Does a TM $M$ enter state $q$ on input $w$?

I proved it was undecidable in this format using the Halting Problem as a subroutine:

`If HALT
 simulate M on w and return result
 else
 return false`

Since HALT is undecidable, this given problem is undecidable as well.

However, the given solution proved in the opposite way, by creating a decider for the problem, and using it as a subroutine to solve the Halting Problem.

Is my direction of the proof still valid, and can my approach be used to prove other undecidable problems (using a known undecidable problem as a subroutine rather than the other direction)?

# Answer
> 2 votes
When proving decidability of a new problem, you reduce the new problem (i.e. a problem with unknown solution) to an old one (used as subroutine) with a known solution, so that the techniques used to solve the old one can be used to solve the new one.

But, when proving undecidability, you have to do the opposite. You reduce the old problem, known to be undecidable, to the new problem (used as subroutine), in such a way that, if the new problem has a decision procedure, its use as a subroutine provides a decision procedure to the old problem, known not to have any. Hence the new problem cannot have a solution, and is undecidable.

In your example, you should have tried to show that if you have a decision for your new problem, that you can use as subroutine, then you ave a decision for the halting problem, which is not possible.

So proofs go both ways only in the sense that the contrapositive of a statement goes the other way. Decidability goes one way, and undecidability goes the other way.

However, it you can do the reduction both ways at the same time (either both for decidability or both for undecidability), then you have proved that the two problems are strictly equivalent, and that any solution for one is a solution for the other. When it goes only one way, this establishes that one problem is harder than the other (letting you work out which is which).

I guess that is about all I can say about the "direction"of the proof.

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