# Question
Title: Is the halting problem decidable for 3 symbol one dimensional cellular automata?
I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata.

*Definition* Let $f(w,i)$ denote the configuration of the system at time step $i$. More formally $f:A^\*\times \mathbb{N} \to A^\*$, where $A$ is the alphabet.

*Definition.* A cellular automaton has halted in configuration $f(w,i)$, if $\forall k\in \mathbb{N}$ we have that $f(w,i)=f(w,i+k)$.

The halting problem for a given cellular automaton is as follows:

*Input:* a finite word $w$
*Question:* will the automaton halt in some state $s$?

Elementary cellular automata (with 2 symbols) are defined here. I am focused on the same sort of celullar automata, except that I'm interested in the case of CA's with 3 symbols instead of just 2 symbols.

From now on, I will denote my rules in the form of $\***\to\*$, meaning that 3 neighboring symbols produce another one beneath them.

### The halting problem is decidable for elementary, 2-symbol cellular automata

I will use $0$ to denote a white cell and $1$ to denote a black one.

If we have rules $000 \to 1$, $001 \to 1$, $100 \to 1$ we know the automaton won't halt. Because with the first rule, since our grid is infinite, we will always have 3 white cells that will generate a black cell. With the second and 3rd rules the word will be expanding to the sides and the automaton will never halt.

In the rest of the cases we can let it evolve for $2^n$ steps and see if it halts. If it does halt, then ok, it halts, if it doesn't then it is repeating some combinations and is stuck in a loop, so we can also conclude that it won't halt.

### What I have figured out for the 3 symbol case

It is obvious that it won't halt if we have rules $000 \to 1$ or $000 \to 2$. But the side rules of the form $00x \to y$ and $x00 \to y$ are harder to analyze, because what if we have rules $002 \to 1$ and $001 \to 0$?

Here's what I came up with:

let's consider all combinations of such rules:

1. $001 \to 0$ and $002 \to 0$
2. $001 \to 0$ and $002 \to 1$
3. $001 \to 0$ and $002 \to 2$
4. $001 \to 1$ and $002 \to 0$
5. $001 \to 1$ and $002 \to 1$
6. $001 \to 1$ and $002 \to 2$
7. $001 \to 2$ and $002 \to 0$
8. $001 \to 2$ and $002 \to 1$
9. $001 \to 2$ and $002 \to 2$

I didn't write the cases for the rules of the form $x00 \to y$, because those are symmetrical.

So, in the first case it's obvious that the input word won't be expanding to the sides, because those side symbol rules produce zeros.

In cases 5, 6, 8, 9 it's obvious that the automaton will never halt, because the input word will be expanding.

Cases 2,3,4,7 are more interesting. First, let's note, that case 2 is similar to case 7 and case 3 is similar to case 4. So, let's just consider cases 2 and 3 for conciseness.

I'm gonna consider case 3 first, because it's easier.

We have $001 \to 0$ and $002 \to 2$. It is obvious that if the first or last symbol of our input word is $2$, then we can conclude that the automaton won't halt. But if they are '1', then we have to look at more stuff, in particular, let's look at rules that can turn the last or first symbols into $2$, because if we have those, then after they do produce that $2$, we can conclude that the automaton won't halt. (the word will be expanding to the side(s)).

Here are all combinations that we need to consider:

```
010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

```

### An explanation of what happens if we have the first triple from the above table

We have a word $w$, written on the grid. The first and last symbols are $1$. Let's say we have rules $010 \to 0$, $011 \to 0$, $012 \to 0$ (the first triple) from above. Then we know that with each next step our input word will be getting smaller by 2 symbols, because these rules erase the first and last symbols, but if at some point we get a $2$, then the rule $002 \to 2$ will make the word grow to one side or the other (or both) and the automaton will never halt. So, all in all, in this case we can let the automaton do $|w|/2$ steps, and if the word becomes empty, then the automaton halts, if not, then it doesn't.

### Generalized case 3

I generalized it and noticed that we can simply let the automaton do $3^n$ steps and if at any one of those steps we have a $2$ as first or last symbol, then the automaton won't halt. If that doesn't happen and the automaton still didn't halt, then it's repeating some configuration, so it's stuck in a loop and won't halt. If it halts, then it halts.

### Where I get stuck

Now let's consider case 2.

We have rules $001 \to 0$ and $002 \to 1$.

And here is where I got stuck and don't know what to do.

I also wrote out a table of rules that start with $1$. I wrote those out, because they seemed to be the first thing I should analyze, because even if we have the input word with first or last (or both) symbol as $2$, at the next step those $2's$ will turn into a $1$. And we will have to deal with rules of the form $01x \to y$.

Here's the table:

```
010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
 0   1   2
 0   2   0
 0   2   1
 0   2   2
 1   0   0
 1   0   1
 1   0   2
 1   1   0
 1   1   1
 1   1   2
 1   2   0
 1   2   1
 1   2   2
 2   0   0
 2   0   1
 2   0   2
 2   1   0
 2   1   1
 2   1   2
 2   2   0
 2   2   1
 2   2   2

```

It is also obvious, that if among our 27 rules, we have a triple from this table in which no rule derives a $2$, then we have nothing to worry about and can simply let the automaton evolve for $3^n$ steps, because it won't really expand, since the side rules will not produce a $2$.

But looking at the triples that do have a $2$, it's actually very hard to analyze, and whether the word will expand or not also seems to depend on the input word.

Can you guys tell me how to solve this? I can't seem to wrap my head around this.

Or, if this 3 symbol cellular automaton looks like something for which the halting problem has been proven to be undecidable, how can I reduce that something to 3 symbol cellular automata?

# Answer
I have found this article: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf and will show how to prove that the halting problem is undecidable for 15-symbol cellular automata.

Let's look at typical instructions of a Turing machine, we have:

1) $q,x\to p,y,L$

2) $q,x\to p,y,R$

The first one says that if the automaton sees symbol $x$ in state $q$, then we replace $x$ by $y$, switch to state $p$ and move left, the second one says the same thing, but it moves right.

Let's assume that the TM alphabet is $A$, the set of rules is $R$ and the set of states is $Q$. Now, let's create a new alphabet for our cellular automaton, it will be the following: $\Sigma=A\bigcup Q\bigcup \\{q'|\forall q \exists r\in R, r=p,x\to q,y,L\\}$. In other words, in the new alphabet we will include the alphabet of the TM, the state alphabet of the TM and for every state $q$, such that there's a rule $p,x\to q,y,L$ we will include $q'$.

The automaton will model the TM, in the following way: at each step of CA's operation we will have one symbol from the TM's state alphabet on CA's tape, and that symbol will point to the symbol that TM's head would be pointing to, in the following way: a symbol that is to the right of the state symbol is the symbol that the TM's head points to. As an example consider the string $s=...xabqzyk...$, let's say, that $q\in Q$, then the TM is in state $q$, and the head points at symbol $z$.

Let's see how we can simulate the operations of the TM. Let's consider the second one first:

2) $q,z\to p,y,R$

So, basically, if we have a string $s=...xabqzyk...$, it should be converted into $...xabypyk...$. Which can be very easily achieved by adding the following rules to the automaton:

$qz\alpha\to p, \forall \alpha \in \Sigma$

$\alpha qz\to y, \forall \alpha \in \Sigma$

The first case is a little more complicated, we have:

1) $q,z\to p,y,L$

So the string $s=...xabqzyk...$ should be converted into $...xapbyyk...$, but there's not a way to do $abq\to p$ because we perform a TM operation by looking at state and symbol, but $abq$ doesn't tell us about the symbol, only state, so we will perform this left move in 2 steps:

first step:

$qz\alpha\to y, \forall \alpha \in \Sigma$

$\alpha qz\to p', \forall \alpha \in \Sigma$

second step:

$\alpha \beta p'\to p, \forall \alpha, \beta \in \Sigma$

$\alpha p' \beta\to \beta, \forall \alpha, \beta \in \Sigma$

As for all the other CA rules, for which there's isn't a rule in TM, we will write the following:

$\alpha \beta \gamma \to \beta, \forall \alpha,\beta,\gamma \in \Sigma$

Now that I explained the way to model the work of TM on a CA, let's see why we need 15 symbols. In the paper, the link to which I gave above we have a universal TM $U\_{6,4}$ with 6 states and 4 symbols:

So, we need all the alphabet symbols, which is 4, plus all the state symbols which is 6 and all the state symbols $q'$ such that there's a rule $p,x\to q,y,L$, which are $u\_1, u\_3, u\_4, u\_5, u\_6$, so, we need 15 symbols in total.

So, now there's a gap between 2 and 15 symbols (exclusive), that we don't know about.
> 1 votes

---
Tags: computability, decision-problem, halting-problem, cellular-automata
---


# Question
Title: NFA to accept strings where the third AND the third-last element are b
Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I don't know where to start. Help please.

# Answer
**Hint**. If $A$ is the alphabet, a regular expression for your language is $AAbA^\*bAA \cup AAbAA \cup AbbA \cup bAb$.
> 2 votes

---
Tags: automata, finite-automata
---


# Question
Title: What is the difference between finite automata and Büchi automata?
as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented.

From an assignment I'm working on, this automaton can be depicted as both infinite automaton and Büchi automaton.

Can you give me an example for each of those automatons to understand the differences?

# Answer
The automaton models themselves, that is the syntax, are indeed identical: both have a finite set of states, a transition relation, and initial and final state(s).

The difference lies in the *acceptance* criteria, that is the *semantics*.

A finite automaton $A$ accepts a word $w$ if and only if there is a computation¹ for $w$ in $A$ that ends in a final state.

A Büchi automaton $B$ accepts a word $w$ if and only if there is a computation¹ for $w$ in $B$ that visits final states infinitely often².

The differences follow from this.

---

1. For which there is a formal definition!
2. Other acceptance criteria have been proposed, e.g. visit *one* final state infinitely often.
> 5 votes

# Answer
There is no difference in the specification (syntax). The only difference is in the interpretation (semantics). The language accepted by a DFA consists of finite strings defined in a certain way given the DFA, and the language accepted by the corresponding Büchi automaton consists of infinite strings defined in a certain way.

Indeed, you can leverage this connection to prove results such as:

> An $\omega$-language is recognizable by a deterministic Büchi automaton iff it is the limit language of some regular language.

For a proof, see Wikipedia.
> 5 votes

# Answer
There are two main differences. First, finite automata are used to recognize sets of *finite* words and Büchi automata are designed to recognize sets of *infinite* words. The second main difference is that finite deterministic and finite nondeterministic automata have the same expressive power: both accept the regular languages, but the situation is different for Büchi automata: as Yuval Filmus pointed out, deterministic Büchi automaton accept the limit of regular languages, but nondeterministic automata accept the whole class of $\omega$-regular languages and these two classes are distinct. However, there do exist classes of deterministic $\omega$-automata that recognize exactly the class of $\omega$-regular languages, for instance Muller automata, parity, Rabin, or Streett automata.
> 3 votes

---
Tags: automata, finite-automata, buchi-automata
---


# Question
Title: Time complexity for Breadth-First search
I would like to know why the average number of nodes at level *d* in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here *b* is the branching factor of the tree and *d* is the depth of the tree)

I think that as average tells us to take the sum of the numbers and divide by how many numbers are present here we should consider the sum of nodes at level *d*(considering the deepest level in search tree) and the number of nodes at level *d*.

**Sum** of nodes at level *d* : $b+\dots+b$(`d+1` times since we consider the initial depth as zero)=$b(d+1)$

**Number** of nodes at level *d* : $b^d$

So the average number of nodes at level *d* would be $\frac{b(d+1)}{b^d}$

# Answer
I think "average" in this context means how many nodes would the search algorithm examine on average before the element you are looking for is found. Best case scenario, you would find it immidiately at depth $d$ hence you would examine 1 node. Worst case scenario, the element is the last you examine on that level or not there at all, hence you would examine all nodes at level $d$, so you would examine $b^d$ nodes. Thus, on average you would need to examine $\frac{b^d+1}{2}$ nodes on that level.
> 3 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, graph-traversal
---


# Question
Title: Are all functions with constant space complexity in $REG$?
The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?

# Answer
A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation graph as one big finite automaton.
> 5 votes

---
Tags: complexity-theory, computability, regular-languages, primitive-recursion
---


title: Shortest distance from a set of points

text:
# Question
Title: Shortest distance from a set of points
Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$.

To be clear, each $v\in V$ has a distance $d\_1, d\_2,\dots , d\_{|S|}$ to each $s\in S$, and we want to find the smallest value of all $d\_1, d\_2,\dots , d\_{|S|}$, and do this for every $v\in V$. So every $s\in S$, for example, would have a distance of $0$.

The algorithm should run in $O(|V|+|E|)$ time. Note that this is independent of $|S|$. I was thinking of running simultaneous BFS's on each $s\in S$ and only assign a vertex a distance if it doesnt already have a distance estimate (i.e. no other node in $s$ reached to $v$ earlier). I'm not really sure how to make the runtime work out though, since we would have to cut off the BFS at some point to prevent a factor of $|S|$ in the runtime.

Also, this is not a homework problem, it's a question from a midterm from a class a few years ago that I am using to study for my final coming up, and the solutions are not available. Thanks for the help!

# Answer
Introduce a new node $s\_0$ with edges to all $s \in S$ (but no others). Run BFS starting in $s\_0$; the quantity you are looking for is

$\qquad\displaystyle \min\_{s \in S} d(s, v) = d(s\_0,v) - 1$

for every $v \in V$.

*Nota bene:* The idea extends to weighted graphs; you have to a) give the new edges weight $1$ and b) use an SSSPP algorithm, of course.
> 1 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: What is the point of the "respect" requirement in cut property of minimum spanning tree?
The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows.

> ***Theorem 23.1*** Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V-S)$ be any cut of $G$ that ***respect $A$*** *(emphasis added)*, and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then, edge $(u,v)$ is safe for $A$.

Why does this theorem require that the cut $(S,V-S)$ respect $A$? How is this requirement used in the correctness proof? I do not see what would fail if the requirement was removed.

---

***Some Definitions:***

* Cut: A cut $(S, V-S)$ of an undirected graph $G=(V,E)$ is a partition of $V$.
* Cross: An edge $(u,v) \in E$ crosses the cut $(S,V-S)$ if one of its endpoints is in $S$ and the other is in $V-S$.
* Respect: A cut respects a set $A$ of edges if no edge in $A$ crosses the cut.
* Light edge: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

# Answer
I don't have the book handy. I assume that

1. "safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
2. the goal is a correctness proof of Prim's algorithm¹.

Now, say the cut did not "respect" $A$. That means that there already is an edge in $A$ that crosses it. By choosing a *second* edge from that cut -- which may happen even with pairwise distinct weights! -- we may introduce a cycle and lose the tree property.

By requiring that the cut "respects" $A$ we know that $A \subseteq S$ and we can not introduce a cycle².

The assumptions of this theorem may be stronger than strictly necessary -- as long as we do not create a cycle, we do not per se need to care about other edges in the cut -- but we can build an algorithm around them, so the theorem is a convenient way to ensure its correctness.

---

1. Note how the theorem directly implies that fact since Prim's algorithm maintains such a cut and chooses light edges from it to grow the tree.
2. In the algorithm, we'll always have $A=S$.
> 1 votes

# Answer
Besides the effect of "avoiding cycles" pointed out by @Raphael, the "respect" requirement in the cut property guarantees that $A \cup \\{ (u,v) \\}$ is included in the minimum spanning tree $T' = T - \\{ (x,y) \\} \cup \\{ (u,v) \\}$ constructed in the correctness proof.

Since $A \subseteq T$, to ensure that $A \cup \\{ (u,v) \\} \subseteq T' = T - \\{ (x,y) \\} \cup \\{ (u,v) \\}$, it requires $\\{ (x,y) \\} \notin A$; see the figure above (Fig 23.3 in CLRS).

$(x,y) \notin A$ holds because $(x,y)$ is chosen as the edge that is on the unique path from $u$ to $v$ in $T$ and crosses the cut $(S, V-S)$ and that $A$ respects the cut $(S,V-S)$.
> 0 votes

---
Tags: algorithms, graphs, correctness-proof, minimum-spanning-tree
---


title: Why is the set of perfect squares in P?

text:
# Question
Title: Why is the set of perfect squares in P?
I am reading an article by Cook \[1\]. In it he writes:

> The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots.

I can see how to use Newton's method to decide whether a natural number is a perfect square or not, but it seems tricky to analyse.

Is there an easier way to see that the set of perfect squares is in P?

---

1. S. Cook, *The P versus NP problem*, Online

# Answer
> 13 votes
A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. If so, terminate. Otherwise, if $m∗m\>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become the same and the midpoint squared is not equal to $n$, then $n$ is not a perfect square. This terminates in $\log n$ steps, which is polynomial in the bit size of $n$, i.e., the length of the input. Each iteration runs in polynomial time as well, so the overall algorithm runs in polytime.

---
Tags: complexity-theory, time-complexity, polynomial-time, number-theory
---


# Question
Title: Proving correctness of an exponentiation routine
I have the following exponentiation routine, which takes $O(\log n)$ steps

```
function power(a:real, n:positive integer)
begin
  x:=1;
  i:=n;
  while i > 0 do
  begin
    if(i % 2 == 1) then   //i odd
      x:=x*a
    i:=floor(i/2)
    if(i > 0) then
      a:=a*a
  end;
  power:=x
end

```

**I'm trying to prove that it always gives $a^n$**. I think it might be provable via induction on $n$. in the examples i went through i found that it always ends with $i=1$ before the final division down to $0$.

# Answer
A standard approach to proving correctness of a program involving a loop is to use a loop invariant. Loop invariant $P(j)$ is a statement indexed by the iteration number $j$ (or a parameter related to the iteration number) that asserts a certain mathematical relationship between some variables appearing in your code. Proving $P(j)$ is true for all $j$ is typically done by induction. You show that $P(0)$ is true, i.e., the loop invariant is true prior to the beginning of the loop. You show that $P(i)$ is true implies $P(i+1)$ is true. Then you can conclude that the statement $P(n)$ (or $P(n+1)$) must be true, which asserts the relationship between the variables of interest that is directly relevant to the correctness of the algorithm. Note that if $j$ is some parameter related to the iteration number (e.g., $j$ could be $n$ minus the iteration number), the starting point and the direction of the induction might be different. Finding the right loop invariant is usually the hardest part.

Let's find a loop invariant for your code. Note that you overwrite the variable $a$ inside the loop. This means that I cannot use $a$ in the loop invariant to refer to the original input, but I'd like to. Therefore I introduce a new letter $\alpha$ to refer to the value of $a$ that is passed to the function, i.e., the first input. The rest of the variables are exactly as in your code. Our loop invariant $P(i)$ will be indexed by the variable $i$, which is related to the iteration number, but starts with $n$ and decreases to $0$ similar to what I wrote about above. Define the following loop invariant: $$P(i) \text{ is true if and only if } x\*a^i == \alpha^n$$ Clearly, at the beginning you have $x=1$, $a=\alpha$, and $i = n$, so $P(n)$ is true. I leave proving the inductive step to you (note you will be proving $P(n)$ is true implies $P(\lfloor n/2 \rfloor)$ is true, so this induction skips over lots of values, but it's okay - why?). When the algorithm terminates you have $P(0)$, which asserts $x\*a^0 = \alpha^n$, i.e., $x = \alpha^n$, which is what you needed to prove.
> 3 votes

---
Tags: correctness-proof, loops, software-verification
---


# Question
Title: Does the Halting Problem prove that true Artificial Intelligence is impossible?
The Halting Problem demonstrates that there are things that a machine can never be programmed to do.

Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and reason like humans - is not possible?

# Answer
If we cannot determine from program description whether it halts we also cannot write algorithm to do so (otherwise we could have determined it from description).
The ability to think and reason like humans is not connected to the halting problem, and the separate problem here is that we do not fully know how people think, so we cannot copy this idea, we are prone to emotions and logic just fails. If you want to create "true Artificial Intelligence" you would have to unlock any restrictions, constraints, let it evolve and think differently otherwise your AI is at the best case clone of you and it will not be self-concious or thinking just ultra advanced processing unit.

If tou like to think about the true AI - human limits are not applicable because if we proved something cannot be done - it is not doable under any circumstances, but if we do not know how to do something (yet) - there is no constraint neither for human nor for the true AI.
> 2 votes

---
Tags: artificial-intelligence, halting-problem
---


# Question
Title: Should names of built-in funtions be part of BNF grammar?
We're creating our own programming language for a subject. And we're confused whether to add the names of the functions we want to have in our language (like our own version of print) in the BNF grammar.

Reserved words should be recognized by the lexer, right? How about function names?

# Answer
> 5 votes
If your language has a small set of functions and there is no mechanism for adding other ones, then you could include the function names as keywords. But that's not a very likely scenario, unless your "language" is just a desk calculator (and even then, these days many calculators allow you to define functions).

So in general, it's not going to be feasible to include all the function names in the lexer, and unless function names are somehow lexically distinguished from other identifiers, all the lexer can do is report that it has found an identifier.

Assuming the grammar is unambiguous, a common idiom is to use a unit rule in the BNF in order to encapsulate whatever needs to be done to turn an identifier into a function reference (and similarly for identifiers representing other kinds of things) \[Note 1\]\[Note 2\]:

```
function_name: IDENTIFIER
type_name:     IDENTIFIER
...

term:          function_name '(' optional_expresion_list ')'

```

But that won't work if certain expressions in the language would be ambiguous without knowing whether an identifier in the expression names a function or some other kind of thing. That's not very common for function names, but C and derived languages famously feature an analogous ambiguity with type names in C.

It's not totally unknown, though. For example, in `awk`, string concatenation is expressed with simple operand juxtaposition, so that

```
first "-" second

```

is the concatenation of two variables and a string containing a dash. The result is that

```
first (second)

```

is ambiguous: if `first` names a function, it could only be a function call; otherwise, it could only be string concatenation. If the language insists of declaration before use (`awk` doesn't), it would be possible to disambiguate by distinguishing according to the type of `first`.

The implementation involves sharing a symbol table between the parser and the scanner. The scanner looks each identifier up in the symbol table, and returns a token based on the broad type (or "kind") of symbol. If the scanner does not find the symbol, it will return a token of type `UNDEFINED_SYMBOL` or some such, which will be required (or at least allowed) in grammar rules where a new symbol is defined.

This technique is commonly called "semantic feedback". Much care must be taken to ensure that the symbol table seen by the lexer while it is examining a token corresponds to the actual semantic state at the moment in which the parser is examining the token. Since lexers typically consume tokens in advance of the parse (or at least one token), this guarantee is not as easy as it might look at first glance.

Semantic feedback is often discouraged, both because of this fragility and because it contaminates the lexer with data which should be private to the parser. But sometimes it is the simplest solution.

As it happens, `awk` does not use this approach, in part because it does not require functions to be declared prior to use. Instead, it has a whitespace-aware lexical rule: a parenthesis which immediately follows an identifier without intervening whitespace is used in a function call expression; if there is intervening whitespace, the parenthesis must be a grouping parenthesis and the expression is treated as a concatenation. This rule is the source of occasional confusion about apparently mysterious errors (see below).

That rule could be expressed in two ways (at least):

* The lexer could return a `FUNCTION_NAME` token when it sees that the character immediately following an identifier is a `(`. In that case, the grammar might include

```
term: FUNCTION_NAME '(' optional_parameter_list ')'
    | '(' expression ')'

```
* The lexer could distinguish between two kinds of open parenthesis: a parenthesis which immediately follows an identifier, and all the other ones. So then the grammar might include:

```
term: function_name OPEN_APPLY optional_parameter_list ')'
    | '(' expression ')'

```

(A third possibility exists, in which the function name and the following parenthesis are recognized as a single token, leading to the rather odd-looking grammar rule `FUNCTION_NAME optional_parameter_list ')'`. Some real-world implementations actually use this for efficiency, but it's confusing for the reader.)

### Editorial comment (i.e. my opinion)

On the whole, you should attempt to avoid playing tricks in your lexer. Ambiguities like the ones mentioned above should be treated as flaws in the language design rather than challenges to be overcome by clever hacks in the parser, particularly if you are designing a language. History demonstrates that ambiguities like the above not only complicate parsers, but also confuse people using the language in question.

A casual search for "most vexing parse" will show the extent of confusion created by an ambiguity in the C++ language. And the use of juxtaposition for concatenation in `awk` creates so many confusing parse errors that the Gnu awk manual has a chapter about how to write concatenation, citing the alleged explanation for the syntax given by one of the `awk` authors: "It seemed like a good idea at the time."

### Notes

1. In this post, I use `yacc` syntax for the BNF, with the convention that terminals (tokens) are represented either by `UPPER_CASE` or by quoted characters, and non-terminals are spelled in `lower_case`.
2. While some languages might be content to not allow higher-order types, almost all languages -- even C -- allow the target of a function application expression to be a computed value. So if you find yourself writing the above rule, you might want to think about its implications for the semantics of your language.

# Answer
> 0 votes
Let me give an illiterate answer. They should not. Not at parser level, and not at scanner level, for sure. Scanner should generate `identifier` token. Since there is no functional difference between built-in and user-defined functions at parser level, you should not differentiate them. It is at semantic, compiler level that you make the difference by precluding the re-definitions. The difference is irrelevant at AST level. You parse only once, I suppose and re-evaluate the parsed AST later, when dependencies changes.

Despite I expose my opinion here, I wonder how easily you ascribe questions to the opinion-based class. This question is certainly answerable. You can easily collect all pros and cons. Every language designer needs the answer in practice. These answers must be a part of every parser book.

---
Tags: programming-languages, language-design
---


# Question
Title: Priority Queue using an AVL tree, run time question
This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input integer of VALUE and i'm required to insert it into an AVL tree. So i created an AVL tree, where each node contains a key that equals the original value of the node plus the global variable. (key = Value + Glob) I input n number of objects into the AVL tree (I assume each one has a unique key)

The question is: I want to increase GLOB by a certain amount, and therefor increase the KEY of each node by that amount. Will this happen in a run time of O(1) or O(n) since i need to "update" all of the nodes, even though they simply contain pointers to GLOB?

# Answer
Assuming that the $GLOB$ variable is consistent under any operations, the update time is $O(1)$, where the variable is changed and all inserts are made without adding it to the key value. Search is done by subtracting the $GLOB$ variable from the input, so there is no need to update every key. If the real key value is needed the addition actually occurs returning the sum $Value + GLOB$ instead if reading just the inserted key.
> 0 votes

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


title: Taking intersection in large search

text:
# Question
Title: Taking intersection in large search
As I understand, you can build the the word -\> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once

```
сomputer -> About 2.14 bln results
science -> About 1.93 bln results

```

---

```
computer science -> About 377 mln results
"computer science" -> About 147 mln results
science computer -> About 0.97 bln results
"science computer" -> About 452k results

```

So, you have got 2 billion pages immediately. To find out the pages which contain both words, you seem to need to make an intersection. How do they make it immediately? I do not believe that they try all 10^18 matches

```
for p in pages(word1):
 for q in pages(word2):
  if p == q yield p

```

# Answer
If you're asking how Google actually works, you'd have to ask Google.

If you're asking how a search engine could plausibly achieve this functionality in a reasonable amount of time (say, within 1 second), here are several strategies, any one of which could work fine:

* **Use a SSD.** Normally, a search index is a map from a search term to a *sorted* list of document IDs (the IDs of the documents that contain that search term). Because these lists are sorted, you can compute the intersection of two lists in time linear in the length of those lists, by using the "merge" algorithm from mergesort. (This is faster than the quadratic algorithm you list.)

As a result, the intersection can be computed in one pass, a streaming fashion. For the parameters you mention, the bottleneck will be the time to read in those sorted lists from disk. If you store them on a SSD, this can be relatively fast. Some modern SSDs can achieve a read bandwidth of perhaps 2500 MB/s. If each document ID is 4 bytes, reading in 4 billion document IDs will take about a half a second. The computation time is negligible in comparison, so the intersection could be computed under a second if indices are stored on a fast SSD.
* **Parallel computation.** If you split the indices across multiple SSDs (say, using RAID or striping), you can increase the read bandwidth. If you use a cluster of machines, each with their own SSD, you can parallelize both data transfer and computation. The intersection task is trivially parallelizable, so you can achieve excellent speeds this way. For instance, if you're using magnetic hard disks with read bandwidth of 200MB/s, striping the indices and computation across 8 machines is enough to finish this task in under a second.
* **Caching.** You only need to do this work once. Once you've computed the size of the intersection once, you can store it in a table and cache it for some time period (a month or more), as it's unlikely to change much in the future, and then once someone else asks the same cache, you can return the number of results instantaneously.
* **Estimation via random sampling.** An even better approach is to avoid computing the entire intersection, but just estimate its size through random sampling. You repeatedly do the following: randomly choose a document that contains `computer`, and check whether it also contains `science`. Each trial (randomly picking a document that contains `computer`) can be done in one operation, by picking a random offset into the sorted list for `computer`, and then it's easy to check whether that document also contains the word `science` (say, by binary search into the sorted list for `science`). Repeat this 1000 times, and you can get a good estimate of the fraction of documents containing `computer` that also contain `science` -- this uses the same principles as political polling, where we survey a random sample of people and then extrapolate to draw inferences about the entire population. Multiply that fraction by the total number of documents containing `computer`, and you've got an estimate of the size of the intersection.

You can apply similar ideas to count the number of documents containing the phrase `"computer science"`.
> 0 votes

---
Tags: search-algorithms, big-data, search
---


# Question
Title: Prove that there is no computable enumeration of all decidable languages
**The question:**

> Let $L\_1,L\_2,...$ be an enumeration of $\mathcal{R}$ and define $A\_i = \\{\langle M\rangle \ | \ L(M) = L\_i\\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \\{\langle M\rangle \ | \ \text{M is a TM that always halts}\\}$. Prove that there exists an $i$ for which $L∩A\_i = ∅$.

**Hint** $\downarrow$

> Hint: Build a TM that returns some (which?) element of $L$ and apply a diagonalization argument.

**My approach**

I thought of the *Hint* but I am not sure that the language I get is decidable and I don't know how to prove that all its "always halting" TMs are not in $L$.

# Answer
> 4 votes
WLOG assume we are talking about languages over a binary alphabet $\\{0,1\\}$. Let $M'$ be an enumerating Turing Machine for $L$, i.e., every element of $L$ is eventually output by $M'$. Let $\langle M\_j \rangle$ denote the $j$th TM output by $M'$. Define $$L\_D = \\{ x \mid M\_x(x) \text{ does not accept} \\},$$ where $x$ is interpreted as a number in base 2. Note that $L\_D$ is decidable: given $x$ you can decide if $x \in L\_D$ by running $M'$ until it outputs $x$th TM $M\_x$ and then running $M\_x$ on $x$ and flipping the output. This is a decider since all TMs output by $M'$ halt on all inputs. Thus $L\_D$ appears in the enumeration of R, say, as $L\_k$ for some $k$.

It is left to show that $L \cap A\_k = \emptyset$. Suppose that there exists a TM $M$ such that $\langle M \rangle \in L \cap A\_k$. Then let $\ell$ be the smallest number such that $\langle M \rangle$ is output as the $\ell$th element by the enumerator $M'$, i.e. $M = M\_\ell$. Therefore, we have $\ell \in L(M) \iff \ell \in L(M\_\ell) \iff \ell \notin L\_D \iff \ell \notin L\_k \iff \ell \notin L(M)$, which is a contradition.

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


title: exercise on Huffman encode

text:
# Question
Title: exercise on Huffman encode
I have these 4 symbols with their probabilities:

```
 x   P(x)
 --------
 1   0.3
 2   0.3
 3   0.2
 4   0.2

```

I built the Huffman tree in this way:

and I obtainded:

```
 x   P(x)   C(x)
 ----------------
 1   0.3     0
 2   0.3     10
 3   0.2     110
 4   0.2     111

```

it's correct? Because according to the solution the results should be:

```
 x   P(x)   C(x)
 ----------------
 1   0.3     00
 2   0.3     01
 3   0.2     10
 4   0.2     11

```

Why? Yet I followed the steps shown here.

# Answer
A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of $2.1$, which is greater than using a code of fixed length $2$, so it can't be correct.

If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 and 4 you get one supernode of priority 0.4. Now your queue would have three elements of priorities $0.3, 0.3,$ and $0.4$. Thus, you would next merge elements corresponding to priorities $0.3$ and $0.3$ (the algorithm works by merging two nodes with lowest priorities), which happen to be nodes 1 and 2.
> 2 votes

---
Tags: huffman-coding
---


# Question
Title: Complexity and number of bits of square root number
Let an integer `a`, and `b` is the number of bits `a`.

1) If I have a number `s = sqrt(a)`, the number of bits `s` will be up to `b/2`?

Considering the code:

```
while (i <= sqrt(a)) {
    if (a % i == 0) return i;
    i++;
}

```

2) The complexity is $O(\sqrt{a})$. But in terms of bits? $O(2^{b/2})$?

# Answer
When you are measuring bits, the complexity is of the form $O(log(b))$ since the number of bits increases at a log rate.

Intuitively, think of the number 10 and 1000. 10 = 1010 and 1000 = 1111101000. The number increases 100-fold but the number of bits only increases a little over two fold. Your hypothesis: $O(2^{b/2})$ is an overestimate.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, numerical-algorithms
---


# Question
Title: How can time complexities be elements of others?
I have a problem that I solved, but I'm unsure if my answers are correct or not. I've never seen the implementation of time complexities as elements of others.

```
f(n) element of O(log(n))
g(n) element of theta(n)

```

Prove if the below are true are false, provide a counter example if it's false.

```
1) g(n) element of omega(f(n))
2) f(n)g(n) element of O(nlog(n))
3) f(n)g(n) element of theta(nlog(n))

```

Below are my attempts, which was just because I thought it was the logical solution. Any ideas on how I can go about solving these types of questions?

1) False, g(n) has a tight bound at (n). If it had a lower bound of f(n), then g(n) should allow log(n), but that's too high of a complexity.

2) True

3) False, f(n) having an upper bound of log(n) implies it could be even faster. Setting a tight bound contradicts that wherein it cant go faster.

# Answer
Actually the 1) is true: omega means "at least", and $O$ means "at most". You now that $g(n)$ is in $n$, which is at least $\log(n)$.

2) is indeed true

For 3) you don't have enough information: it is only true if $f$ is in $\theta(log (n))$ which you don't know, so 3) could be true or false. You can give a counter example where it is false: $f(n)=\log(\log (n)))$ and $g(n)=n$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Prove the halting problem is undecidable using Rice's theorem
Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed:

* We want to reduce Rice's Theorem (decide if a language has the nontrivial property P) to the Halting Problem
* We want to say "if the Halting Problem can be solved, then we can decide if a language as nontrivial property P"

Here's how I thought the proof might go:

* Suppose we have a machine H that solves the halting problem. We want to use this machine to decide if a language has property P.
* We construct a machine that uses H to decide a language has property P.

Example: Take P to be "language contains the string 1".

We want to use H to decide if the language of a TM M contains the string 1, i.e that the TM halts and accepts when given input 1.

Now, if M halts on 1, that doesn't mean it accepts 1, so we don't know if L(M) contains 1. On the other hand if M does not halt on 1, that certainly means that L(M) does not contain 1.

And that's where I'm stuck. Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

# Answer
> 2 votes
Actually Rice theorem is a generalisation of the Halting problem, so if you can assume Rice theorem you have the Halting problem as a direct consequence: Halting is a property of the function computed by the TM, and it is therefore undecidable by Rice theorem. your proof scheme tries to do the opposite: prove Rice theorem from the undecidability Halting problem, which is a more difficult (but not too much, see for instance here).

# Answer
> 2 votes
Your question contains a few hints at misunderstandings of the fundamentals that would take several pages to address. So let's focus on your final question:

> Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?

No. Rice's theorem can only be used to show undecidability of *index sets* and the (usual) Halting problem can not be expressed as such. For details, see here and here.

---
Tags: computability, proof-techniques, undecidability
---


title: All output functions of a truth table

text:
# Question
Title: All output functions of a truth table
> http://www.cim.mcgill.ca/~langer/273/3-notes.pdf

I can name one more: XNOR. But besides these, what other output functions are there?

# Answer
> 2 votes
Suppose you try to come up with a new output function, which you call $A\otimes B$, with new, custom behaviour. You will have to come up with four values: $0\otimes 0, 0 \otimes 1, 1 \otimes 0, 1 \otimes 1$. One arbitrary example is: $0\otimes 0 = 0, 0 \otimes 1 = 1, 1 \otimes 0 = 0, 1 \otimes 1 = 0$. Any sequence of zeroes and ones will do (this is the answer to your question). So you can write a string of four zeroes or ones, and that will represent your function. For example, my function is represented with $0100$. How many such strings are there? Well, try enumerating them: $0000,0001,0010,0011,\ldots$ Hence the remark that there are $2^{4}=16$ possible functions.

Not all of these functions are equally useful. The example I gave is equivalent to $A\otimes B = \neg A \wedge B$. In fact, every (binary) output function can be written as a combination of the three functions $\neg, \wedge, \vee$, i.e. NOT, OR and AND.

Consider functions that use three arguments, $A,B,C$. The truth table of such a function has $8$ entries, so there are a total of $2^{8}=256$ functions on three variables. Can you find a formula for the number of functions on $n$ variables? The example functions in your excerpt are all examples of *commutative* functions, which are functions $\circ$ where $A\circ B = B \circ A$ for every value of $A$ and $B$. Can you think of a noncommutative function?

---
Tags: propositional-logic
---


title: Number of winning combination in Nim

text:
# Question
Title: Number of winning combination in Nim
I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like \[1, 2, 4, 3, 490\], \[100, 100, 100, 100, 100\], \[100, 200, 100, 100\], \[0, 200, 200, 50, 50\] and so on. So basically there are `stones^piles` combinations possible. Among these, some will yield `Xor > 0` and considered as winning possible.

My question is - how many winning initial positions are possible for given `stones` and `piles`? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?

This is not a homework or programming contest problem.

# Answer
I assume there are `k` piles and each pile can have stones in the range `[0,n]`. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of `n` be `b`. We take a 2-D array called `dp` of size $kx2^b$, where `dp[i][j]` denotes number of ways of assigning no. of stones to first $i$ piles such that xor of no. of stones in these first $i$ piles is $j$. It is easy to see that no. of losing positions is `dp[k][0]`. Now what's left is to come up with the recurrence relation ( I leave the base cases for you to come up with ).

```
           // take care of the base case
           for i in range 1 to k:
               for j in range 0 to 2^b:
                   dp[i][j] = 0
                   for m in range 0 to 2^b:
                       // first i piles have nim-sum j
                       // ... if first i-1 piles have nim-sum m in the last
                       // ... pile we keep (m xor j) stones
                       dp[i][j] = dp[i][j] + dp[i-1][m]

```

**EDIT**
If $k$ piles in total have $n$ stones , you can again solve it by dynamic programming , but this time keeping a 3-D `dp` array of size $k$x$2^b$x$n$, where `dp[x][y][z]` means number of arrangements of first `x` piles having in total `z` stones and the nim-sum being `y`. Although I point it out that this method would be feasible only for small values of $k$ and $n$ ( in the order of few hundreds ). Following is a pseudo code ( again take care of base cases, if you have problem with them you could comment )

```
            // take care of base cases
            // our answer would be ( no. of losing ) positions = dp[k][0][n]

            for i in range 1 to k:
                for j in range 0 to 2^b:
                   for l in range 0 to n:
                      dp[i][j][l] = 0
                      for m in range 0 to l:
                            dp[i][j][l] = dp[i][j][l] + dp[i-1][m^j][l-m]

```

Clearly the above method works for small $k$ and $n$ ( you can reduce the memory, which I leave up to you to figure out ).
> 3 votes

# Answer
(added) As I now realise, you are asking for the number when the *total* number of stones is given.

It seems to be easy to count the number of *loosing* positions when the *maximum number* of stones in each pile is a power of two (minus one). Remember that a postion is loosing if the nim-sum of all the piles is zero, that is xor-ing all the bits will give $0$ at each bit position. So if there are $k$ piles each with at most $2^n-1$ stones, for each bit position, half of the initial positions xor's to $0$. So for each of the $n$ bit positions there are $2^k$ possible combinations for the $k$ piles. Half of these, $2^{k-1}$ xor to zero. This is to be combined to for each bit position, so ${(2^{k-1})}^n$. The total number of initial positions is ${(2^{k})}^n$.

For an arbitrary number of stones there is not such a nice formula, I am afraid.
> 2 votes

---
Tags: algorithms, game-theory
---


# Question
Title: Searching the best trading route - algorithm
Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount `a` of good `b` for amount `c` of good `d`.

I have made a simple table to point out what I am trying to explain:

In this case there are three different goods: Wood, Sand and Gras.

I also live in the village and noticed that the prices of the traders vary greatly. I have **1** wood and want to increase it by simply trading between the five dealers. But: **I must not visit a dealer more than once**.

There would be different routes, for example I could do `Dave - Adam`, which would result in +1 wood for me. A better route would be `Earl - Berta - Adam`, because it would mean +2 wood.

I think at that point you might already know what I am asking for. I am looking for a technique / algorithm to find the route which maximizes my input. The rules are:

* Input good = Output good
* Output value \> Input value
* Each node ("dealer") must not be visited more than once
* You do not have to visit all dealers
* Each dealer is limited to one trade ("Giving amount `a` of good `b` for amount `c` of good `d`").
* $a\in\mathbb{R}\_{\>0}$ and $c\in\mathbb{R}\_{\>0}$
* The benefit is calculated at the end by output - input, i.e., by the increase in the quantity of the goods that you're starting with (if you start with 1 wood, then all that matters is the number of woods you end with).
* It is important that the input good is the same as the output good ("Input good = Output good"). If I start with wood, I need to end with wood. If I start with sand, I need to end with sand, etc.

I don't even know how such a problem is called. That means that anything like algorithm names to solve it, the general name for this kind of problem, etc. would help me to continue with my research. I have already tried approaching it by converting the table to a graph and then run path-finding algorithms. That did not work, because I wasn't sure how to weight the edges and the Longest-Path-Problem was also in my way, which is NP-Hard for non-DAGs.

---

The traveling salesman problem (TSP) was already mentioned. I had a look at the Wiki page of the TSP. Quote: "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" I think my problem is very different, because:

1. I look for the most profitable route, not the shortest.
2. I don't have to visit every dealer ("city").
3. I must not return to the origin, because as I said each node ("dealer") must not be visited more than once.

---

The "village" can get quite big. About 200 different goods and 500 dealers, so the algorithm should be able to perform good in this scenario.

The last possibility would be to brute-force, but I really want to avoid that.

# Answer
This problem is NP-Complete by reduction from Directed Hamilton Path. I use the method of the linked mathoverflow answer. Let's say $b(v)$ and $s(v)$ is the good that villager $v$ buys and sells, respectively (each villager only buys/sells one good). Then you may ask, what dealers can I visit consequtively? This is the following graph:

$$G = \langle \text{Villagers}, \\{ (\sigma, \beta) | s(\sigma)=b(\beta) \rangle $$

This directed graph has an edge from $\sigma$ to $\beta$ iff $\sigma$ sells something that $\beta$ buys (using the letters $\sigma$ and $\beta$ because they sound like 's' and 'b' for seller and buyer). In this graph, you are one node called $y$ and you have a good, $s(y)$, which you want to sell. You can verify that you are looking for a route through $G$. How much profit do you make? If $\\$\_b(v)$ and $\\$\_s(v)$ are the buying and selling price of villager $v$'s goods, and you travel some route $v\_1\cdots v\_k$ through the village, then your profit is: (w.l.o.g. assume that you start with $1$ unit of your good)

$$ \text{Profit}(v\_1\cdots v\_k) = \prod\_{i=1}^{k}\frac{\\$\_s(v\_i)}{\\$\_b(v\_i)}$$

This suffices for a reduction from Directed Hamilton Path: Take a directed graph $H=\langle V, E \rangle$, and say you want to find out whether there is a Hamilton Path starting in vertex $x$. Suppose that the $n$ vertices are villagers. Each villager $v\_i$ trades his own good for his own good at a $1/1$ ratio. Now populate the village further as follows. For each edge $(\sigma,\beta)\in E$ in the graph, add a "stockbroker" villager called $\tau\_{\sigma,\beta}$ who buys $\sigma$'s goods and sells the goods that $\beta$ buys at a rate of two units of $\beta$ for each unit of $\sigma$. That is, $b(\tau\_{\sigma,\beta})=s(\sigma)$ and $s(\tau\_{\sigma,\beta})=b(\beta)$ at $\\$\_b(\tau\_{\sigma,\beta})=1$ and $\\$\_s(\tau\_{\sigma,\beta})=2$. In this scenario, you are villager $x$.

If your profit problem were easy, then you could ask 'Is there a route from $x$ which makes $2^{n-1}$ profit?' Iff there is such a route in the graph I constructed, then there is a Hamilton Path in the graph I constructed it from. $\square$

So this problem is NP-Complete and in fact it is hard even to approximate. Instances of the problem that are not contrived are probably more difficult. You can also make an elegant reduction from Traveling Salesman by assigning to each villager a profit $\varepsilon(v\_i)=\log\left(\frac{\\$\_s(v\_i)}{\\$\_b(v\_i)}\right)$, I'll leave the details up to you. If you really mean to solve this problem practically, you can look for some advice in this question here (link) and in the extensive literature on TSP and related problems. Personally, I would use a greedy algorithm which looks ahead some fixed number of steps, say $3$ steps. Or you can use an evolutionary approach, which should work just fine, too.

Here's one heuristic: given a candidate solution $v\_1\cdots v\_k$ computed by an evolutionary algorithm, you can check the intermediate profits halfway along the route, and quickly find the point at which you should have stopped. Fix only the last part of the path $v\_j\cdots v\_k$.
> 2 votes

---
Tags: algorithms, optimization, traveling-salesman
---


# Question
Title: How to prove the following xor equation?
In a test paper, a question is given as :

```
Let, x1^x2^x3^x4 =0 where x1, x2, x3, x4 are Boolean variables,and ^ is the XOR operator.

Which one of the following must always be TRUE?
(A) x1x2x3x4 = 0
(B) x1x3+x2 = 0
(C)  x1'^x3' = x2'^x4'
(D) x1+x2+x3+x4 = 0

+ is OR and concatenation is AND operator.

```

Correct answer is C, which I guessed because when all booloean variables are 1, then, neither A,B, or D will hold,**But what is the correct way to get to option C?**

# Answer
(I use the symbol $\oplus$ here because $\wedge$ is mathematically used for conjunction ("and") instead of exclusive-or)

First we rearrange the terms, \begin{align} x\_1 \oplus x\_2 \oplus x\_3 \oplus x\_4 &= 0 \\ x\_1 \oplus x\_3 \oplus x\_2 \oplus x\_4 &= 0 \\ x\_1 \oplus x\_3 &= x\_2 \oplus x\_4 \end{align} Then use $a \oplus b = a' \oplus b'$ to get (C). $$ x\_1' \oplus x\_3' = x\_2' \oplus x\_4' $$
> 2 votes

# Answer
Xor means when we get two same variables answer is 0. That is 0^0=0 and 1^1=0. it is possible to get x1^x2^x3^x4=0 if and only if x1^x2==x3^x4
> -1 votes

---
Tags: boolean-algebra
---


# Question
Title: Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?
I am experimenting with the sorting of arrays and their execution times. While using `bubblesort`, `insertsort` and `quicksort`, I have observed that relative standard deviation (%RSD) of execution times, for five hundred arrays of the same size containing random integers, decreases if the size of the arrays increases.

For example: if the %RSD of execution times while sorting 500 arrays, of size *fifty elements* each, is observed as 7%, the same for arrays with *five hundred elements* each is about 2.5%.

So the question is: why this value of change decreases with the increase in the array size?

**P.S.** I am using a cycle-accurate simulator (gem5) and taking exact clock cycles.

# Answer
In the case of `insertsort`, the complexity (time) depends on the number of swaps performed during sorting. A `kth` element `(k=1,2,3,...,n)` in an array of size `n`, may require `0 to k` swappings.

The execution time mentioned in the question depends on the sum of all the swaps performed during the sorting of a complete array.

Considering the random initialization of the arrays, the number of swaps performed for any `kth` element would be a random number bounded by the given range.

Now, If we consider the average value of the number of swaps per element (sum of all the swaps divided by the number of elements in the array), then, according to the law of large numbers, as the number of elements per array will increase this average will get closer to the expected value.

i.e., the variation in, the total number of swaps per array, among different arrays, will decrease.

Hence, the change (%RSD) in the execution times will also decrease.

--to be continued--
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, quicksort
---


# Question
Title: Computing gaussian kernel for image blurring
When I compute a gaussian kernel for image blurring should I normalize the 1D vectors? Because when I apply the raw values sometimes the image gets lighter or darker. The function I'm using is $f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{\frac{-x^2}{2\sigma^2}}$ or the 2D function. So, should I just apply the results using cross correlation/convolution or should I normalize first?

# Answer
> 0 votes
Your function is used to compute 2D kernel, which you should normalize, otherwise if the sum of used weights is higher than $1$ your image gets lighter, when it is smaller it gets darker. You should not normalize vectors, because you apply 2D kernel, so normalized 1D vectors will not help.

The operation that you perform is **convolution**, not correlation, which in common meaning would try to measure how similar is the part of image to given kernel.

---
Tags: image-processing, computer-vision
---


# Question
Title: Why is BNF considered an unsatisfactory technique for describing a language?
I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part highlighted by me):

> Faced with the situation as it exists today, where there is a generally known method of describing a certain class of grammars (known as BNF or context-free), the first instinct of these mathematicians seems to be to **investigate the limits of BNF**—what can you express in BNF even at the cost of very cumbersome and artificial constructions? This may be a question of some mathematical interest (whatever that means), but it has very little relevance to programming languages where it is more important to discover better methods of describing the syntax than BNF (which is already both inconvenient and inadequate for ALGOL) than it is to **examine the possible limits of what we already know to be an unsatisfactory technique**.

**Is there a specific reason the author considers the BNF to be an unsatisfactory technique for describing languages?** Could it be because you can only describe syntax and not semantics with a single BNF grammar (though, you can extend it to describe operational semantics via turning it into an attribute grammar)?

# Answer
> 3 votes
You mention one reason.

The other reason is that the syntax of programming languages isn't context-free, unless you *define* syntax to be that which can be, or is, described by a context-free grammar.

When Strachey's paper was written, the syntax of a new language, Algol 68, was being defined in a new formalism, two-level grammars, that was used to describe syntactic validity in full, including many things that, brainwashed by the "BNF is the syntax" meme, many of us do not consider part of syntax at all, such as all variables needing to be declared before use.

Most of us won't go that far, but will still agree that non-context-free syntactic features in programming languages exist.

# Answer
> 3 votes
I do not think that the semantics play a role. Your quote asks for "discover better methods of describing the syntax than BNF." Of course, things like function and variable names form part of the syntax. With BNF you cannot, for example, distinguish a language where variables must be decalred before usage from one where you can use undeclared variables. These things must be explained in accompanying text usually, which is not perfect.

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


# Question
Title: Is EXPTIME "solvable" or "checkable" in exponential time?
According to this video, EXP has problems that are exponentially difficult to check.

But according to this video, EXP are problems that are exponentially difficult to solve.

It would make sense to me, that if EXP contains problems that are exponentially difficult to check, that they would contain problems that are harder than NP-complete ones.

However, if it's true that EXP is problems that are just solvable in exponential time, why wouldn't they be equal? Wouldn't EXP therefore be a subset of NP (and so would R), as problems that are harder (like R) are still solvable in "non-deterministic" time? Because the term "non-deterministic" extends to any finite amount of time, correct?

Thank you in advance for resolving my confusion. If you could explain it as simply as possible, I would appreciate it, as I get easily bogged down by the set theory.

# Answer
> 5 votes
A language $L$ belongs to $\mathsf{EXPTIME}$ if there is an algorithm deciding it which runs in time $O(2^{n^k})$ for some $k$.

A language $L$ belongs to $\mathsf{NEXPTIME}$ if there is an algorithm verifying it which runs in time $O(2^{n^k})$ for some $k$. In other words, a language $L$ belongs to $\mathsf{NEXPTIME}$ if there is a constant $k$ and a machine $M$ running in time $O(2^{n^k})$ such that $x \in L$ iff there exists $y$ of size at most $O(2^{|x|^k})$ such that $M(x,y) = 1$. Alternatively, a language $L$ belongs to $\mathsf{NEXPTIME}$ if it can be decided in nondeterministic time $O(2^{n^k})$ for some $k$.

You observe correctly that every problem in $\mathsf{NP}$ has an $\mathsf{EXPTIME}$ algorithm, that just goes over all possible witnesses. This shows that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. It is conjectured that the two classes are distinct. In contrast, it is believed that $\mathsf{EXPTIME} \neq \mathsf{NEXPTIME}$, and this is stronger than (i.e., implies) the more famous conjecture $\mathsf{P} \neq \mathsf{NP}$, through a padding argument.

Note that nondeterministic computation can still be time-bounded. For example, $\mathsf{NP}$ is the class of languages computed by nondeterministic polytime algorithms. The nondeterministic time hierarchy theorem shows that $\mathsf{NP} \neq \mathsf{NEXPTIME}$; similarly, the deterministic time hierarchy theorem shows that $\mathsf{P} \neq \mathsf{EXPTIME}$.

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


# Question
Title: Check whether an undirected graph contains a simple cycle of length four using the "Squares" method
The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

> *Squares.* Design and analyze an algorithm that takes as input an undirected graph $G = (V,E)$ and determines whether $G$ contains a simple cycle (i.e., a cycle which does not intersect itself) of length four in $O(|V|^{3})$ time.

This can be solved by checking for each pair of vertices $u$ and $v$ whether they share at least two common neighbors; see the answer.

However, in the book, the authors gave a single-word hint: *Squares*.

Following the hint, I square the adjacency matrix $M$ of $G$ twice (i.e., $M \to M^2 \to M^4$) and check whether $M^4\[i\]\[i\]$ is true for some $i$. But this attempt fails because it produces "false positives" by treating $a-b-a-b-a$ or $a-b-c-b-a$ as cycles of length four.

How to fix the "false positives" in the squaring method above?

# Answer
Square $M$, to get $M^2$. Write $M^2 = D + P$, where $D$ is the diagonal part (all non-diagonal entries are zero) and $P$ is the non-diagonal part (all diagonal entries are zero).

Compute $Q=P^2$. Note that $Q\_{aa}$ counts the number of ways to start at $a$ and end at $a$, excluding cycles of the form $ababa$ and $abaca$ etc., but not avoiding cycles of the form $abcba$.

Now compute $R = MDM - D$. Note that $R\_{aa}$ counts the number of cycles of the form $abcba$ where $c \ne a$.

Let $S = Q-R$. We find that $S\_{aa}$ counts the number of simple 4-cycles that start and end at $a$. Thus, the graph has a simple 4-cycle if and only if one or more of the diagonal entries of $S$ are non-zero.
> 3 votes

# Answer
Here is a slightly different (but equivalent) approach. The entry $(M^4)\_{ii}$ computes the number of walks $i\to j\to k\to \ell\to i$. These are either squares (if all of $i,j,k,\ell$ are different), or of the form $i \to j \to i \to \ell \to i$ (possibly $j = \ell$), or of the form $i \to j \to k \to j \to i$. There are exactly $d(i)^2$ of the second type (here $d(i)$ is the degree of $i$, equal to $(M^2)\_{ii}$) and exactly $\sum\_{k \neq i} (M^2)\_{ik}^2$ of the third type. So $(M^4)\_{ii} \> \sum\_k (M^2)\_{ik}^2$ iff there is a square through $i$.

Note that this actually gives an $O(|V|^\omega)$ algorithm for detecting squares, where $\omega$ is the matrix multiplication constant (the best known bound, $\omega \< 2.373$, is due to Le Gall).
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton.

Now Assume that $R$ is a regular language and $D$ is a deterministic context-free language.
How can we prove that $R\cup D$ is a DCFL?

Note : I saw a similiar theorem for the intersection. But i'm new to PDA's and i almost have no idea how to prove this one.

Thanks in advance.

# Answer
> 6 votes
Yes, deterministic context-free languages are closed under union with regular languages.

It is easy to show they are closed under intersection with regular languages. We can apply a product construction. When reading a symbol we also do a step of a FSA that is running in parallel. Accepting a computation means accepting both the DPDA part and the FSA part.

This doesn't work for union. Why? Because a DPDA may end up in an infinite loop of $\varepsilon$-transitions, so it will never read all of its input. In that way we cannot test acceptance by the FSA.

In order to make this work we also need a normal form for DPDA, that they will never do such infinite loops, and always read all input. That normal form is usually proved when showing DCFL are closed under complement (and is non-trivial).

By he way, once we know that DCFL is closed under complement and closed under intersection with regular languages, closure under union with regular languages follows by De Morgan: $L\cup R = (L^c \cap R^c)^c$.

---
Tags: context-free, automata, pushdown-automata
---


# Question
Title: What is the difference between oblivious and non-oblivious merging, sorting etc
Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?

# Answer
Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as *sorting net*_ is oblivious, because it always compares the same elements disregarding data it gets, while Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data. Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from $n$ steps to $n^2$ (for example).

This definition for cache is very similar, it means that it takes advantage of cache independently of its size (cache length).
> 10 votes

---
Tags: algorithms, complexity-theory, sorting
---


title: Computing a subproduct tree

text:
# Question
Title: Computing a subproduct tree
Consider the following description of a subproduct tree.

We define a tree T for some points *x\[0\]* to *x\[n-1\]*, and define *m = log\_2(n)*.

Tree T is represented as a matrix where each row-column entry *i, j* is the product of pairwise nodes in the row above it. In total, there are m rows; the 1st row is has n column entries, and the last row has 1 column entry.

**In short, how does one compute the coefficients for a large n?** Once m \> 4, the coefficients of the entries become greater than 64-bits. Consider the product of *(x - i)* for *i = 0 to 15*. The coefficients become very large.

Unless we are working in a finite field, it seems as though one cannot construct such a subproduct tree for say *n = 2^20*.

Formally: http://specfun.inria.fr/bostan/publications/BoSc05.pdf

Addendum:

I understand the complexity of the operation, as stated in the next section of the paper. However, I'm unsure how one would practically approach computing the coefficients of this subproduct tree as size n grows to be large (say 2^20).

Ex, consider the following simple example:

# Answer
> 1 votes
## How does the computation scale?

Keep reading! The paper describes how this scales for $n$, in the *very next line* after the excerpt you show. In particular, the next line is Proposition 1, which states the running time of computing the subproduct tree, as a function of $n$. That tells you how the running time scales for large $n$.

## How do you compute the coefficients?

Follow the algorithm described in the paper! You already described the algorithm. Use exactly what you described.

## Don't the coefficients become large, when $n$ is large?

Yes, potentially. This is inherent to the task: if you want to compute some polynomial (the product) whose coefficients are large, then yes, the coefficients produced by such an algorithm will be large. This is pretty much a tautological statement.

---
Tags: trees, binary-trees, polynomials, subtree
---


# Question
Title: Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?
I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum tens of thousands of edges).

The map represents an arena in which two teams fight, and both have the ability to change the map, either by creating complete walls (removing a vertex from the graph), or changing weights on the edges (i.e. by temporarily making a hex difficult to walk over).

The reason I'm considering using all-pairs-shortest-path algorithm is because I need to simulate the game as fast as possible, and thus I can't waste time with actual pathfinding during the simulation.

**Is there a way to detect which paths need to be re-calculated when a change is made to the graph?** It seems that if I only increased the weights/removed vertices, I could only re-calculate the affected paths, is that true? And what if I'm also decreasing weights/adding new vertices/edges?

# Answer
> 3 votes
Yes. The phrase to search for in the literature is "dynamic shortest paths". "Dynamic" refers to the path that the graph might change, and we want to efficiently update the shortest paths (more efficiently than recomputing them from scratch).

There are different ways one might change the graph. Some papers consider the case where edges can be added. Others consider where edges can be removed. You can also find algorithms that can handle both kinds of changes; that might go under the name "fully dynamic shortest paths".

Search the literature. You'll find many algorithms, with different tradeoffs between running time, simplicity of implementation, and types of graph updates supported.

---
Tags: graphs, shortest-path
---


# Question
Title: Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?
Let `f` and `g` be two functions with integer range `0..m-1`. They may keep state and interact with the world (for example setting a seed or reading the current time), calling them multiple times may produce different results. `f` and `g` can see each other's state, but cannot modify the other's state.

Assume at least one of `f` and `g` is a cryptographically secure pseudorandom number generator, but it is unknown which one. Is it possible to create a function `h` that uses `f` and `g` and behaves as a CSPRNG? `h` is not allowed to set or read external state directly, the only way it can modify or read state is by calling `f` and `g` and observing their results. `h` should work for any given `f` and `g`.

Of course, `h` is not allowed to use any "true" source of randomness, and ideally the construction should not involve passing randomness tests.

As a related problem, I believe that if `f` and `g` were perfectly random, then `f + g (mod m)` would also be perfectly random. But I think in this deterministic case, it's always possible to create a `g` such that it "cancels out" `f` in `h`. Not sure how to prove this.

# Answer
> 3 votes
No. There's no way to create such an $h$.

Here's an informal sketch of the proof. Suppose $f$ is a CSPRNG. Then for all $h$, there exists a $g$ such that $h(f,g)$ outputs only even numbers. In particular, $g$ reads the state of $f$, deduces what $f$'s next output will be, and outputs something that will cause $h$ to output an even number (if necessary, by generating multiple candidate outputs and testing each one to see which will provoke $h$ to output an even number).

\[This is the main idea of a proof. To get a full formal proof, you'd also have to consider the case where $h$ ignores its second input or mostly ignores its second input. However, it's pretty easy to see that such a $h$ can't possibly be any good, either.\]

---

That's the theory. What about practice? In the real world, if you're not sure whether $f$ or $g$ are any good, *don't let them read the internal state of anything else*. Don't ever let something that might be malicious read the internal state of security-critical parts of your system.

---

If you know that $f$ and $g$ are independent (as random variables), and you know that at least one of $f,g$ is a secure CSPRNG, then $f+g \bmod m$ is indeed good (it's a secure CSPRNG). However, the critical requirement here is that they be *independent*. If one can read the internal state of the other, then they're not independent.

---
Tags: discrete-mathematics, cryptography, randomness, pseudo-random-generators
---


# Question
Title: Does the order matter in the adjacency matrix?
I have nodes a, b , c,d,N, and e in an adjacency matrix. If I follow the order as a,b,c,d,N,and,e , I get 100010(the question does not matter because I'm asking about the order) for b.But if I follow the order a,b,c,N,d,and e, I get 100100 which was done by my TA in the class. Does the order really matter? If so then is there a way to find order from the adjacency graphs?

# Answer
Let $f$ be an isomorphism from graph $G$ to graph $G'$ which takes vertex $v\_i$ to vertex $v\_i'$. Let $A$ and $A'$ be the adjacency matrix of $G$ and $G'$, respectively. If the rows and columns of $A$ are in the order $v\_1,\ldots,v\_n$, and the rows and columns of $A'$ follow the same order $v\_1', \ldots, v\_n'$, then it can be seen that $A=A'$.

If $f$ is an isomorphism from $G$ to itself, then $f$ is called an automorphism of $G$. Thus, $f$ is a permutation of $V(G)$ which maps edges to edges and nonedges to nonedges. If we permute the rows of the adjacency matrix $A$ by $f$, and if we apply the same permutation to the columns of $A$, we get back the same matrix $A$. Equivalently, a permutation $f$ of $V(G)$ is an automorphism of $G$ if and only if the permutation matrix $P$ corresponding to $f$ satisfies the equation $P^{-1}AP=A$. Recall that premultiplying a matrix $A$ effects row operations/permutations and postmultiplication effects column permutations.

So, graphs with the same structure (i.e. isomorphic graphs) have the same adjacency matrix (up to a permutation of the rows and columns - here, the same permutation must be applied to both the rows and the columns). The graph invariants which we study are the same for isomorphic graphs and so the ordering of vertices you choose for the adjacency matrix shouldn't matter.
> 1 votes

---
Tags: discrete-mathematics, adjacency-matrix
---


# Question
Title: How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?
As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C\_5$. How many $(x, y)$-paths of length $20$ are there?

# Answer
Hint: consider powers of adjacency matrix of $C\_5$ (Wiki: Matrix powers).
> 2 votes

# Answer
You can use the fact that if $A$ is the adjacency matrix of a graph, then the $(i,j)$th entry of $A^k$ is the number of paths of length $k$ from vertex $i$ to vertex $j$. This fact can be proved by induction. So we need to obtain the $(1,2)$th entry of the matrix $A^{20}$. You can compute $A^{20}$ using a computer, or by hand by diagonalizing $A$ (observe that $A$ is a circulant matrix). A SAGE simulation (see below) gives the answer to be 204,820.

```
sage: c5=graphs.CycleGraph(5)
sage: A = c5.adjacency_matrix()
sage: A^20
[215766 204820 211585 211585 204820]
[204820 215766 204820 211585 211585]
[211585 204820 215766 204820 211585]
[211585 211585 204820 215766 204820]
[204820 211585 211585 204820 215766]
sage:

```
> 1 votes

---
Tags: graphs, combinatorics, discrete-mathematics
---


# Question
Title: Are there any useful deterministic quantum algorithms for decision problems?
The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (a) Deutsch's algorithm, in which the quantum speedup is pretty trivial, (b) the Deutsch-Josza algorithm, which solves a promise problem rather than a decision problem, and (c) this algorithm (which I found by Googling): http://arxiv.org/abs/1108.5848, which also doesn't solve a decision problem. Are there other known examples of "interesting"/"useful" deterministic quantum algorithms, especially for decision problems?

I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available. Are there any interesting algorithms that use only a "realistic" set of quantum gates? (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)

# Answer
> 4 votes
There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions":

> a total boolean function $g$ on $n$ variables that has \[...\] exact quantum query complexity \[...\] $Q\_E(g) = \tilde O(\sqrt n)$.

---

More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.

EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:

1. Theoretical-side, **there's no universal set of gates**. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) & -\sin(10^\circ)\\ \sin(10^\circ) & \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}\_{my\\\_favorite\\\_gate\\\_set}$s instead of a nice unified one.
2. Practical-side, **there's no possibility of error correction**. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.

# Answer
> 2 votes
A small modification to Grover's algorithm can make it deterministic. So, you get a quantum algorithm that can search an unsorted database with quadratic speedup compared to a classical computer. Of course, as you pointed out, the usefulness of this algorithm very much depends on the set of gates we are allowed to use.

You can find the paper on arxiv.

---
Tags: algorithms, quantum-computing, probabilistic-algorithms
---


# Question
Title: Classify the set of all TMs whose languages from the accepting problem
Let $$L = \\{ \langle M \rangle \mid M \text{ is a Turing machine so } A\_{TM} \leq\_m L(M) \\}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} \cup co-\mathcal{RE}}$ ?

I gained some progrees showing $L \notin co- \mathcal{RE}$:
Define reduction $f:A\_{TM}\rightarrow L$ on input $\left\langle M,w\right\rangle$ returns:

* if $M$ accepts $w$ return $ \left\langle U\_{TM}\right\rangle $ ($L \left(U\_{TM}\right)=A\_{TM}$ so $\left\langle U\_{TM}\right\rangle \in L$)
* if $\left\langle M\right\rangle$ rejects $w$ return 1 (not a TM encoding hence not in L)

$f$ is computable and $\left\langle M,w\right\rangle \in A\_{TM}\iff f\left(\left\langle M,w\right\rangle \right)\in L$ hence $A\_{TM}\leq\_m L \implies L\notin co-\mathcal{RE}$.

Now I want to show that $L \notin \mathcal{RE}$. And I'm stuck..

Notation:

$A\_{TM} = \\{ \langle M,w \rangle \mid M \text{ is a TM}, w \in L(M)\\}$

$H\_{TM} = \\{ \langle M,w \rangle \mid M \text{ is a TM and $M$ halts on $w$} \\}$

# Answer
As suggested in the comments, the extended version of Rice's theorem clearly states this language is not in $RE$. Nevertheless, let us prove this claim via a direct reduction from a language known not to be in $RE$, let's say $$ \overline{HP} = \\{\langle M,w\rangle \mid M \text{ doesn't halts on }w \\}$$

We will show that $\overline{HP} \le L$ and conclude that $L \notin RE$.

The reduction will assume we have a machine that recognizes $A\_{TM}$ (call it $R$) and goes as follow. Given an input $\langle M,w\rangle$ we construct the output string $\langle M\_w\rangle$ which is a machine that, on input x, does:

1. repeat the loop:
1.1 run one step of $M$ on $w$
1.2 run one step of $R$ on $x$
1.3 if 1.1 halts - the machine $M\_w$ rejects. If 1.2 accepts - the machine $M\_w$ accepts.

It is easy to verify this is a computable reduction. Let's just verify it is valid.

Case I: $\langle M,w\rangle\notin \overline {HP}$, then eventually (say after $T$ steps) $M$ will halt on $w$ before the computation of 1.2 concludes, thus $L(M\_w)$ can be **decided** in less then $T$ steps and in particular it is decidable. Therefore $A\_{TM} \not\le L(M\_w)$ and thus $\langle M\_w\rangle \notin L$.

Case II: $\langle M,w\rangle\in \overline {HP}$, then $M$ never halts on $w$, which means that only step 1.2 is relevant, which means that $M\_w$ behaves in this case just like $R$. So it holds that $L(M\_w) = A\_{TM}$ and in particular, $A\_{TM} \le L(M\_w)$. Then, $\langle M\_w \rangle \in L$.
> 1 votes

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


title: Is Not-STCON is NL-Complete?

text:
# Question
Title: Is Not-STCON is NL-Complete?
$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$

I've tried the following proof:
Let $S\in NL$, and let $S^\complement \in coNL$. ($S^\complement$ complement is $S$)
Let $M\_S$ be the NDTM that solves $S$.
$x\in S \iff x\notin S^\complement$, so If I can decide membership in $S^\complement$, I can decide membership in $S$. Then I claim that $x\in S^\complement \iff(G\_x,v\_0,v\_{acc}) \in Co-STCON$, where $G\_x$ is the configuration graph of $M\_S(x)$, $v\_0$ is starting configuration, and $V\_{acc}$ is a single accepting configuration.

The problem I have with the proof above is that it has the form $x\in S \iff (G\_x,v\_0,v\_{acc}) \notin Co-STCON$, so I feel like I'm missing something essential here. Is it correct?

# Answer
> 4 votes
Your proof doesn't work, since you're using an oracle reduction rather than a many-one reduction.

To show that a problem $A$ is NL-complete, you need to show that for every $S \in \mathsf{L}$ there is a logspace-computable function $f\_S$ such that $x \in S$ iff $f\_S(x) \in A$ (that's the definition); it's enough to show such a reduction for a single NL-complete problem $S$ (exercise). You show instead that $x \in S$ iff $f\_S(x) \notin A$.

Showing that nonSTCON is NL-complete is actually not so easy. Even showing that nonSTCON is in NL is not so easy; it is equivalent to showing that NL equals coNL. This is a non-trivial result due to Immerman and Szelepcsényi.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Number of possible programs in a language
Is the number of possible programs usually finite or infinite? I'm playing with the idea of generating all possible programs for a language - is that even a finite number or must we be more specific, finite RAM etc?

# Answer
> 6 votes
When considering such questions we usually disregard limitations of real computers and think about a programming language theoretically.

A general-purpose programming language (any language used in practice falls into this category) has infinitely many programs. Furthermore, all programs can be generated systematically. Implementing a program which generates all programs may be a useful learning experience, but has little actual value. The number of all programs of length $n$ is exponential in $n$ and so is unfeasable, except for fairly small values of $n$.

# Answer
> 4 votes
**The number of programs of any given length is finite.** You can get an upper bound to the number rather simply: if the program's source code is $n$ bits long, then there are at most $2^n$ programs of that length. The real number will be far, far less, because of the need for programs to be syntactically valid. But any number less than a finite number is still finite, so "The number of programs of any given length is finite" still holds.

**The number of programs of all finite lengths is infinite.** This is depressingly easy to prove. In C++, take the programs which (apart from decoration) say `x=1`, `x=2`, `x=3`,… (and so on for ever) and you have your infinite list of programs.

**The number of programs of all finite lengths is countable rather than uncountable.** To show this, stick one binary digit $1$ to the front of the bit-stream representation of a program, and treat the resulting bit stream as a base-2 integer, most significant bit first. No two programs can have the same integer representation, so there are *at most* as many programs as there are integers, so the number of programs is *at most* as large as the number of integers, and "the number of integers" is the definition of countability.

# Answer
> 4 votes
As the other answers have indicated, in most programming languages of interest the set of possible programs is infinite. That means that in order to do any interesting combinatorics, you need to consider the programming language as a *family* of finite sets of programs, indexed by some parameter (such as "length"). This is a quite general pattern in combinatorics, though, so not really a reason to worry. For example, there are infinitely many binary trees, but we can enumerate all the binary trees with a given number $n$ of internal nodes, which yields the sequence of Catalan numbers $C\_n = \frac{1}{n+1}{2n\choose n}$.

If done with appropriate care, enumerating all of the programs of a given size can actually be very interesting! (I strongly disagree with Andrej's assessment that it is of little value.) For example, analogous to the case of the Catalan numbers (which count not *just* binary trees but also strings of well-balanced parentheses, noncrossing partitions, and a myriad of other families of objects), it can lead to the discovery of bijective correspondences between programs and other families of other objects, hence to new ways of thinking about a programming language.

In fact, this is exactly what has happened recently with the discovery of unexpected connections between different fragments of lambda calculus and different families of graphs embedded on surfaces. For example, the sequence $L\_n$ counting the number of closed *linear lambda terms* of a given size $n$ is OEIS sequence A062980, which it turns out also counts *rooted trivalent maps* (3-regular graphs embedded on a compact oriented surface without boundary) by number of edges. Combinatorists already know all sorts of properties about this sequence — for instance, they can prove that asymptotically

$$L\_n \sim \frac{3\cdot 6^n \cdot n!}{\pi}.$$

Moreover, this numerical coincidence can be explained constructively as a bijection between linear lambda terms (of size $n$) and rooted trivalent maps (with $n$ edges), see:

* O. Bodini, D. Gardy, and A. Jacquot. Asymptotics and random sampling for BCI and BCK lambda terms. Theoretical Computer Science, 502:227–238, 2013. (pdf)
* N. Zeilberger. Linear lambda terms as invariants of rooted trivalent maps. December 21, 2015. arXiv:1512.06751. (pdf)

The second paper also shows how to use this bijection to give a natural lambda calculus reformulation of the Four Color Theorem.

Since this is fairly recent work, the applications of these connections are still difficult to foresee, but I think it's safe to say that enumeration of programs can lead in quite unexpected directions!

---
Tags: programming-languages
---


# Question
Title: What is the archive attribute for windows files?
What is the archive attribute for windows files. What is Archive in file details?

# Answer
> 1 votes
As I understand it, it's basically a variable of sorts to work out what has and hasn't been backed up. So when a backup is taken, the archive attribute will be set to '0', now as a user modifies files, their archive attribute will be set to '1' meaning when the next backup is taken, rather than backing up every file again, the files with the archive attribute at '1' will be searched for and backed up. So in short, it's a clever way to ensure backups are both efficient and complete.

Taken from http://www.2brightsparks.com/resources/articles/understanding-file-attributes.html

---
Tags: attribute-grammars
---


# Question
Title: Flaw in linear programming solution for multi-commodity flow problem?
The multi-commodity flow problem problem statement - wiki

According to constraints of multi-commodity flow problem a given material must start at source *s* with demand *d* and end up at its target *t*. The linear program form of this problem as given in clrs is

*f* is flow, *c* is capacity, *u and v* are vertices, *d* is demand, *s* is source, *t* is target(sink). We are given *k* commodities. *i* corresponds to ith commodity.

Now How does these constraints guarantee that i commodity will end up only in target of i (ti) with its respective demand (di)

## Why It works for single commodity case

In single commodity case it includes all the constraints. This is popularly known as the Maximum Flow problem. The first constraint is capacity constraint, the second one is flow conservation. The fourth implies flow is non-negative.

## Why There is Problem for the multi-commodity case ?

There is no constraint on target which guarantees that flow will only go into its respective case.

For instance, this seems like a simple counter example:

# Answer
> 1 votes
The linear programming formulation from CLRS is fine. There is no problem with it.

Your purported counterexample isn't a valid counterexample -- it doesn't satisfy all of the inequalities. Take a closer look at the specification of the second inequality. For instance, when we are dealing with commodity $a$ ($i=a$) it says that we should have

$$\sum\_{v \in V} f\_{auv} - \sum\_{v \in V} f\_{avu} = 0$$

for all $u \in V \setminus \\{s\_a,t\_a\\}$. In particular, consider the case $u = t\_b$. We have

$$\sum\_{v \in V} f\_{at\_bv} - \sum\_{v \in V} f\_{avt\_b} = 0 - 2 \ne 0,$$

so the inequality is violated.

To put it in English: the second inequality requires conservation of flow for each commodity, except at that commodity's source and sink. For example, for commodity $a$, we must have conservation of flow at every vertex except $s\_a$ and $t\_a$. In your proposed counterexample, conservation of flow for commodity $a$ is violated at vertices $s\_b$ and $t\_b$; that's not allowed.

---
Tags: algorithms, graphs, np-complete, linear-programming
---