# Question
Title: Clear, intuitive derivation of the fixed-point combinator (Y combinator)?
The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as:

FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y))$

I understand its purpose and I can trace the execution of its application perfectly fine; **I would like to understand how to derive FIX from first principles**.

Here is as far as I get when I try to derive it myself:

1. FIX is a function: FIX $\triangleq \lambda\_\ldots$
2. FIX takes another function, $f$, to make it recursive: FIX $\triangleq \lambda f.\_\ldots$
3. The first argument of the function $f$ is the "name" of the function, used where a recursive application is intended. Therefore, all appearances of the first argument to $f$ should be replaced by a function, and this function should expect the rest of the arguments of $f$ (let's just assume $f$ takes one argument): FIX $\triangleq \lambda f.\_\ldots f~(\lambda y. \_\ldots y)$

This is where I do not know how to "take a step" in my reasoning. The small ellipses indicate where my FIX is missing something (although I am only able to know that by comparing it to the "real" FIX).

I already have read Types and Programming Languages, which does not attempt to derive it directly, and instead refers the reader to The Little Schemer for a derivation. I have read that, too, and its "derivation" was not so helpful. Moreover, it is less of a direct derivation and more of a use of a very specific example and an ad-hoc attempt to write a suitable recursive function in $\lambda$.

# Answer
I haven't read this anywhere, but this is how I believe $Y$ could have been derived:

Let's have a recursive function $f$, perhaps a factorial or anything else like that. Informally, we define $f$ as pseudo-lambda term where $f$ occurs in its own definition:

$$f = \ldots f \ldots f \ldots $$

First, we realize that the recursive call can be factored out as a parameter:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}\_{M} f$$

Now we could define $f$ if we only had a way how to pass it as an argument to itself. This is not possible, of course, because we don't have $f$ at hand. What we have at hand is $M$. Since $M$ contains everything we need to define $f$, we can try to pass $M$ as the argument instead of $f$ and try to reconstruct $f$ from it later inside. Our first attempt looks like this:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}\_{M} \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}\_{M}$$

However, this is not completely correct. Before, $f$ got substituted for $r$ inside $M$. But now we pass $M$ instead. We have to somehow fix all places where we use $r$ so that they reconstruct $f$ from $M$. Actually, this not difficult at all: Now that we know that $f = M M$, everywhere we use $r$ we simply replace it by $(r r)$.

$$f = \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}\_{M'} \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}\_{M'}$$

This solution is good, but we had to alter $M$ inside. This is not very convenient. We can do this more elegantly without having to modify $M$ by introducing another $\lambda$ that sends to $M$ its argument applied to itself: By expressing $M'$ as $\lambda x.M(xx)$ we get

$$f = (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}\_{M}(xx)) (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}\_{M}(xx))$$

This way, when $M$ is substituted for $x$, $MM$ is substituted for $r$, which is by the definition equal to $f$. This gives us a non-recursive definition of $f$, expressed as a valid lambda term!

The transition to $Y$ is now easy. We can take an arbitrary lambda term instead of $M$ and perform this procedure on it. So we can factor $M$ out and define

$$Y = \lambda m . (\lambda x. m(xx)) (\lambda x.m(xx))$$

Indeed, $Y M$ reduces to $f$ as we defined it.

---

*Note:* I've derived $Y$ as it is defined in literature. The combinator you've described is a variant of $Y$ for call-by-value languages, sometimes also called $Z$. See this Wikipedia article.
> 37 votes

# Answer
As Yuval has pointed out there is not just one fixed-point operator. There are many of them. In other words, the equation for fixed-point theorem do not have a single answer. So you can't derive the operator from them.

It is like asking how people derive $(x,y)=(0,0)$ as a solution for $x=y$. They don't! The equation doesn't have a unique solution.

---

Just in case that what you want to know is how the first fixed-point theorem was discovered. Let me say that I also wondered about how they came up with the fixed-point/recursion theorems when I first saw them. It seems so ingenious. Particularly in the computability theory form. Unlike what Yuval says it is not the case that people played around till they found something. Here is what I have found:

As far as I remember, the theorem is originally due to S.C. Kleene. Kleene came up with the original fixed-point theorem by salvaging the proof of inconsistency of Church's original lambda calculus. Church's original lambda calculus suffered from a Russel type paradox. The modified lambda calculus avoided the problem. Kleene studied the proof of inconsistency probably to see how if the modified lambda calculus would suffer from a similar problem and turned the proof of inconsistency into a useful theorem in of the modified lambda calculus. Through his work regarding equivalence of lambada calculus with other models of computation (Turing machines, recursive functions, etc.) he transferred it to other models of computation.

---

How to derive the operator you might ask? Here is how I keep it in mind. Fixed-point theorem is about removing self-reference.

Everyone knows the liar paradox:

> I am a lair.

Or in the more linguistic form:

> This sentence is false.

Now most people think the problem with this sentence is with the self-reference. It is not! The self-reference can be eliminated (the problem is with truth, a language cannot speak about the truth of its own sentences in general, see Tarski's undefinability of truth theorem). The form where the self-reference is removed is as follows:

> If you write the following quote twice, the second time inside quotes, the resulting sentence is false: "If you write the following quote twice, the second time inside quotes, the resulting sentence is false:"

No self-reference, we have instructions about how to construct a sentence and then do something with it. And the sentence that gets constructed is equal to the instructions. Note that in $\lambda$-calculus we don't need quotes because there is no distinction between data and instructions.

Now if we analyse this we have $MM$ where $Mx$ is the instructions to construct $xx$ and do something to it.

> $Mx = f(xx)$

So $M$ is $\lambda x. f(xx)$ and we have

> $MM = (\lambda x. f(xx))(\lambda x. f(xx))$

This is for a fixed $f$. If you want to make it an operator we just add $\lambda f$ and we get $Y$:

> $Y = \lambda f. (MM) = \lambda f.((\lambda x. f(xx))(\lambda x. f(xx)))$

So I just keep in mind the paradox without self-reference and that helps me understand what $Y$ is about.
> 11 votes

# Answer
So you need to define a fixed point combinator

```
fix f = f (fix f)
      = f (f (fix f))
      = f (f (f ... ))

```

but without explicit recursion. Let's start with the simplest irreducible combinator

```
omega = (\x. x x) (\x. x x)
      = (\x. x x) (\x. x x)
      = ...

```

The `x` in the first lambda is repeatedly substituted by the second lambda. Simple alpha-conversion makes this process clearer:

```
omega =  (\x. x x) (\x. x x)
      =α (\x. x x) (\y. y y)
      =β (\y. y y) (\y. y y)
      =α (\y. y y) (\z. z z)
      =β (\z. z z) (\z. z z)

```

I.e. the variable in the first lambda always disappears. So if we add an `f` to the first lambda

```
(\x. f (x x)) (\y. y y)

```

the `f` will bob up

```
f ((\y. y y) (\y. y y))

```

We have got our `omega` back. It should be clear now, that if we add an `f` to the second lambda, then the `f` will appear in the first lambda and then it will bob up:

```
Y f = (\x. x x)     (\x. f (x x))
      (\x. f (x x)) (\x. f (x x)) -- the classical definition of Y

```

Since

```
(\x. s t) z = s ((\x. t) z), if `x' doesn't occur free in `s'

```

we can rewrite the expression as

```
f ((\x. x x) (\x. f (x x))

```

which is just

```
f (Y f)

```

and we have got our equation `Y f = f (Y f)`. So the `Y` combinator is essentially

1. double the `f`
2. make the first `f` bobbed up
3. repeat
> 3 votes

# Answer
You may have seen the classic example of an equation without a normal form:

$$(\lambda x.xx)(\lambda x.xx) \triangleright (\lambda x.xx)(\lambda x.xx)$$

A similar equation is suggested by that for general recursion:

$$\begin{array} {rr} & (\lambda x.R(xx))(\lambda x.R(xx)) ~\\ \triangleright & R(~ (\lambda x.R(xx))(\lambda x.R(xx))~) \\ \triangleright & R(R(~ (\lambda x.R(xx))(\lambda x.R(xx))~)) \\ \triangleright & \dots \end{array} \tag{A}$$

**(A)** is a way to write general recursive equations in lambda calculus (beyond primitive recursive). So how you solve the equation $Yf = f(Yf)$ ? Plug $f$ in for $R$ in the above equation to get:

$$Yf = (\lambda x.f(xx))(\lambda x.f(xx))$$ $$Y = \lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$
> 3 votes

# Answer
Instead of starting with the properties of $\mathrm{Y}$, start with a term that explicitly refers to itself:

$$\textbf{letrec }f = \ldots f \ldots f \ldots \textbf{ in } f$$

and consider how it could be expressed without $\textbf{letrec}$.

You can get an equivalent term by passing $f$ as an argument to itself at each call site:

$$\textbf{let }f f' = \ldots f' f' \ldots f' f' \ldots \textbf{ in } f f$$

As this point, we have already accomplished the interesting part of this construction: effective self reference in a language that lacks explicit self reference. This is enough to show that the language is inconsistent as a logic, or to simulate a Turing machine in it. You don't need a $\mathrm{Y}$ combinator as such – that is, self-referencing expressions needn't contain any subexpression with the properties of $\mathrm{Y}$.

---

If you want to define $\mathrm{Y}$ anyway, that's easy too: it takes a function of the form $(λg'.\ \ldots g' \ldots g' \ldots)$ and returns an expression equivalent to the above. Therefore, you can take\*

$$\mathrm{Y}\\,g = \textbf{let }f f' = g (f' f') \textbf{ in } f f$$

To convert this to a term in the pure lambda calculus, replace the function arguments with lambdas:

$$\mathrm{Y} = λg. \textbf{let }f = λf'. g (f' f') \textbf{ in } f f$$

and then replace $\textbf{let }x = e' \textbf{ in } e$ with either $e\[e'/x\]$ or $(λx.e)e'$, whichever is your preferred interpretation of $\textbf{let}$. This gets you either

$$\mathrm{Y} = λg. (λf'. g (f' f')) (λf'. g (f' f'))$$

or

$$\mathrm{Y} = λg. (λf. f f) (λf'. g (f' f'))$$

I find both of those forms far more confusing than the $\textbf{let}$ form, which is why I used $\textbf{let}$ throughout this answer. You can use $\textbf{let}$ without sullying the purity of the calculus if you interpret it as a meta-notation like $e\[e'/x\]$ rather than an expression form.

---

* In an eagerly evaluated programming language, this is not equivalent because it evaluates $(f' f')$ too early. You can fix that by replacing $(f' f')$ with $(λx. f' f' x)$. With the substitution interpretation of $\textbf{let}$ and renaming of variables, that yields the FIX from the question.
> 2 votes

# Answer
`M a = a a` is the self-applicator combinator that receives a function and applies it to itself. The trick of passing itself as an argument is essential. Now,

```
y = f x   // function
y = f y   // fixed-point function

```

The problem is `y` is referring to itself before being assigned; so we use the *trick* above.

```
y = (x x)
x x = f (x x)    // x is the name of the function which is ALSO the first argument

```

The problem is **where does `f` come from?**

There are a couple of ways to pass `f` in `x x = f (x x)`.

```
#1:
    x = (L f)     // introduce a new function L
    (L f) (L f) = f ((L f) (L f))

#2:
    x x f = f (x x f)    // pass directly

NOTE: in both cases the pattern Y = f(Y)

```

**The first method gives us Curry's Y-combinator. The second gives us Turing's!**

We could end here, but for completeness we convert to the typical lambda notation you find in literature.

### Curry's

```
(L f) (L f) = f ((L f) (L f)) where L a b = a (b b)
L = λf.λx. f (x x)
Y = λf. (L f) (L f)
Y = λf. (λx.f(x x)) (λx.f(x x))

```

### Turing's

```
x x f = f (x x f)
U U f = f (U U f) where U a b = b(a a b)
Y = U U
Y = λf.((λx.λy.y(x x y)) (λx.λy.y(x x y)))

```
> 0 votes

# Answer
Having a *one-step* functional $G := (\lambda r.\lambda x.\ \dots r\dots)$ where $r$ is used for a "recursive" call (or calls), the corresponding recursive function denoted by the $\lambda$-term $R$ must fulfill

$$R = G\ R = G(GR) = \dots $$

precisely because $r$ is used for the recursive call(s).

Lambda terms have no names, but they can be passed as arguments to other terms, which will thus be able to refer to them. Thus we seek lambda terms $M$, $N$ such that

$$MN = G\ (NN) = G(G(NN)) = \dots $$

but we must have $R = GR$, thus $MN = NN$ i.e. $M = N$:

$$MM = G\ (MM) = G(G(MM)) = \dots $$

The term $M$ must depend on $G$ to be able to recreate it that way; thus we seek

$$ M = HG \\ HG(HG) = G(HG(HG))$$

i.e., with the *combinators* $C$, $B$ and $Ux = x\ x$, $H$ is a plain combinator defined as

$$ Hgz = g(z\ z ) = g(Uz) = CBUgz $$

which, when self-applied with any given appropriate $G$ term as seen above, will achieve what we want. Thus,

$$Yg = Hg(Hg) = U(Hg) = BU(CBU)g$$

or in lambda notation,

$$ H = \lambda g. \lambda z. g(z\ z) \\ Y = \lambda g. (\lambda z. g(z\ z))\ (\lambda z. g(z\ z)) $$
> 0 votes

---
Tags: computability, logic, programming-languages, lambda-calculus, combinatory-logic
---


title: What does RSGD stand for?

text:
# Question
Title: What does RSGD stand for?
I'm reading a paper that involves an algorithm for RSGD. It's clearly a form of stochastic gradient descent, but I can't find what the R stands for. The authors provide their own implementation of it, and I would like to find its original formulation to compare.

# Answer
It's probably Riemannian stochastic gradient descent (R-SGD), (Stochastic Gradient Descent on Riemannian Manifolds).

You'll find several articles on the subject by searching for this term.
> 3 votes

---
Tags: gradient-descent
---


# Question
Title: $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
About the language $L=\\{\<M\>|M~is~a~TM~and~L(M)=\\{0^n1^n|n\ge0\\}\\}$

I want to determine if it is in RE / coRE or neither.

I think that I found a mapping reduction from $\overline{A\_{TM}}$ to $L$, where $\overline{A\_{TM}}=\\{\<M,w\>|M~is~a~TM~and~M~does~not~accept~w\\}$:

Define $f(\<M\>)=\<N\_{M,w}\>$ as follows:

$N\_{M,w}=$ "On input $x$:

1. If $x='01'$, accept
2. Run $M$ on $w$ and do as $M$ does."

So if $\<M,w\>\in\overline{A\_{TM}}$ we have $L(N\_{M,w})=\\{01\\} \in L$.

If $\<M,w\>\notin\overline{A\_{TM}}$ we have $L(N\_{M,w})=\Sigma^\* \notin L$

But I don't know if I am able to construct a TM for $\overline{L}$ or find another reduction from a RE language to $L$.

Any help?

Thanks!

# Answer
If you want ro prove that L-complement is RE, you can construct a TM which enumerates L-complement. L-complement contains the M's which are not some Turing machine's code or they are code of Turing machines that accept some input which is not in the form of 0'1' . If such an input exists, It can be computably found. So L-complement is re because both following sets are re:

A = { \< M \> | M is not a Turing machine code.}

B = {\< M \> | M is a Turing machine which accepts some input which is not in the form of 0'1'}

And

L-complement = A U B

It is a theorem that if A and B are r.e sets, then so is A U B
> 1 votes

---
Tags: complexity-theory, turing-machines, computability, automata, reductions
---


# Question
Title: If $B \in RE$ then $A \in RE$ - Reduction
I know that if there is a Turing Reduction from $A$ to $B$, say $A \le\_T B$, and $B \in R$ then $A \in R$.

I also know that Turing Reduction is for Decision, and not Recognition.

Is it possible to design a new type of reduction, such that if $B \in RE$ then $A \in RE$ ?

Thank you!

# Answer
Actually Mapping reduction is the reduction that can do that.

Mapping reduction is defined as A is many reducible to B if there is some computable((recursive))function say f such that For all x, x belongs to A if and only if f(x) belongs to B. It can be proved that in many one reducability if B is r.e, then so is A.
> 0 votes

---
Tags: complexity-theory, turing-machines, computability, reductions, turing-recognizable
---


# Question
Title: How are enumerator programs formally defined?
Enumerator programs appear quite often in even an elementary computer science textbook without a formal definition. It does not seem to fit the standard definition of a computable function (through mu recursion, Turing machines or lambda calculus), which takes a single input and a single output.

What's a standard literature definition of an enumerator program? I would imagine either:

1. A computable function that takes in an additional input `i` and returns the `i`th entry of the sequence, or
2. A computable function `f(x, y)` that takes in some "state" `x` from the previous step, as well as some extra input `y` at the current step.

# Answer
> 0 votes
One possible answer can be that an enumerater program for a set say A is actually made of two other program:

One is the program that computes A'enumerating function((a total function which its range is A)). Let's call this function f.

So it is a program that takes some natural number say m and returns f(m)

The other program is a program which is on an infinite loop and produces each natural number and gives it as input to first program.and the results are printed one after the other.

It can be helpful to consider an enumerater program as a program which takes some input ((like the on and off button)) and runs into an infinite loop and never stops.

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


# Question
Title: Doubt on nearest-neighbour approach to solve TSP
I am a math undergrad and we have algorithms as one of our courses. We came across TSP and algos to solve them. I thought of an algorithm and apparently its already known as the Nearest Neighbour algorithm. Could anyone tell why it might lead to longer tours with instances (short numerical examples maybe) ?

***Thanks in advance!***

# Answer
Consider the following points on a line, where $0$ is the starting point: $0, 1, -2, 5$. An optimal tour has length $14$, while your algorithm produces a tour of length $1 +3+7+5 = 16$.
> 2 votes

---
Tags: traveling-salesman
---


title: BPP is closed to Symmetric difference?

text:
# Question
Title: BPP is closed to Symmetric difference?
How can I prove that BPP is close to Symmetric difference? I tried to find proof online but couldn't. Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to proof?

# Answer
Let $A, B \in BPP$, and let $\mathcal{A}$ (resp. $\mathcal{B}$) be an algorithm for $A$ (resp. $B$) with a probability of error of at most $\frac{1}{3}$.

Given $x$ the following algorithm decides whether $x \in A \Delta B$ with a probability of error of at most $\frac{1}{3}$:

* Perform nine independent executions of $\mathcal{A}(x)$.
* Perform nine independent executions of $\mathcal{B}(x)$.
* If the majority of the executions of $\mathcal{A}(x)$ had a different outcome (i.e., accept or reject) than the majority of the executions of $\mathcal{B}(x)$ then accept. Otherwise reject.

The probability that the majority outcome among of the executions of $\mathcal{A}(x)$ (resp. $\mathcal{B}(x)$) does not match whether $x \in A$ (resp. $x \in B$) is at most the probability that at least $5$ out of the $9$ executions fail. I.e., it is at most: $$ \sum\_{i=5}^9 \binom{9}{i} \left( \frac{1}{3} \right)^i \left( \frac{2}{3} \right)^{9-i} = \frac{2851}{19683} \< \frac{1}{6}. $$

Using the union bound, the probability that *at least one* of the majority outcomes of $\mathcal{A}(x)$ and $\mathcal{B}(x)$ is incorrect is less than $2 \cdot \frac{1}{6} = \frac{1}{3}$. Whenever both the majority outcomes are correct, the result of the above algorithm is also correct.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: A bipartite maxiumum matching problem, fitting a ratios vector on the resulting subset
**Statement of problem**

We have two sets of vertices, $V$ and $U$, each of which has a vector of attributes $A$.

The set of edges $E$ is defined such that there is an edge $vu\in{E}$ between vertices $v$ with attributes $\[a\_1,a\_2,...\]$ and $u$ with attributes $\[a'\_1,a'\_2,...\]$ IFF a function $f(\[a\_1,a\_2,...\],\[a'\_1,a'\_2,...\])=true$.

It is allowed to match each vertex in $V$ up to $m$ times, and each vertex in $U$ up to $n$ times.

We need a maximum matching betteen $V$ and $U$.

This was the original problem, and we have a working solution for this.

We now have an additional requirement.

Vertices in $U$ have an additional attribute $s\in{S}$. $S$ is a finite set. We have a vector $R$ of ratios for $S$ (that is, if $S = \\{s\_1,s\_2,...,s\_{|S|}\\}$, a vector $\[r\_1,r2,...,r\_{|S|}\]$ such that for each $i$, $0\le{r\_i}\le1$, and $\sum\_1^{|S|}{r\_i}=1$ ).

We need the set $U'$ of matched vertices from $U$, from the maximum matching, to fit this vector of ratios as best it can. To put it more formally, we also have a function $g(U')$ which takes a subset $U'\subseteq{U}$, calculates $\[\frac{freqency(s\_1)}{|U'|},\frac{freqency(s\_2)}{|U'|},...\]$, and calculates a distance between that and our vector $R$. We need to produce a maximum matching with minimum $g(U')$.

Due to the nature of our data, there may be many maximum matchings. So the aim is to select the maximum matching that minimizes $g(U')$. That is, getting maximum coverage is first priority, the ratios are second priority.

**The existing solution**

If possible, we would like to do this as an extension to our existing implementation rather than start from scratch. So here is how we solved the first part of the problem.

* We noticed that many vertices in $V$ and $U$ had the same vector of attributes $A$. So we decided to define new artificial sets of vertices $V\_{agg}$ and $U\_{agg}$, which had one vertex for each of the existing vectors. Each $v\_{agg}$ also carries the number of vertices in $V$ that it stands for, $w$, and $u\_{agg}$ the number of vertices in $U$ it stands for, $w'$. We kept a record of the exact vertices represented by each $v\_{agg}$ and $u\_{agg}$.
* We break the graph into connected components and solve each independently.
* We use a flow network to represent the graph.

+ From the source to each $v\_{agg}$, we have an edge with weight $m\times{w}$.
    + from each $v\_{agg}$ to each $u\_{agg}$ for which $f(A,A')=true$, we have an edge whose weight is infinite.
    + from each $u\_{agg}$ to the sink, we have an edge with weight $n\times{w'}$.
* We solve for maximum flow using Push-Relabel
* Once we have final weights on the edges (the ones who had infinite capacity), we use those to create individual matches between the original vertices.

**The question**

* How can we adjust the maximum flow algorithm so it also minimizes the ratio distance function?
    + I realize that we might not be able to break the data into connected components because the ratios are over the entire output set.
    + We may also need to aggregate the vertices in $U\_{agg}$ more finely - group together vertices that share both the same $A'$ and the same value of $s$.
* If not possible, is there another algorithm that will do this?
* If not possible, is there a sub-optimal solution? The coverage needs to be maximum, but we can be somewhat lenient about the distance function $g(U')$, i.e., it's good enough if $g(U')\lt{k}$ for a given $k$.

# Answer
Try using (integer) linear programming.

The matching problem can be expressed as a linear programming instance. In particular, you have a variable $x\_{u,v}$ for each pair of variables joined by an edge, with the intended meaning that $x\_{u,v}=1$ means $(u,v)$ is included in the matching and $x\_{u,v}=0$ means it is not; then you can write down linear inequalities to capture a maximum matching (e.g., $0 \le x\_{u,v} \le 1$, $\sum\_u x\_{u,v} \le 1$, $\sum\_v x\_{u,v} \le 1$, maximize $\sum\_{u,v} x\_{u,v}$).

In your case, let's assume you have pre-computed a maximal matching (without additional constraints), so you know the size of the maximal matching is $s$. Now you can add the inequality $\sum\_{u,v} x\_{u,v} \ge s$.

Now add in linear inequalities to compute your distance. If you use the L2 distance, that's not expressible with linear inequalities, so I suggest you use the L1 or L$\infty$ distance. For L$\infty$ distance, add a new variable $d$, and add the inequality

$$2r\_i s - 2ds \le \sum\_{u \in S\_i,v \in V} x\_{u,v} + \sum\_{u \in V,v \in S\_i} x\_{u,v} \le 2r\_i s + 2ds$$

where here $S\_i$ is the set of vertices whose attribute is $s\_i$. Then find a solution to the linear program that minimizes $d$. For L1 distance, we're going to do almost the same: add variables $d\_1,d\_2,\dots$, and for each $i$, add the inequality

$$2r\_i s - 2d\_i s \le \sum\_{u \in S\_i,v \in V} x\_{u,v} + \sum\_{u \in V,v \in S\_i} x\_{u,v} \le 2r\_i s + 2d\_i s$$

and then minimize the objective function $d\_1+d\_2+\dots$.

Now solve this with an off-the-shelf ILP solver and require that all of the $x$'s be integers. I am hopeful that the resulting ILP might be feasible, given that without the additional distance constraint it can be solved in polynomial time, but I imagine there are no guarantees.

See also https://en.wikipedia.org/wiki/Assignment\_problem#Solution\_by\_linear\_programming.
> 1 votes

---
Tags: bipartite-matching
---


# Question
Title: Inventory planning problem solved through dynamic programming
I am working on problem (15-11) Inventory planning from *Introduction to Algorithms* (CLRS, 3rd Ed).

> **15-11: Inventory Planning, p.411**
>
> The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $n$ months. For each month $i$, the company knows the demand $d\_i$, that is, the number of machines that it will sell. Let $D = \displaystyle\sum\_{i=1}^{n} d\_i $ be the total demand over the next $n$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $h(j)$ for $u = 1, 2, ... , D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j+1)$ for $j \le 1 \le D - 1$.
> Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $n$ and $D$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.

So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem: Let $MinCost(i,j)$ be the function that returns minimized cost of operation for past $i$ months, $j$ is the number of unsold machines left at the end of the month $i$.(Goal, is to calculate $MinCost(n,0)$, in other words, at the end of planning period(month $n$), there are no unsold machines.)

So, the DP recurrence is given by $MinCost(0,0) = 0$ and

$\quad MinCost(i,j) = \min\\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \\}$

for $i+j \> 0$; here, $c(k,j,i)$ is the function that calculates the costs of the production.

If my optimal sub-problem is correct, how do I create an algorithm to solve it?

# Answer
CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

* recursive top-down (p363),
* memoized (p365f) and
* bottom-up (p366).

I suggest you try to adapt one of these.
> 4 votes

# Answer
The overal idea of the sub-problem sounds good.

I've noticed a few issues:

##### What is k supposed to represent?

$j$ represents the number of machines unsold at the end of month $i$. This can't be negative as you cannot have a negative number of machines unsold, which means you sold more than what you produced!

You said you start with $MinCost(n,0)$ so you start with $j=0$, but then you need to compute $MinCost(n-1,0-k)$ and you wrote that $1 \leq k$, which leaves to negative $j$!. There seem to be an issue here.

I think your idea was that $k$ was the net difference of machines unsold on day $i$, which makes it hard to reason about.

**So let's define $k$ as the number of unsold machines at the beginning of month $i$** (= number of unsold at the end of month $i-1$).

##### What is $c(k,j,i)$?

You should have enough data to compute the costs yourself. By the new definition of $k$, $c(k,j,i)= c \cdot (j-k + d\_i - m)$. This is because you had $k$ machine at the beginning of month $i$, you have $j$ machines at the end of that month and you sold $d\_i$ machines, so you produced $j-k + d\_i$ machines that month. You can produce $m$ machines without any additional cost so the remaining number of machine costs $c$ dollars per machine.

Please note that this value cannot be negative, as you can't get back the costs if you have to build less than $m$ machines. So $c(k,j,i)= max(0, c \cdot (j-k + d\_i - m))$.

##### This brings us to

$\quad MC(i,j) = \min\\{MC(i-1,k) + max(0, c \cdot (j-k + d\_i - m)) + h(j) \mid 0 \le k \le D \\}$

With $MC(0, j) = \begin{cases} 0 & \quad \text{if } i = 0\\ \+ \infty & \quad \text{if } i \neq 0 \end{cases}$

Because you can't have machines in stock before the first day.

We could make some optimisation on the max value of $k$ but it's a bit hard to compute and won't improve the asymptotic complexity.

I believe this should be enough to write the algorithm.
> 0 votes

# Answer
I was visiting the dynamic programming questions in the CLRS the other day, and I saw this problem. I think this can be solved in $O(nD)$.

Let $C(i,j)$ be the minimum cost of producing a total of $1 \leq j \leq D$ machines at the end of $1 \leq i \leq n$ months. Since the production must meet the demand, if we have $j \< \sum\_{k=1}^i d\_k$ at month $i$ (i.e., we couldn't meet the demand), we set $C(i,j) = \infty$ since this is not a valid solution. Otherwise, at month $i$ to produce $j$ machines, where $j \geq \sum\_{k=1}^i d\_k$, we have the choice of producing $l \leq j$ machines in $i-1$ months and $j-l$ machines this month. The optimal cost of the former is given by $C(i-1,l)$ and the cost of the latter is $c \cdot (j-l-m)$. Since this value cannot be negative, we can rewrite it as $c \cdot max(0, (j-l-m))$, which makes the cost $0$ if it is negative. We also need to store the extra produced machines that are over the demand in an inventory, whose cost is $h(j-\sum\_{k=1}^i d\_k)$. This must be added to the cost above. Let $C$ be an $(n+1) \times D$ matrix. We also compute the cumulative summation of demands in an array $A$ to help checking whether we meet the demand in a particular month. Then the recursive formulation becomes:

\begin{equation} C(i,j) = \begin{cases} 0, & \text{if } i=0 \\ \infty, & \text{if } j \< A\[i\] \\ min\_{1\leq k \leq j} (C(i-1,k) + (c \cdot max((j-k-m),0)) + h(j-A\[i\])), & \text{otherwise} \end{cases} \end{equation}

The above formulation looks like $O(nD^2)$. But assume we computed $C(i,j)$ and this cell chose some $k$ in row $i-1$ as minimum. While computing $C(i,j+1)$ the minimum cell in the above row for it must either be again $k$ (i.e., $C(i-1,k)$) or $C(i-1,j+1)$. The former is because $h(j) \leq h(j+1)$ and we would choose the same minimum in the above row when computing for $j+1$ if we did not consider $C(i-1,j+1)$. By keeping a running minimum for row $i-1$, thus the runtime can be reduced to $O(nD)$.
> 0 votes

---
Tags: algorithms, dynamic-programming, check-my-algorithm
---


# Question
Title: Any hints about loop invariant of weird loop?
I have this tiny program for finding largest prime divisor (taken from Code Review Stackexchange and written by user Altinak: https://codereview.stackexchange.com/a/74792):

Here is my try to write it in pseudocode:

```
GLOBAL VARIABLE highest;

// This function takes parameters n and f with 1 <= n and 2 <= f.
// It returns n with f factored out of it.
// Also, if f divides n and if f > h then it replaces h with f

factorize(n, f) {
    if (n < f)
        return n
    while (n mod f == 0) {
        n = n / f
        if (f > highest)
            highest = f
    }
    return n
}

find(n) {
    highest = 1

    n = factorize(n, 2)
    n = factorize(n, 3)

    if (n >= 5) {
        i = 5
        while (i * i <= n) {
            n = factorize(n, i)
            n = factorize(n, i + 2)
            i = i + 6
        }
    }
    if (n == 1)
        return highest
    else
        return n
}

```

But the `while` loop in the function `find` is harder than ones I have seen before - its number of iterations aren't easy to calculate before the loop, as the variable `n` from the condition `i * i <= n` changes in the loop body.

Right now I feel like I'm stuck and have no idea how to write the loop invariant for this loop, but I will try to think of something. Meanwhile, big thanks in advance for any hints!

# Answer
> 1 votes
The invariant says that the current value of `n` is the initial value of `n` divided by all its factors in the trial sequence 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31... until `i`. Some of the numbers in this sequence are not primes, but their factors have been previously processed and simplified, so equivalently, we have `n` divided by all its prime factors until `i`.

The number of iterations of the while loop equals the number of elements of the sequence 5², 7², 11², 13², 17², 19²... that do not exceed `n[5]`, `n[7]`, `n[11]`... respectively, where `n[m]` denotes the value of `n` after all factors until `m` have been removed. So the number of iterations is also the number of elements of the sequence until the highest prime factor.

In addition, the function `factorize` executes a number of divisions equal to the multiplicity of the prime factor `f` in the number `n`. When `f` is not a prime, the function returns immediately because its factors have already been consumed; the iteration count is the same for the initial and current `n`.

Hence, the total complexity will be like the sum of the multiplicities of the prime factors of `n`, plus the highest prime factor.

---
Tags: loop-invariants
---


# Question
Title: Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?
If I understand correctly, the first incompleteness theorem says that any "effectively axiomatized" formal system which is consistent must contain theorems which are *independent* of the axioms. In other words, there are models of the system where the theorem is provably true and others where it's provably false.

This seems rather similar to how the results of code that include undefined behavior cannot be determined by the language specifications alone -- in order to say what will happen, we need information about which particular compiler is being used and possibly also what hardware system it's being run on (which of course is why it's best to avoid undefined behavior when possible).

It seems like the language specifications of a given programming language, such as C++, might be an example of an "effectively axiomatized" mathematical system, while the various implementations would represent various models of the system. And so programs containing undefined behavior would correspond to theorems independent of the axioms. Is that correct?

Or, perhaps another way to do put it is, are all Turing complete models of computation examples of formal systems to which the incompleteness theorems apply, and, if so, does that imply that programming languages that implement such models must have undefined behavior? That is, is undefined behavior a necessary result of the incompleteness theorems applying to all Turing complete models of computation?

# Answer
> 11 votes
No, it doesn't require that. These are two orthogonal issues. You can easily define a new programming language where you provide fully defined semantics for all operations; yet it can be Turing complete. For a concrete example, consider Bitwise Cycle Tag; it is Turing complete, and yet it has no undefined behavior, because the behavior is always fully defined in all circumstances.

# Answer
> 4 votes
Your intuition is incorrect. The analogies you're trying to draw are not there, even though it's understandable you would expect them.

Programming languages can be defined as formal systems, but they are of a different kind than logic. Gödel's incompleteness theorems do not apply to them, because the formal systems do not even incorporate first-order logic.

C++ is not such a language because its specification is written in English on a 1000 pages. That's an outdated way of specifying languages.

For a modern account you can have a look at several textbooks, such as Benjamin Pierce's "Type theories and programming languages" and Bob Harper's "Practical foundations of programming languages" (a PDF of an early version is available). Chapter 6 of the linked PDF explains things in detail, but briefly, there are two theorems which together give "no undefined behavior":

> **Preservation:** If a program $p$ has type $T$ and it can make an execution step $p \mapsto p'$ then $p'$ has type $T$.

> **Progress:** If a program $p$ has a type then it is either a value (final result), or it has an execution step $p \mapsto p'$.

What this says is that no well-type program will ever get stuck: either it is done (a value), or it has one more step.

Note that "undefined behavior" is not the same thing as "runs forever" (some of the other answers assumed that's what was meant).

# Answer
> 2 votes
The incompleteness theorem only applies to formal systems that can express a certain amount of arithmetic. In particular, they have to support statements of the form $\forall n\in\mathbb N. P(n)$, because the Gödel sentence has that form. If your formal system can only express statements of the form $P(n)$ for fixed $n$, then it's not Gödelizable and there is no obstacle to its being consistent and complete.

For example, if $P(n)$ is the proposition that some program has not halted after $n$ steps, $\forall n\in\mathbb N. P(n)$ is the proposition that it never halts, which may be undecidable—but even if it is, every particular $P(n)$ may be decidable.

If you want to take the position that a program's behavior is undefined if you can't determine whether it halts, then indeed a Turing-complete language must have undefined behavior, but that's stronger than the notion of well-definedness that's normally used in computer science.

---
Tags: formal-languages, programming-languages, logic, turing-completeness, incompleteness
---


# Question
Title: Can we ever achieve Turing completeness?
I want to relate **Turing completeness** to the **Halting Problem**.

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But since **Halting Problem** can't be solved by any programming language so every programming language should be **Turing Incomplete**. Right?

But every where in internet it's written that modern programming languages like **c++** are **Turing Complete**. Are they wrong or Did I Misunderstood something?

# Answer
> 33 votes
> As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task.

No. A model of computation is *Turing-complete* if it can compute any *Turing-computable function* (i.e., any computable function that *can be computed by a Turing Machine*).

An alternative, but exactly equivalent way to phrase it, is that a model of computation is Turing-complete if it can *simulate any Turing Machine*.

Another equivalent way is that a model of computation is Turing-complete if it can *simulate a Universal Turing Machine* (which is just a Turing Machine which can simulate any other Turing Machine).

Yet another way to phrase it is that a model of computation is Turing-complete if it can *simulate another Turing-complete model of computation*. This is, in fact, how most Turing-complete models of computation are proven to be Turing-complete. Usually, the proof is not done using Turing Machines but using some other, more mathematically "simple" Turing-complete model of computation such as Rule 110, Conway's Game of Life, Cyclic Tag Systems or other Tag Systems, or even by implementing an interpreter for a simple Turing-complete programming language such as Brainfuck.

> But since Halting Problem can't be solved by any programming language so every programming language should be Turing Incomplete. Right?

The Halting Problem is undecidable, which means the function $\mathit{Halts}(P, i)$ cannot be computed by a Turing Machine. That is the whole point of the Halting Problem.

Since $\mathit{Halts}(P, i)$ cannot be computed by a Turing Machine, it is irrelevant for determining Turing-completeness.

Note that Turing-completeness *only* refers to *computable functions on the natural numbers*. It does not refer to non-computable functions (such as $\mathit{Halts}(P, i)$), and it does not refer to operations which are not functions (such as printing, reading from a keyboard, launching a nuclear missile, etc.).

Also note that, according to the Church-Turing Thesis, the terms "effectively calculable", "computable", and "Turing-computable" are the same thing, meaning that everything that can be computed by a physically implementable machine *at all* can be computed by a Turing Machine, and, additionally, that the "intuitive" notion of "computable" is the same as the *formal* notion of "can be computed by a Turing Machine". Furthermore, this means that no model of computation that can be physically implemented can be more powerful than a Turing Machine.

So, in this *particular* sense, we can say that "something is Turing-complete if it can compute everything that can be computed at all". But that does *not* mean "compute any function" or "do any task".

But again, keep in mind that this only applies to computable functions on the natural numbers. For example, C++ can print to the screen, which a Turing Machine cannot. But that does not mean that C++ is more computationally powerful than a Turing Machine.

Some people have jokingly coined the term "Tetris-complete" or "Pacman-complete" to describe a programming language which can draw to the screen, receive asynchronous, interactive, input events, interact with the operating system, call third-party and system libraries, model the passage of time, etc. In other words: a programming language which can be used to implement real-world, interactive, macOS/Windows/Linux/Android/… (GUI) applications.

Most real-world programming languages are both Turing-complete and Tetris-complete, whereas the models of computation we are often talking about when discussing Turing-completeness are often not Tetris-complete: e.g., Turing Machines, λ-calculus, Rule 110, Tag Systems, etc.

OTOH, it is possible to have a programming language which is not Turing-complete but Tetris-complete. For example, it is possible to model event-driven interactivity as finite co-recursion over co-data rather than infinite recursion over data.

# Answer
> 4 votes
*Disclaimer: Please double check everything in this answer, because I am no expert on the topic.*

The Halting problem is not a necessary condition for Turing completeness. On the contrary: the Turing machine itself cannot solve the halting problem. If You did build a "machine" that *could* solve the halting problem for Turing machines, it would be, at least in that sense, *more* powerful than a Turing machine. It would be unlike anything that we think of as computers. It would be "magic".

So what does a programming language have to do to be Turing complete? It has to be able to simulate a Turing machine. To prove that, it is sufficient to write a program that simulates any Turing complete "machine", e.g. lambda calculus.

So is C++ Turing complete? Yes but it is complicated. A Turing machine has an infinitely long Tape of memory. C++ on the other hand is very much designed for finite memory. Address pointers use a fixed number of bits, which is determined at compile-time at the latest. So you cannot simply use a (doubly) linked list to simulate the tape. In other languages with a more abstract memory reference model, like Java, this is very much possible.

So how can You prove that C++ is Turing complete? You can show that any program written in lambda calculus can be translated to C++. It is not quite a simple one-to-one translation because in C++ you will have to make some extra efforts to make recursion lazy. That being said that is enough to prove that C++ is Turing complete. All you need now is a computer with infinite memory with an instruction set that allows infinite recursion and a compiler that compiles to that architecture...

Fun fact: C++ is even Turing complete during compilation thanks to template-level programming. One implication is that we cannot even determine if compilation halts.

The memory limit is, of course, more of a theoretical limitation. Writing a range of length $n$ bits to the tape, the Turing machine requires at least $n$ iterations. To write to an infinite amount of memory takes an infinite amount of time. Ain't nobody got time for that! Alternatively, You could run the machine at an infinite clock frequency, in which case you will likely run into physical limitations. So for our finite lives, finite memory is just fine.

# Answer
> 1 votes
Short answer:

* no machine can solve the Halting problem, this is a mathematical impossibility.
* a system is called Turing-complete when it is able to simulate a Turing machine.

---

It is an easy matter to program a Turing machine in C. Strictly speaking, anyway, the simulation cannot be perfect because a physical system does not have infinite resources.

# Answer
> -1 votes
The if-statement alone is fully Turing complete for any computation that can be performed, so while it would not be efficient or pretty you could write any program purely with if-statements. I think that a lot of the meaning around this term has kind of taken on a sort of extended meaning that is more like saying "can this computer write a program as if it were human" or some variation of A.I. is implied. The simple fact of the matter is that A.I. is not physically or logically possible at least within a digital computer system. The requirement of every computer is to have a predictable instruction set which is mutually exclusive to free will or arbitrary behavior, they can not mix without destroying the thing that makes it "a computer" in the first place.

Regarding the halting problem, it can be solved by any program that has the potential to be halted, it is just not something we can easily forecast or reduce the computational work so as to run a simulator in fast-forward, but in their own time each program will solve it's halting status or run indefinitely, we just can't look ahead in time with that type of problem because it's inputs and conditions rely on unknown future conditions, so it is inherently a necessarily expensive computation to perform when determining if a program will encounter a deadlock or crash.

You could design a language that has this capability to know it's future halting status or potential, but in creating the bounds needed to construct that type of language we would need to remove it's turing completeness to some degree so that it operates within a finite set of possible conditions... the trade off is diversity in the language's complexity for ability of the compiler to forecast something like a halting condition.

---
Tags: turing-machines, programming-languages, halting-problem, turing-completeness
---


title: Sign confusion in a BFS lemma

text:
# Question
Title: Sign confusion in a BFS lemma
I have a confusion related the Lemma 22.1 in Cormen Leiserson Rivest Stein's Introduction to Algorithm book,

Here it is written that delta(s,v) \<= delta(s,u) +1 ,where s,u,v are the vertices of a graph G My question is why \<= is used ? Won't that be = only ? I am learning Algorithms and Data Structures.

# Answer
> 0 votes
Consider the graph $G = (V,E)$ with $V = \\{s,u,v\\}$ and $E =\\{ (s,u), (s,v), (u,v) \\}$. You have: $$ \delta(s,v) = 1 \< 1+1 = \delta(s,u) + 1. $$

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Why Minimum circuit size problem is important?
Given a truth table, find the smallest size circuit computing it. Recently it was shown that for multiple output function the problem MSCP (Minimum Size Circuit Problem) is NP-Complete. The article is available online see.

**Question:** What will be the impact of this problem? or I am not able to follow why this problem MSCP is so important?

I didn't read the article completely, only the introduction part, it seem to me that problem is related to many other problems of interest.

# Answer
Finding the *minimum* size circuit is not important in practice for large circuits. Finding *small* size circuits is of course important because it directly impacts the cost of building a circuit.

Finding minimum size circuits for small circuits that are used as building blocks is quite important. For example, you'd want to know how to build the smallest possible full adder if you end up having a million of them in a processor. And you really want a minimum size circuit for a bit of memory in your L3 cache when your processor has 36MB of L3 cache or 288 million of these cells.

However, minimising the delay of a circuit is also important, and sometimes more important or even far more important than minimum size.
> 4 votes

# Answer
# Meta Complexity

MCSP is one of the two signature problems in the subfield of meta-complexity. You could say that meta-complexity itself is on the bleeding edge of the P=NP problem. Since the full problem is so difficult to resolve, we are forced to attack it from many angles. Impagliazzo described 5 Worlds of complexity relative to the P=NP question. MCSP may help eliminate one or more of these worlds from possibility, getting us a little closer to the final result.

I don't think MCSP as studied by complexity researchers has anything to do with real-world circuit optimization, because there are many other considerations when designing real circuits that are completely ignored by MCSP. The most trivial example is that theoretical circuits do not need to concern themselves with fan-in and fan-out, while real circuits do, as this can affect the voltage and current within the circuit at extreme levels.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Why does the machine word size need to be bigger than clog(n)
I am watching MIT's Introduction to Data Structure and there is something I'm not understanding at the 14:48 mark

Why does the machine word size, w have to be \>= lg(n) where n is the length of a static array?

As I understand a static array, `[1,2,3]` is stored consecutively in the RAM like:

$$|\*|\*|1|2|3|\*|\*|\*|$$

If each element in the array is stored in a word size w then wouldn't w have to be larger than lg(i)?

If I am storing a number equal to or smaller than 31, then the word size required is

$$w=ln(31)=5 ~bits$$

So as long as my array doesn't include an element \>31 then wouldn't my word size be fine at 5 bits?

# Answer
> 1 votes
Maybe the lecture is assuming the Transdichotomous RAM Model. Under this assumption and with respect to algorithms involving arrays, you can access elements in $O(1)$, since this allows storing of indices in a single machine word. Because there are $n$ possible elements, at least $O(\log n)$ bits are needed to store an index $0 \le i \le n-1$. Note that this size is a lower-bound on the word size and $w$ can be bigger than $\log n$, to allow storage of values that are reasonably larger than $n$.

This $O(1)$ access time is quite reasonable in most cases and simplifies analysis of array operations since the running-time would just be counting the number of access.

# Answer
> 1 votes
It’s the other way round: it’s not the array size determining the word size. It’s the word size determining the maximum possible array index and therefore the maximum array size.

Take for example a word size of 32 bits. A word can hold values from 0 to $2^{32}-1$.

Now you want an array with $2^{32}+1$ elements. According to the formula, the word size is too small or the array size is too large.

And you can see that you need an index of $2^{32}$ to access the last array element, which does not fit into a word. That’s the reason why the size of the largest array is limited.

You just confused yourself by looking at tiny arrays. This is about big arrays. A 16 bit processor cannot have arrays with more than 65,536 elements. A 32 bit processor cannot have arrays with more than about 4 billion elements and so on.

# Answer
> 0 votes
You understand that $n=2^b$ numbers are stored at addresses $0$ to $n-1=2^b$.

What matters in this discussion is that the word size is a $\Theta(\log(n))$ function.

# Answer
> 0 votes
Word size determines the amount of memory that can be addressed. For example, if we have 4GB of RAM, then the word size should be 32 bits

```
 log2(4GB) = 31.89 bits, or 32 bits approximately
 word size to address 4GB should be >= 32 bits

```

So, it means in

---
Tags: algorithms, time-complexity, data-structures
---


# Question
Title: Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?
I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me:

* Unrecognizable languages can be accepted by a Turing machine, but the machine may not always halt on inputs outside the language.
* Undecidable languages cannot be decided by a Turing machine for all possible inputs; there is no algorithm that can determine membership for every input in these languages.

I am new to this topic, so I could be wrong, but I think that both of these are incorrect. I think the definition for unrecognizable languages it gave me is actually the definition for recognizable languages, because the a recognizer accepts strings in the language while it rejects or loops on everything else. And I think its definition for undecidable languages is approximately actually for unrecognizable languages.

Am I correct?

# Answer
> 7 votes
ChatGPT is not capable of being “right” or “wrong” about anything. It is however capable of producing very plausible sounding nonsense about just any subject. Never trust anything it says.

---
Tags: formal-languages, turing-machines, computability, undecidability, computation-models
---


title: XOR pair frequency queries

text:
# Question
Title: XOR pair frequency queries
We are given an array of length $N$ and $Q$ queries (offline) where each query is a value $K$, for each query we need to count number of pairs in array with XOR $K$.

If $N$ and $Q$ can both be upto $10^5$, is it possible to answer these queries better than traversing entire array for each query?

An analogous version to count pairs with given sum uses FFT to precompute frequency every possible sum, which seems very difficult to do for XOR operation.

We can assume values in array are upto $10^5$ too, but if a solution exists which works for larger numbers too, that's preferable.

# Answer
> 1 votes
*(The following sample code is written in Scala, but is hopefully understandable without Scala knowledge.)*

If I understand Your question correctly You are looking for a faster alternative to the following $\mathcal{O}(n²)$ function:

```
def countXorPairsV1( a: Array[Int], k: Int ): Long =
  var n = 0

  for ai <- a do
    for aj <- a do
      if (ai^aj) == k then n += 1
    end for
  end for

  return n
end countXorPairsV1

```

## Radix Splits

The first optimization that You can do, is to go through the bits of Your integer representation one by one. For each bit index $b$ you recursively split Your array $a$ into two parts:

$$ low\_b(a) = \left\\{\\; x \in a \\; | \\; bit\_b(x) = 0 \\;\right\\} $$ $$ high\_b(a) = \left\\{\\; x \in a \\; | \\; bit\_b(x) = 1 \\;\right\\} $$

This is very reminiscent of the splitting performed by radix sort. Depending on the value of $bit\_b(k)$, You can deduct that only either low-high/high-low or low-low/high-high pairings can xor to $k$. In code it looks like this:

```
def countXorPairsV2( a: Array[Int], k: Int ): Long =

  def count( bit: Int, u: Array[Int], v: Array[Int] ): Long =

    if u.isEmpty || v.isEmpty then return 0
    if bit == 0 then return u.length * v.length.toLong

    def splitFn( x: Int ) = (x & bit) != 0

    val (u_lo,u_hi) = u.partition(splitFn)
    val (v_lo,v_hi) = v.partition(splitFn)

    val nxt = bit >>> 1 // <- next bit to be used

    if (k & bit) == 0
    then return count(nxt,u_lo,v_lo) + count(nxt,u_hi,v_hi)
    else return count(nxt,u_lo,v_hi) + count(nxt,u_hi,v_lo)

  end count

  return count(1<<31,a,a)

end countXorPairsV2

```

Each split requires $O(n)$ operations operations. If the integers in $a$ are uniformly distributed, each split should roughly partition $u$ and $v$ into halves. That results in the recursion:

$$T\_{V2}\[n\] = n + 2 \cdot T\_{V2}\left\[\frac{n}{2}\right\]$$

Which results in $\mathcal{O}(n\log{n})$ operations. But we can go even faster...

## Binary Search

If we take some time to sort $a$ beforehand, we can perform splits in $\mathcal{O}(log(n))$ time using binary search:

```
def countXorPairsV3( a: Array[Int] ): Int => Long =

  val lookup = a.sorted(Integer.compareUnsigned)

  def count( k: Int ): Long =

    def recursion( bit: Int, l0: Int, l2: Int, r0: Int, r2: Int ): Long =

      if l0 >= l2 || r0 >= r2 then return 0
      if bit == 0 then return (l2-l0) * (r2-r0).toLong

      @tailrec def binarySearch( from: Int, until: Int ): Int =
        if from >= until then return from

        val mid = from+until >>> 1

        if (lookup(mid) & bit) == 0
        then return binarySearch(mid+1, until)
        else return binarySearch(from, mid)
      end binarySearch

      val l1 = binarySearch(l0,l2)
      val r1 = binarySearch(r0,r2)
      val nxt = bit >>> 1

      if (k & bit) == 0
      then return recursion(nxt, l0,l1, r0,r1) + recursion(nxt, l1,l2, r1,r2)
      else return recursion(nxt, l0,l1, r1,r2) + recursion(nxt, l1,l2, r0,r1)

    end recursion

    return recursion(1<<31, 0,a.length, 0,a.length)

  end count

  return count

end countXorPairsV3

```

This should result in $\mathcal{O}(n)$ operations per query derived from the recursion:

$$ T\_{V3}\[n\] = \log(n) + 2 \cdot T\_{V3}\left\[\frac{n}{2}\right\] $$

## Further Optimization Potential

There is a lot more optimization potential, but I feel like I'v already gone beyond the scope of a simple answer. So I will only hint at what's possible:

* If $a$ contains duplicates, You can group them together.
* You can probably modify the binary search to perform a multi-bit split, in order to make sure that $u$ and $v$ are roughly split in half every time.
* You can use a tree data structure to be able to split in $\mathcal{O}(1)$ operations.
* ...

## An Interesting Observation

I have not checked let alone proved this, but I have the hypothesis that, as long $a$ a contains *unique* uniformly distributed values, there should be $\mathcal{O}(n)$ pairs that $\operatorname{xor}$ to $k$.

# Answer
> 0 votes
A simple method: Calculate the array B = A xor k. Sort arrays A and B and count the common entries. Time is O(n log n) with n array elements.

This works because (x xor y) = k iff x = (y xor k). So it wouldn’t help for “find all pairs with a product equal to k”.

# Answer
> 0 votes
With your small numbers, you just create an array that counts how often each number turns up, say f\[i\] = number of array elements equal to I. Then for query K, you add up f\[i\] * f\[i xor k\] for all i. So if all values are less than M = 2^n, then you need max(M, N) steps to fill the array f, and Q * M steps for all queries, independent of N.

If N is small compared to M, you create a linked list of indices I with f\[i\] ≠ 0, then the queries take Q * N’ where N’ is the number of different values in the array A. You’d do actually do this if there are much fewer than M different values, even if N is large.

Since the naive method takes Q * N^2 steps, you’d use that if this is not much larger than M.

# Answer
> 0 votes
There is a simple reduction to 3XOR when you have large numbers, so it's unlikely there is an efficient solution (faster than the $O(NQ)$ which can be achieved with a hash table).

In a bit more detail, if the array and the queries are the same, if any of the queries, say $c$, have a non-zero value then you know there's a solution to $a \oplus b = c$ which can then be found in $O(N)$ time.

In fact it even lets one count the number of solutions to 3XOR, so even if the numbers are small and randomized algorithms could find a solution to 3XOR efficiently (because either one exists WHP or there aren't many numbers) you likely can only get approximate answers.

---
Tags: counting, xor, fast-fourier-transform
---


# Question
Title: Why is the Program counter(PC) 12 bits and not 24 bits in IAS computer system?
Why is the Program counter(PC) 12 bits and not 24 bits in IAS computer system? PC is said to have next - instruction pair and an instruction has 12 bit adress and 20 bit opcode, so if it's a pair it should store 24 bits , right ?

# Answer
It should be because the PC needs only to point to the memory address of the next instruction's address field, which has a size of 12 bits. The instruction pair is located in consecutive memory addresses, thus the PC does not need to store a full 24-bit value for the next instruction pair
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: What are the conditions necessary for a programming language to have no undefined behavior?
For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question in the first place is that, awhile ago, someone on the learnprogramming subreddit told me something about the reason C++ in particular having so much undefined behavior is because, for it to *not* have undefined behavior, it would have to use a much more restrictive language model, but they didn't explain what that means exactly. I had also asked on Quora awhile ago about why C++ compilers don't always throw errors when a program contains undefined behavior and at least one answer mentioned something about it being fundamentally *impossible* to always detect undefined behavior at compile time and that this was related to the halting problem being undecidable.

Those two things combined have me wondering about models of computing more generally -- my understanding is that all/most popular programming languages, including C++, are Turing complete, and since I was told the problem of detecting UB in C++ is *fundamental* and related to the halting problem, I thought that perhaps *all* Turing complete programming languages must have undefined behavior and C++ is just worse at hiding it than others. But judging from the answers to my above-linked question, I was mistaken about that.

So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior determined by the language specification? And, on a side note, does the answer have anything to do with the incompleteness theorems? I ask the latter question because the idea of defining a language for which all possible programs have fully defined behavior seems quite similar to the idea of defining an axiom system for which all possible theorems are provable/disprovable.

# Answer
The problem of statically detecting undefined behavior has nothing to do with undefinedness as such. It's just impossible to prove in general that programs in a Turing-complete language will do anything (Rice's theorem). For example, if your `main` function looks like

```
int main() {
    do_something();
    cout << "Done" << endl;
}

```

then for any algorithm attempting to determine whether the program halts, there is some definition of `do_something` that will fool it. For the same reason, for any algorithm attempting to determine whether the program displays `Done`, there is a definition of `do_something` that will fool it. For the same reason, if you add `"42"[42];` at the end, then for any compiler that tries to warn you about undefined behavior, there is a definition of `do_something` that will fool it.

Whether a program displays `Done` is decidable for a Turing-complete language that has no way to display text. Likewise, whether a program has undefined behavior is decidable for a Turing-complete language that completely defines the behavior of every program (as Turing's original computing model did, for instance).

It is possible to detect and warn about undefined behavior in C++ in *many* cases, and popular compilers could do a better job of it than they do.

> someone \[...\] told me \[...\] for \[C++\] to not have undefined behavior it would have to use a much more restrictive language model, but they didn't explain what that meant exactly.

They probably meant that defining the behavior of every program makes optimization more difficult. For example, if the effect of an out-of-bounds array access is defined, then every array access has to be compiled into code that checks whether the index is out of bounds so it can do the mandated thing (unless the compiler can prove that that code is dead, which in many cases is not possible). If the effect is not defined then the compiler can just generate a single memory-access instruction. It may crash the program, or overwrite some other variable causing weird, hard-to-debug behavior down the line, but that's okay, because that can only happen when the index was out of bounds, and the spec says anything goes then.
> 5 votes

# Answer
First off, let's be clear on what "undefined behaviour" is. In just C alone (and this is the understanding inherited by C++), there are two possible meanings, depending on which version of the standard you choose.

The C89 standard, section 3.16, defines:

> **undefined behavior**: Behavior, upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects, for which this International Standard imposes no requirements. Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

The 1999 *C Rationale* explains:

> *Undefined behavior* gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior.

The C99 standard, section 3.4.3, words it slightly differently, turning the second sentence into an explanatory note:

> **undefined behavior** behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements
>
> NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
>
> EXAMPLE An example of undefined behavior is the behavior on integer overflow.

Note that in the second sentence, the word "permissible" was changed to the word "possible".

The way everyone interpreted the C89 standard was that the second sentence was normative: it described the set of permissible behaviours. So "undefined behaviour" is only "undefined" in the sense that the standard does not require which of the permissible behaviours an implementation may do.

But with C99, following ISO rules, moving the second sentence to an explanatory note and changing the word "permissible" to "possible" means that it is *not* normative. These are merely possible behaviours, but because the standard imposes no requirements, *any* behaviour is possible. This is sometimes jokingly known as a nasal demon, because making demons fly out of your nose is a possible behaviour.

This is more than a little controversial, and the reinterpretation has caused customary C programming idioms to become bugs, including one in SPECint, the standard suite of integer benchmarks. Chris Lattner of LLVM put it this way: "huge bodies of C code are land mines just waiting to explode."

But I digress.

C is designed as a systems programming language, and as such, allowing direct manipulation of the underlying platform (e.g. CPU, OS) is a feature. But C is also meant to be portable, which means that differences in the underlying platform manifest as differences in behaviour of the program. And sometimes, this behaviour is a *global* property of the program, not detectable in any specific line of code.

There are essentially only three ways out of this, for any given situation that would otherwise be undefined behaviour.

1. Define the behaviour. For example, you could mandate two's complement arithmetic so that integer overflow has a defined behaviour. In some situations this may require extra code; see point 3. For example, shifting a 64-bit word left by 64 bits might seem to have a reasonable "answer" (i.e. zero), but the shift left instruction on many CPUs doesn't do this, so this would require extra code to detect it.
2. Provide enough *static* guarantees such that UB never occurs. This could be anything from not having language support for the kind of activity that might cause UB (e.g. unsafe references or pointer arithmetic, which many languages simply don't have) to having a strong static type system which the programmer cannot subvert (e.g. to disallow modifying static strings).
3. Generate code to detect the situation at run-time and take action then (e.g. raise an exception, terminate the program, substitute defined behaviour).
> 12 votes

# Answer
The C language may say "if you do X, then whatever the result is, is not a violation of the C Standard". "Whatever the result is" can include the result that you hoped for, some completely different result, your software crashing, or your program doing strange things. An example for this would be to write

```
int a[2]; const int b = 3; a[2] = 5;

```

which is undefined behaviour, and the result might be that now b is 5. But not always. So printing b twice could print 5 and 3. And quite often "whatever the result is" includes "nothing bad happens when the developer runs the software, but as soon as it is delivered to a customer, all hell breaks lose".

How can the language eliminate undefined behaviour? It must define the behaviour of any code that you execute. It may include "your program crashes" as a possible behaviour. For example, Swift does that in many situation. If you access the data in a nil object, the program crashes. It crashes definitely (unlike C where it *may* crash or do nothing or do something worse than crashing).

The compiler must enforce this. So it may add code that checks for unusual situations (situations that would be undefined behaviour in C). Or it may set up things so that a crash happens automatically with checks done for free in the computer's hardware. Or it may prove that an unusual situation cannot happen. As an example, in a loop for (i = 0; i \< limit; ++i) you can prove that the ++i cannot produce an arithmetic overflow if i is not modified elsewhere. So this increment can be executed without checking for an overflow.

Another possibility is to just define the behaviour. For example, shifting a 64 bit integer x to the left by 64 bit positions is undefined behaviour in C. The "natural" hardware instruction that shifts by arbitrary amounts will leave x unchanged on a 64 bit Intel processor, and set it to 0 on an ARM processor. So you could have a language "C for Intel" that has the defined behaviour that x \<\< 64 produces the result x, and another language "C for ARM" that has the defined behaviour that x \<\< 64 produces the result 0. Whether this is useful is another question, because using x \<\< 64 is not portable code.
> 8 votes

# Answer
> So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior determined by the language specification?

1. Enough time and attention to specify all possible behaviors in all corner cases
2. Either no multi-threading at all, or a will to do something similar to Python's GIL (Global Interpreter Lock).

Although one can argue that a good memory model is not "undefined behavior" even if there is no global lock, I think it's still worth mentioning.

E.g. Java/Kotlin/Scala have no undefined behavior in C/C++ sense except for some dark corners of multi-threading that I'm not sure about. Maybe the deprecated `Thread.stop()`.

> And, on a side note, does the answer have anything to do with the incompleteness theorems? I ask the latter question because the idea of defining a language for which all possible programs have fully defined behavior seems quite similar to the idea of defining an axiom system for which all possible theorems are provable/disprovable.

Absolutely not. A program is more similar to "expression" rather than "theorem". You execute program to obtain a result, step-by-step, and everything goes well as long as all steps are precisely defined.

What you will have troubles with is theorems about programs. E.g. "can this integer overflow ever happen". That is impossible to determine in general. So you cannot rely on a "smart compiler" to eliminate undefined behavior, you have to eliminate it in the language's specification and define all possible behavior, no matter how unlikely it seems.
> 4 votes

# Answer
Lets look at a sample program

```
Collatz_thingy(bigint n):
seen = set()
While not n in seen:
   seen.add(n)
   If n odd:
       n = 3n + 1
   Else:
       n = n / 2
N_64 = Cast(n, int64)
result = new char[5]
result[N_64] = ‘x’
Return result `

```

In a language with no undefined behavior, the compiler has to either insert a bounds check in result\[N\_64\] = ‘x’ , prove the collatz conjecture, or refuse to compile unless you provide a proof of the collatz conjecture in a type annotation. The authors of C and C++ are incredibly averse to automatic insertion of bounds checks.
> 3 votes

# Answer
Starting from the C/C++ languages, ruling out all undefined behavior would be very hard. But if you're designing a language from scratch, it's not difficult at all to rule out undefined behavior. Many languages -- including type-safe compiled languages, and typically interpreted/dynamic languages -- have no such thing as undefined behavior\*. There may be cases where they will reject a program as invalid, or cases where they run a program and it crashes (because the semantics of the language call for it to crash.) But there's no need for them to have cases where a program's behavior is not defined by the language.

(\*Many otherwise-safe languages have various features which are clearly documented as being unsafe, and inherently cannot be otherwise by their nature. This includes things like foreign-function interfaces, through which you can call C code, for example. I think it's fair to say a language "does not have undefined behavior" if you can avoid it by avoiding those features. I also don't count compiler bugs, for obvious reasons, even though those can result in a safe language displaying unsafe behavior.)

Incompleteness is most often irrelevant in practice, and I claim it is irrelevant here. One could maybe use it to show that, in a sufficiently powerful language, some hypothetically safe programs cannot be proven safe. But that doesn't actually matter. In practice, it's easy to design a language where the programs we *actually wish to write* can be proven safe. And then we can simply reject all other programs.

In proof theory terms, you should think of every program as (ideally) coming with a proof of safety -- a proof that the program executes correctly and has defined behavior. In C/C++, the type system is supposed to provide that proof, but it's kind of leaky. You can write a program which passes type checking, but does not actually have well-defined behavior.

But in, say, Haskell or OCaml (if you refrain from using deliberately-unsafe features), the proof system is sound -- the type checker only accepts programs which have well-defined behavior. And in something like Python (again, if you refrain from deliberately using unsafe features), the semantics of the language are such that you don't need a type checker to ensure well-defined behavior, because you instead have runtime safety checks on every operation that could fail. This is slower, but much easier to engineer.
> 3 votes

# Answer
I would argue that there is one very specific requirement to defeat undefined behaviour: that the programming language designers control the hardware design.

Undefined behaviour exists notionally to allow variation in compiler implementation, but that is desirable primarily when different compilers target different hardware, each themselves with somewhat different (or even very different) conceptions and architectures.

These different hardware architectures prevent the language having a defined behaviour in certain corners, because what is a reasonable implementation on one architecture may be unacceptably inefficient on another.

So undefined behaviour is the result of disintegrated design.

Many languages like C still date from an era when microprocessor designs were more various for real technical and creative reasons, and high-level languages (as C was then) sought to find the common ground between them.

Nowadays, it's all just legacy, and simpler and more consistent integrated designs are prevented only because of heavy transition costs, and because the total costs of undefined behaviour are mostly sunk (with only a small ongoing cost).
> 1 votes

---
Tags: programming-languages, undecidability, mathematical-foundations, decidability, incompleteness
---


# Question
Title: Does the base component affect Logarithmic and Exponential Runtimes in Time Complexity (Big-Oh) of an algorithm?
Let us look at the following 2 cases:

1. We say a *binary search* implementation in a `sorted array` of size `n` has a time complexity of $O(\log n)$. In detail, $O(\log\_{2} n)$ because binary search halves the input space with each iteration.
2. In a recursive code block as below, We say that the time complexity is $O(3^n)$ as there will be exponential growth of branches in the order of 3 per iteration.

```
    int recursive(int n){
    if (n<=1){
      return 1;
     }
    else{
      return recursive(n-1) + recursive(n-2) + recursive(n-3);
     }
    }

```

Since Time Complexity talks about the behavior/trends of algorithms with respect to input size,

Can we say that the base component in the above cases is not crucial?

*(logarithm's base component is 2 & exponential's base component is 3)*

i.e., Can we just say their Time Complexity as $O(\log\_{k} n)$ and $O(k^n)$ where $k$ is a constant?

# Answer
> 3 votes
The basis of logarithm and the basis of an exponential are very different.

By logarithm basis change formula we have: $$\log\_a n=\frac{\log\_c n}{\log\_c a} \\, $$ where $\log\_c a$ is a constant (independent on $n$). Thus $O(\log\_a n)=O(\log\_c n)$.

For exponentials it is not the case:

$$4^n=(2\cdot 2)^n=2^n \cdot 2^n = (2^n)^2 \ . $$

So, a multiplicative factor at the basis of the exponential becomes a power-factor. If you call $2^n=y$, we have $O(4^n)=O(y^2)$ which is a polynomial in $y$ with a larger degree than $O(2^n)=O(y)$.

In conclusion, you can just omit the basis of the logarithm in big-O notation, but you can't do it with exponentials

# Answer
> 1 votes
The logarithms in different bases are proportional to each other, and in complexity analysis a constant factor is unimportant. Hence

$$O(\log\_a(n))=O\left(\frac{\log(n)}{\log(a)}\right)=O(\log(n)).$$

But such a rule does not hold for exponentials, there is no constant such that

$$a^n=c\\,e^n.$$

---

**Proof:**

Taking the natural logarithm,

$$n\ln(a)=\ln(c)+n$$ makes

$$n=\frac{\ln(c)}{\ln(a)-1},$$ which is absurd.

---

**Numerical insight:**

$$\frac{\log\_2(4)}{\log\_4(4)}=\frac21=2,\\\frac{\log\_2(16)}{\log\_4(16)}=\frac42=2,\\\frac{\log\_2(64)}{\log\_4(64)}=\frac63=2,\\\cdots$$

while

$$\frac{4^1}{2^1}=\frac42=2,\\\frac{4^2}{2^2}=\frac{16}4=4,\\\frac{4^3}{2^3}=\frac{64}8=8,\\\cdots$$

---
Tags: algorithms, time-complexity
---


# Question
Title: A Fast Linear-Arithmetic Solver: How can Gaussian elimination be used to simplify matrix A?
I am working on an LRA Theory solver for SymPy, an open source python library for symbolic computations. You can find my work here. Currently I'm trying to optimize it to run faster.

My implementation is based off of Bruno Dutertre's and Leonardo de Moura's paper "A Fast Linear-Arithmetic Solver for DPLL(T)". My question regards a particular paragraph from the paper about a way to speed things up:

> Since the elementary atoms of Φ′ are known in advance, we can immediately simplify the constraints Ax = 0 by removing any variable xi that does not occur in any elementary atom of Φ′. This is done by Gaussian elimination. In practice, this presimplification can reduce the matrix size significantly.

Φ′ is the second part of the boolean formula above—that is the bottom formula which includes only inequalities. The top formula which is a conjunction of equalities is represented by the matrix A. The matrix for this particular example would look something like this (or at least this is how it's represented in my implementation):

The first row with variables is just to show which column corresponds to which variable. It's not actually part of the matrix.

I'm confused about how to reduce the size of this matrix. In this particular example, it seems like the column with z can be removed while maintaining equisatisfiability. I think you can also get rid of y. However, I can come up with examples where variables can't be removed despite not appearing in Φ′, so you can't simply just always get rid of such variables. Presumably Gaussian elimination has to be involved somehow.

# Answer
The idea here is that if you have a solution for $x$, $s\_1$, and $s\_2$, then from this you can find $y$ and $z$.

The way you can solve this is to solve the linear system:

$$\begin{eqnarray\*} y + 0z & = & s\_1 - x\\ 2y - z & = & s\_2 - x\end{eqnarray\*}$$

Which has the solution:

$$\begin{eqnarray\*} y & = & s\_1 - x \\ z & = & 2s\_1 - s\_2 - x\end{eqnarray\*}$$

What I think the paper is getting at is that you can use Gaussian elimination directly on the tableau that you have constructed. Consider this form of the linear system, with the variables to be eliminated moved to the left:

$$\left\[\begin{matrix}1 & 0 & 1 & -1 & 0 \\ 2 & -1 & 1 & 0 & -1\end{matrix}\right\] \left\[\begin{matrix}y \\ z \\ x \\ s\_1 \\ s\_2\end{matrix}\right\] = \left\[ \begin{matrix}0 \\ 0\end{matrix} \right\] $$

Turn this into an equivalent system where the leftmost 2 by 2 submatrix is the identity:

$$\left\[\begin{matrix}1 & 0 & 1 & -1 & 0 \\ 0 & 1 & 1 & -2 & 1\end{matrix}\right\] \left\[\begin{matrix}y \\ z \\ x \\ s\_1 \\ s\_2\end{matrix}\right\] = \left\[ \begin{matrix}0 \\ 0\end{matrix} \right\] $$

And that gives you equations for $y$ and $z$:

$$\left\[\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}\right\] \left\[\begin{matrix}y \\ z\end{matrix}\right\] = - \left\[\begin{matrix}1 & -1 & 0 \\ 1 & -2 & 1\end{matrix}\right\] \left\[\begin{matrix}x \\ s\_1 \\ s\_2\end{matrix}\right\] $$
> 0 votes

---
Tags: satisfiability, smt-solvers
---


# Question
Title: Solving systems of linear equations over semirings
So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm at a loss of how to find solution spaces to even rings much less semirings. In fact I'm not 100% sure this is decidable. The problem demands that I be able to do this for a wide class of semirings (preferably all) and not just 1 specific kind.

Are systems of linear semiring equations decidable? If so what algorithms are known to compute solutions for them?

# Answer
> 8 votes
I don't think there's any general algorithm that works for arbitrary semirings. The requirement to be a semiring doesn't give us a lot to work with.

However, if you have a *closed* semiring, then there *are* algorithms for solving systems of linear equations over the semiring.

# Closed semirings

A closed semiring is a semiring with a closure operator, denoted $\*$, which satisfies the equation

$$a^\* = 1 + a \times a^\* = 1 + a^\* \times a.$$

A closed semiring is also known as a star semiring.

The intuition is that $a^\*$ is intended to be the sum of the infinite series

$$1 + a + a^2 + a^3 + \dots$$

For instance, the regular languages form a closed semiring under union and concatenation; the $\*$ operator is the Kleene star. The real numbers form a closed semiring under addition and multiplication; the $\*$ operator is $a^\* = 1/(1-a)$.

# Systems of linear equations over a closed semiring

Now, if you have that kind of structure, then there *is* an analog of Gaussian elimination. In particular, if you have a linear system of equations

$$Ax+b = x$$

where $x$ is a vector of variables over the closed semiring, $b$ is a vector of constants, and $A$ is a matrix of constants, then this has the solution

$$x = A^\* b.$$

The closure operator on matrices takes a bit of work to define, but it can be computed efficiently using an analog of Gaussian elimination.

For a careful development of the theory, I recommend the following papers:

Stephen Dolan. Fun with Semirings: A functional pearl on the abuse of linear algebra. International Conference on Functional Programming, ICFP '13.

Daniel J. Lehmann. Algebraic structures for transitive closure. Theoretical Computer Science, vol 4 pp.59--76, 1977.

# Answer
> 1 votes
Even for the canonical example of a semiring, $\mathbb N$, solving linear equations is hard; in a sense, NP-hard.

See 0-1 Knapsack Problem, and Integer Knapsack Problem (Papadimitriou and Steiglitz, page 376).

---
Tags: algorithms, undecidability, linear-algebra, algebra
---


# Question
Title: Language of equal numbers of as, bs, cs in any order not context-sensitive?
In his book "Foundations of Computing", professor Allison shows an example of *"language of equal numbers of as, bs, and cs, but in any order"*, formally: $L = \\{ w \in \\{a,b,c\\}^\*\ |\ |w|\_a=|w|\_b=|w|\_c \\}$, where $|w|\_a$ denotes the number of $a$s in a word $w$. This language is a variant of the language $L\_1 = \\{ a^nb^nc^n |\ n\>0 \\}$ which *is* context-sensitive.

Later, he says that this language is not context-sensitive because *"the working strings grow beyond a constant times the size of the initial input before shrinking down to the final output."*

However, I can think of a Turing machine that first sorts the input (in a linear space n + c, where n is the input size and c is a constant such as 1) and then accepts/rejects in the very same manner as the machine accepting the language $L\_1$. Both subroutines are also linear bounded and thus the machine itself is a linear bounded automaton (LBA). Context-sensitive languages are accepted by LBAs, therefore the language $L$ is context-sensitive.

Where am I mistaken?

# Answer
> 3 votes
It seems the author of the book is a little careless at this point. His definition of context-sensitive is that "the right-hand side of a rule must never be shorter than the left-hand side" together with a specific assumption that enables us to generate the empty string.

He states "The grammars in Examples 9–1 and 9–2 are not context-sensitive. In both cases, the working strings grow beyond a constant times the size of the initial input before shrinking down to the final output."

This is confusing. In his Example 9-1 for equal numbers of $a$, $b$ and $c$'s the only contracting rule is $S\to \lambda$ which can be easily transformed into a grammar where $S$ does not appear to the right of a rule by introducing a new copy of $S$. Then you will have a proper non-contracting grammar for the language you are interested in.

The other Example 9-2 for $\\{ a^{2^n}\mid n\ge 0\\}$ has several rules that are contracting, like $GR\to R$ and $XA\to X$. In this case there seems no fast solution, but with proper care also here one can design a noncontracting grammar for the language.

Then, I quote, "The languages generated by those grammars are not context-sensitive". This is not true as you suspected. Both languages can be recognized by a linear space Turing machine, or generated by noncontracting grammar.

(I prefer noncontracting here, as context-sensitive is usually a more restrictive type of grammar, which nevertheless is equally powerful.)

PS. For the second example several solutions can be found at Context sensitive grammar for $\\{a^{2^n}\mid n\ge 0\\}$.

---
Tags: formal-languages, formal-grammars, context-sensitive, linear-bounded-automata
---


# Question
Title: $ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity
My algorithms and data structures' book states that to create a dynamic array the following procedure is followed:

> Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in it. Each time an insertion operation is done, if there is enough space $(n+1\<d)$, $n $grows by 1; otherwise if $n=d$, we allocate and array $b$ of size $2d$, $d$ is updated to$ 2d$ and all elements are copied to it, then we do $a=b$. Similarly, everey time a deletion operation is performed, $n$ decreases by 1, when $n=d/4$, we allocate and array of size $d/2$, $d$ is updated to $d/2$ and we copy all elements of the array $a$ to the array $b$ an do $a=b$.
>
> The pseudocode of the functions doing the array doubling and halving is shown in the picture

then the following theorem is proved:

> The execution of N insertion or deletion operations in a dynamic array requires a time $O(n)$, beside d=$O(n)$
>
> proof: Let $d$ be the length of an array and n the number of elements stored in it After doubling the array's size there are $m=d+1$ elements in the new array of $ 2d $ positions. We need at least m-1 insertion requests for a new doubling and at least $m/2 $ deletion requests for a halving. Similarly,after a halving, there are$ m=d/4$ elements in the new array of $ d/2 $ elements, for wich at least$ m+1$ insertion requests are needed for a new doubling and at least $m/2 $ deletion requests are needed for a new halving.
>
> In any case, the cost of $ O(m) $time required for the resizing can be virtually distributed among the $ \Omega(m)$ operations that caused it(starting from the last resizing) . Finally, supposing the when the array is created there are $n=1$ and $d=1$, the number of elements of the array is always one fourth of its size, so $d=O(n)$

I am a beginner with this $ \Omega(m)$ and $ O(m)$ , I know the mathematical definitions and I've been reading a lot about it but I am not able to understand it well in context. I know big O should indicate an upper bound on the time complexity of an algorithm and big omega a lower bound.

I don't understand the last paragraph when they use these symbols, Why is the time cost O(m), why are they using $ \Omega(m)$ for the number of operations that caused the resizing (besides specifically what operations are they referring to?) and why do they write $d=O(n)$, what should I understand from it? Any help will be greatly appreciated

Note: I got this from : Strutture di dati e algoritmi, progettazione, analisi e visualizzazione. Crescenzi, Gambosi, Grossi-2nd edition.

# Answer
> 0 votes
The definitions are (as used commonly in Computer Science, all functions positive):

$f(n) = O(g(n))$ if there is $c\_1 \> 0$ such that for some $N\_1$ whenever $n \ge N\_1$ it is $f(n) \le c\_1 g(n)$

$f(n) = \Omega(g(n))$ if there is $c\_2 \> 0$ such that for some $N\_2$ whenever $n \ge N\_2$ it is $f(n) \ge c\_2 g(n)$

$f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

Note that the values of $N\_i$ might be huge, and nothing is said about the values of $c\_i$. This is a rather crude comparisons for very large $n$. Useful because they are (comparatively) easy to get, and we are mostly interested in our algorithm's performance for large inputs (small ones are dispatched with not too much work).

Informally, $f(n) = O(g(n))$ means $g$ is an upper bound to $f$, $f(n) = \Omega(g(n))$ means $g$ is a lower bound, $f(n) = \Theta(g(n))$ that they grow roughly at the same rate. Note that for example $n = O(n^3)$ and $n = \Omega(\ln n)$. The notation *does not* mean $g(n)$ is "best possible" in any sense. Often it is understood from the context that the bounds are tight, but you have to check the context/derivation.

# Answer
> 0 votes
You are facing a special type of analysis, called *amortized*. This is necessary when the running time of an operation can vary widely from one execution to the next, for instance due to periodic reorganization.

The main purpose of the study is to establish an $O(n)$ bound ("at most") for the insertion of $n$ elements (because we are always interested in the worst-case behavior of algorithms). But in this case, $O(k)$ is not required on every $k^{\text{th}}$ insertion, only when the capacity is exceeded, and a doubling performed.

This is why the author observes that it takes $\Omega(n)$ insertions ("at least") before the capactiy is exhausted, so that in the end, the *average* cost of an insertion is $O(1)$.

---

In the usual *algorithm* complexity analysis, usually only $O$ estimates are needed. And conversely, when studying the complexity of a *problem*, $\Omega$ bounds are established, as being impassable barriers. For instance, bubble sort sorts in $O(n^2)$ operations, and it is known that a comparison-based sort takes at least $\Omega(n\log n)$ operations.

# Answer
> 0 votes
O(f(n)) could be a lot smaller than f(n). An extreme one: n = O(n!).

When you divide by some amount and that amount is O(f(n)) then the actual amount could be much less than f(n) which would make the result arbitrarily large. So dividing by some amount, you want a lower bound, not an upper bound.

# Answer
> 0 votes
No one seems to be addressing your actual question, though @vonbrand comes close. Importantly, you need to understand that statements using big-O notation (and the related notations) are not statements about *algorithms* but actually statements about *functions*. In the context of algorithm analysis, we often want to say something about the function $T: \mathbb{N} \to \mathbb{N}$ where $T(n)$ is the maximum number of "elementary operations" performed by an algorithm on any input of "size" $n$ (usually measured in bits). We often shorten our language and say stuff like "this algorithm runs in time $O(f(n))$.

In this particular example, the authors are analyzing a function that, when given $N \in \mathbb{N}$ returns the number of elementary operations performed when $N$ insertion/deletion operations are performed on a dynamic array. The idea of this analysis is that we can consider the total number of operations performed by our algorithm as the sum of the operations performed by the algorithm to make each individual insertion/deletion. Most of these will take a constant number, ie $O(1)$, of operations, but whenever an insertion/deletion causes us to resize the array, it takes more time.

The authors then note that after any resizing of the array (or initializing the array), if the array has $m$ elements, and size $d$, it will be the case that $d \approx 2m$. When the next resizing happens, the number of elementary operations needed will be a function of $d$ but since $d \approx 2m$ we can say it is a function of $m$ as well. This function will be in the class $O(m)$. Now, consider the number of insertions/deletions needed before another resizing occurs, as a function of $m$. This function will be in the class $\Omega(m)$. This means that the number of operations needed to resize the array grows like a constant multiple of the number of insertions/deletions made since the last resizing. So the total number of operations spent resizing the array throughout all of our $N$ insertions/deletions is bounded by a constant multiple of the number of insertions/deletions we performed, that is, by $N$.

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, arrays
---