# Question
Title: Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?
Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators.

Is it the case that the construction of the SLR(1) parser and the LALR(1) always yield the same table?

If not, what happens if the grammar G is SLR(1)?

---

I'm particularly interested in this question about the following grammar:

\begin{align\*} C &\to E \\, \text{rel} \\, E \mid C \\& C \mid ! \\, C \mid \text{pred}\\, ( \\,Es\\, ) \\ E &\to \text{num} \mid \text{id} \mid E\\, +\\, E \mid E\\, \*\\, E \mid - \\,E \mid ( \\,E \\,) \\ Es &\to E \mid E\\, ,\\, Es \end{align\*}

Using a custom SLR and LALR table generator I obtain exactly the same table for the above grammar, with some shift/reduce conflicts that can be resolved by giving precedences in the order &, !, rel, +, \*, - and left associativity to &, + and \*. I'm in doubt whether my implementation is incorrect or the tables are really the same, and if this is the case whether there is some general rule that applies in certain circumstances.

# Answer
> 8 votes
If a grammar is SLR(1), then: \[Note 1\]

* The SLR(1) and LALR(1) state machines will have the same states
* The set of shift transitions in the two machines will be identical (as will the goto actions).
* The set of accept transitions in the two machines will be identical.
* The set of reduction actions in the LALR(1) machine will be a subset of the set of reduction actions in the SLR(1) machine.

In other words, it is possible for there to be a reduce action in the SLR(1) machine which is an error (or unspecified) action in the LALR(1) machine. In the case of an input which triggers such a reduce in the SLR(1) machine, that input will still eventually trigger an error before another shift transition is taken.

The difference comes from the fact that the SLR(1) algorithm generates a reduction action for a state with a reducible item for any lookahead in the follow set of the LHS of that item. The LALR(1) algorithm only includes the lookaheads which are feasible in the context of the state.

For example, here's a simple grammar: \begin{align\*} S &\to A \\, \[ \\, A\\, \] \\ A &\to \epsilon \\, \mid \\, ( \\, A \\, ) \end{align\*}

The follow set of $A$ is $ \\{ ) , \[ , \] \\} $.

Now consider any state in which $A$ follows the dot. For example:

\begin{align\*} A &\to ( \\, \centerdot A \\, ) \\ A &\to \centerdot \\ A &\to \centerdot \\, ( \\, A \\, ) \end{align\*}

This state has a shift action on $($ and a reduction action for $A \to$. It's clear that the reduction action should only be performed if the lookahead is $)$; any other lookahead is an error. But since $\[$ and $\]$ are in the follow set for $A$, the SLR(1) algorithm includes reduction actions for those lookaheads as well. The error will be detected after the subsequent goto action in the state $A \to ( \\, A \\, \centerdot \\, )$. In the LALR(1) table, these two lookaheads will lead directly to an error.

However, there are other entries in the LALR(1) table for this grammar in which the LALR(1) parser will also execute reductions with a lookahead which obviously cannot be shifted. Only in an LR(1) parser are errors detected immediately. (That's not a good reason to use a canonical LR(1) parser).

### Notes

1. I take the view that if conflicting transitions are generated, then the construction algorithm fails and no parser is produced. That's the way the algorithms are described in Aho, Sethi & Ullman, for example (the so-called "Dragon Book"). If you take the equally valid view that a parser is always produced, but is not necessarily deterministic, then the following statements would be true for all grammars.

---
Tags: formal-grammars, parsers
---


title: type theory notation troubles

text:
# Question
Title: type theory notation troubles
I'm working through "Types and Programming Languages" by Benjamin Pierce and I don't quite understand the notation. Particularly on Page 106, (chapter 9 Simply Typed Lambda-Calculus) there is a lemma (9.3.7):

$$ \text{If } \Gamma \vdash t:T \text{ and } x \notin dom(\Gamma) \text{, then } \Gamma, x:S \vdash t:T. $$

I understand the idea roughly but I can't quite read this statement out in english. How do I translate the turnstile symbol (\vdash in tex) in this context? In the book I've seen $$ \vdash t:T $$ translated as t is a closed, well-typed term but I don't quite see how to apply that in this context. Looking around apparently the turnstile symbol is also used to mean provable.

Gamma is the typing context and provides binding of variables and their types. t:T means the term t is has the type T. The function dom(gamma) is the set of variables bound by Gamma.

So my best guess for translating this is as follows:

If the term t having type T is a closed, well-typed term under the typing context gamma and x is not in the set of bound variables of gamma, then the term t having type T is still a closed, well-typed term in the typing context gamma after binding the term x having type S.

Is this roughly right? It makes sense but I still feel a bit shaky on the translation. Anyone have any other suggestions, corrections, or comments? Thanks

# Answer
$X \vdash Y$ means "The information in $X$ lets you prove that $Y$ is true." This is true in logic in general, as well as in type theory specifically. I often read this as "$X$ says that $Y$ is true."

So,

> If $\Gamma\vdash t\colon T$ and $x\notin\mathrm{dom}(\Gamma)$, then $\Gamma,x\colon S\vdash t\colon T$

translates as

> If we can prove that that $t$ has type $T$ using $\Gamma$, and $\Gamma$ doesn't directly assign a type to $x$, then adding to $\Gamma$ the assumption that $x$ has type $S$ doesn't change the type of $t$,

which is just my way of writing what you wrote.
> 8 votes

---
Tags: lambda-calculus, type-theory, notation, types-and-programming-languages
---


# Question
Title: "Practical forms" of Chernoff bound for inequality in expectation
From Wikipedia:

> The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
>
> (i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0\<\delta\<1$
>
> (ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0\<\delta\<1$

The assumption they use is $E\[X\]=\mu$.

Would (i) still hold if we only assume $E\[X\]\leq \mu$? Would (ii) still hold if we only assume $E\[X\]\geq\mu$?

If not, what "practical forms" do we have in these cases?

# Answer
> 2 votes
It is more practical just because it has

> the advantage of being easier to state and compute with in many situations (quoted from \[1\]).

---

I am not sure whether (i) still holds for $\mu' = E\[X\] \le \mu$. At least, we cannot obtain that directly from the following computation:

$$Pr\[X \ge (1 + \delta) \mu\] \le Pr\[X \ge (1 + \delta) \mu'\] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$

---

\[1\] Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.

---
Tags: probability-theory, chernoff-bounds
---


# Question
Title: How can a universal Turing machine simulate "bigger" ones?
I'm trying to find the answers of two questions about the Universal Turing machine.

1. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger number of states?
2. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger number of alphabet characters?

Can anyone help me with these questions?

# Answer
The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings.

Note, though, that the universal machine has a fixed number of states, which makes computing the transition function a little tricky. What we'd like to do is write some instructions that implement a big switch statement of the form, "If the state is $s$ and the character under the head is $x$, then move to state $s'$, write character $x'$ and move the head in direction $d$." So – and I think this may be the root of your question – how do we calculate the transition function if we don't even have enough states in the universal machine to store the transition function's input?

One way is to store the transition function as a binary tree. Suppose all the simulated machine has $2^q$ states and $2^\ell$ tape symbols. Store the transition function as a binary tree of depth $q+\ell$ where, at the first $q$ levels, you go left or right according to whether the next bit of the simulated state is a one or a zero and the next $\ell$ levels are the same but for the successive bits of the simulated tape character. Now, your universal machine can walk backwards and forwards on its tape, checking the next bit of the state/character, remembering that bit in its own states, moving back to the tree, putting a marker at the correct node, and so on.

This gets somewhat easier if you let your universal machine have multiple tapes but then you still have to show that your multitape machine is equivalent to a single tape machine.
> 10 votes

---
Tags: computability, turing-machines, simulation, turing-completeness
---


# Question
Title: Computing theory: can a single node be a subgraph?
Can a single node be considered a subgraph?

For example, if I had this graph, G:

`X`-----`Y`

and I deleted Y, leaving me with the graph

`X`

is this a subgraph (induced) of G?
What about the following argument?

Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.

Though this is only valid if a single node can be considered a graph.
In computing theory, what is the generally accepted norm?

# Answer
> What about the following argument?
>
> Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.
>
> Though this is only valid if a single node can be considered a graph.

That's completely circular. If a single node can be a graph, you can ask about its subgraphs and, sure, every graph is a subgraph of itself. But if a single node can't be a graph, it doesn't make sense to ask about subgraphs of something that isn't a graph.

In general, a single vertex is considered to be a graph, referred to as the "trivial graph". However, it's something of a special case in that it's often an exception to statements one might wish to make when proving things. For example, every connected graph contains at least one edge... except for the trivial graph; every graph has a proper subgraph... except for the trivial graph; etc. Because of this, writers often exclude the trivial graph from consideration. So, for example, in the "notation" section of a graph theory paper, you often see a statement such as "Except where stated otherwise, we assume that every graph contains at least one edge".

In this respect, asking whether the trivial graph is a graph is a bit like asking whether zero is a natural number. Some people will jump up and down and insist that it is; some people will jump up and down and insist that it isn't; the best plan is to say that it is or isn't according to what makes your life easiest in any particular situation.
> 5 votes

# Answer
Yes, an isolated node is usually considered an induced subgraph, as is the graph with no nodes (the empty graph), though sometimes the latter is banished from consideration. If you're not sure whether isolated nodes should be considered induced subgraphs in your particular context, you'll have to tell us more about it.
> 2 votes

---
Tags: graphs
---


title: Restricted version fo CNF-SAT

text:
# Question
Title: Restricted version fo CNF-SAT
Given formula $\phi$ on CNF-form in CNF-SAT. Clauses can be arbitrarily long. The problem is NP-complete and it is also given that part of the problem is that a variable can occur many times in a formula.

Another problem $CNF\_3$ is introduced. Each variable can at most occur **three** times, with a given formula. This problem is NP-complete.

Problem: Decide if this formula is satisfiable or not. Give a method translating any $\phi$ to a $CNF\_3$ formula $\psi$ such that $\phi$ is satisfiable if and only if $\psi$ is.

Following hints are given:

* Introduce new variables in $\phi$
* Variables $a$ and $b$ are equivalent if $(a\lor \lnot b )\land (\lnot a\lor b)$

I have trouble starting this task. Any help necessary is appreciated!

# Answer
Let $\phi$ be an arbitrary $\mathrm{CNF}$ formula. The idea is to start with $\psi := \phi$ and then replace each variable in $\psi$ that occurs more than three times by distinct copies that are logically equivalent.

Lets consider each variable $x$ that occurs $n$ times in $\psi$. If $n$ is less or equal than $3$, the (syntactic) $\mathrm{CNF}\_3$-condition is fulfilled for $x$ and we do not need to change $\psi$. So lets assume that $x$ occurs more than three times in $\psi$. We introduce $n$ new variables $x\_1, \ldots, x\_n$ and replace the $i^{th}$ occurrence of $x$ in $\psi$ with the new variable $x\_i$.

In order to have the property $\phi \in \mathrm{CNF} \iff \psi \in \mathrm{CNF}\_3$, we need to add the condition that all $x\_i$ must be equivalent, i.e. \begin{align} x\_1 \iff x\_2 \iff \ldots \iff x\_n. \end{align}

We can model a bi-implication $x\_i \iff x\_{i+1}$ like proposed in the hint with the two clauses \begin{align} (x\_{i} \lor \lnot x\_{i+1}) \land (\lnot x\_{i} \lor x\_{i+1}). \end{align}

Unfortunately, we cannot do this directly since doing so would cause each variable $x\_i$ of the set $\\{x\_2, \ldots, x\_{n-1}\\}$ to appear more than three times inside $\psi$: \begin{align} (x\_{i-1} \lor \lnot x\_{i}) \land (\lnot x\_{i-1} \lor x\_{i}) \land (x\_{i} \lor \lnot x\_{i+1}) \land (\lnot x\_{i} \lor x\_{i+1}) \end{align} Therefore, for each inner bi-implication $x\_i \iff x\_{i+1}$ above ($i \in \\{2, \ldots, n-2\\}$), we introduce a new variable $x\_{i,i+1}$ that acts as a bridge between $x\_i$ and $x\_{i+1}$: \begin{align} x\_i \iff x\_{i,i+1} \iff x\_{i+1}. \end{align}

Each bridging variable $x\_{i,i+1}$ occurs twice inside $\psi$. Furthermore, each new variable $x\_i$ occurs three times inside $\psi$, namely

* once inside clause where it replaces $x$, and
* twice inside the clause $x\_i \iff x\_{i,i+1}$.

Therefore, the new formula $\psi$ fulfills the syntatic $\mathrm{CNF}\_3$ condition after the replacement.
> 2 votes

---
Tags: np-complete, satisfiability, decision-problem
---


# Question
Title: How to state a recurrence that expresses the worst case for good pivots?
**The Problem** Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $\frac{3n}{4}$(a good pivot). Also with probability $\frac12$ the pivot selected will be between 1 and $\frac{n}{4}$ or between $\frac{3n}{4}$ and $n$(i.e. a bad pivot)

1.State a recurrence that expresses the worst case for bad pivots.
2.State a recurrence that expresses the worst case for good pivots.

**My Work:** I understand the overall idea of quicksort - pivot all the elements around the pivot(less-\> to the left, right -\> to the right) and repeat the process for the elements to left of the pivot and for the elements to the right of the pivot
Here is the recurrence I came up with for 1 -$ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(n-1) + n, & \text{if $n$ is \> 1} \end{cases}$
I was able to work out this recurrence by reasoning that if I just chose the worst possible pivot(either greatest or least), I would have to traverse through all the elements(the $n$) and then repeat this process for the rest of the elements(n-1)

I am having trouble with coming up with a recurrence that expresses the worst case for good pivots. The two I came up with is if you choose a pivot of $\frac{n}{2}$ and if you choose a pivot of $\frac{n}{4}$

The recurrence for a pivot of $\frac{n}{2}$ would be $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ 2T(\lfloor(n/2)\rfloor) + n, & \text{if $n$ is \> 1} \end{cases}$
I wasable to reason this out because if you had a pivot of $\frac{n}{2}$, you have to evaluate all the elements with regards to the pivot(the $n$) and then partition the equal proportions to the left and to the right of the pivot.

The recurrence for a pivot of $\frac{n}{4}$ would be $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(3n/4)\rfloor) + T(\lfloor(n/4)\rfloor) + n, & \text{if $n$ is \> 1} \end{cases}$

Which one of these would express the worst case for good pivots?

# Answer
> 2 votes
The worst case for the good pivot is one where you split in 3n/4 and n/4. Splitting into two equal parts of size n/2 is the best possible case you can have. On the other hand, for the good pivots, 3n/4 leaves you with the largest subproblem possible.

---
Tags: algorithms, recurrence-relation, recursion, discrete-mathematics, quicksort
---


title: T(n/3) + log(n)

text:
# Question
Title: T(n/3) + log(n)
how do you find the Theta of this problem... $$T(n) = T(\frac{n}{3}) + \log\_2(n)$$ I end up getting a pattern of $$T(\frac{n}{3^{k}}) + \log\_2(\frac{n}{3^{k-1}}) + \log\_2(\frac{n}{3^{k-2}}) + ... + \log\_2(n)$$ when I solve for k with T(1) = 1 I get this... $$\frac{n}{3^{k}} = 1 \\ n = 3^{k} \\ \ln n = k \ln 3 \\ k = \log\_3(n)$$ then I plug into the original problem and get this... $$\log\_2(\frac{n}{3^{\log\_3 n}}) +log\_2(\frac{n}{3^{\log\_3 n - 1}}) + ... + \log\_2(n)$$ I'm not sure how to proceed from this point. Any suggestions?

# Answer
Actually the Master Theorem does not apply in this recurrence.The reason is that $n^{\epsilon}$ is greater than $\log(n)$ for every positive $\epsilon$, making $\log(n)$ ,for a factor $n^{\epsilon}$,polynomially less than $n^{\log\_{b}a}=n^0=1$. So we have to work with the replacement method which you have done correctly. Now for $$n=3^k$$ we get $$T(n) = T(1) + \log\_{2}(\frac{3^k}{3^{k-1}})+\log\_{2}(\frac{3^k}{3^{k-2}})+...+\log\_{2}(3^k) $$ which gives us $$T(n) = T(1)+\log\_{2}(3)+\log\_{2}(3^2)+...+\log\_{2}(3^k)$$ which is the same as $$T(n) = T(1)+\log\_{2}(3)+2\log\_{2}(3)+...+k\log\_{2}(3) $$ and now we see that the recurrence can easily be written as $$T(n)=T(1)+\sum\_{b=1}^{k}b\log\_{2}(3) \Leftrightarrow T(n)=T(1)+\log\_{2}(3)\sum\_{b=1}^{k}b$$ then we simply solve the summation $$T(n) = T(1) + \log\_{2}(3)\frac{k(k+1)}{2}$$ we easily get $$k=\log\_{3}n$$ and finally we have $$ T(n) = T(1)+\log\_{2}(3)\frac{\log^{2}\_{3}n+log\_{3}n}{2}$$ And the solution is obviously $$T(n) = \Theta(log^{2}\_{3}n)$$ T(n)=T(n/5)+logn is solved accordingly

Sorry for my English!
> 4 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Normalizing edge weights and the effect on Dijkstra's algorithm
If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would finding the minimum weight (most negative weight) $w$ and adding the absolute value to every edge's weight preserve the shortest path, and get rid of the possibility of a negative cycle in one fell swoop? I can't seem to find any good literature on this, which makes me think that it can't be true.

# Answer
Your idea does not work. Adding an absolute value to every edge wont preserve shortest paths. To see this take this graph:

```
u------v
|      |
|      |
a------b

```

with all edge weights 1 except for $uv$ where the weight is 4. The shortest $uv$ path goes via $u \to a \to \to b \to v$. But if you add a +2 to every edge, the sortest $uv$ path is $u\to v$.

There is however a reweighting scheme that works. Check out Johnson's algorithm, which is built around this. Simply speaking: add a dummy vertex $x$ connected to all other vertices with a zero weight edge and add to every weight of an edge $(i,j)$ the value $d(x,i) - d(x,j)$.
> 3 votes

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


# Question
Title: Determining which states in a transition system satisfy a specific CTL formula
Trying to answer the following question:

However, my answer is that only one of these states satisfy the TS (which is for sure wrong since the next part of this question asks to remove states that don't satisfy the formula and compute the new TS).

Reasoning follows:

1 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

2 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

3 - does not satisfy the formula since if you go to 1, EXISTS NEXT c is violated

4 - satisfies the formula since all paths satisfy EXISTS NEXT c

5 - does not satisfy the formula since if you go to 6, EXISTS NEXT c is violated

6 - does not satisfy the formula since if you go to 4, EXISTS NEXT c is violated

Can anyone see where I have gone wrong with my reasoning?

Something else I'm not sure about is for example if we take 4, it is satisfied since all paths lead to other states that (together) satisfy the equation. Do we need to include these 'other states' in the satisfaction set?

Really grateful for any help.

# Answer
A hint that might put you in the right direction: Note that $\exists Xc$ (where $X$ is the "next" operator) holds in every state from which there exists a neighbor with $c$. Thus, for example, $1\models \exists Xc$.

Now, $\forall (\phi U \psi)$ holds if in all computations $\phi$ holds until $\psi$ holds. In particular, every state that satisfies $\psi$ also satisfies $\forall (\phi U \psi)$, since the eventuality holds immediately.

Thus, $1$ satisfies the formula. See if you can complete the rest of them now.
> 0 votes

---
Tags: model-checking
---


# Question
Title: Countability union of all finite and countably infinite sequences over finite alphabet
Is the set of all finite and countably infinite sequences over $\\{0,1\\}$ countable?

From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=\\{0,1\\}$, hence $\Sigma^\*$. (is this a good assumption?).

I later show that I can count each string in the following order: $0$,$1$ (length $1$), $00$, $01$, $10$, $11$ (length $2$) and so on.

However, I am very confused from the initial requirement "finite and countably infinite sequences". Does my method account for the countably infinite strings?

# Answer
Your solution for proving that $\Sigma^\*$ is countable is correct. However the set $\Sigma^\omega$ of infinite sequences is not countable, since it is in bijection with the set of subsets of $\mathbb{N}$, which is not countable. See this question.
> 2 votes

---
Tags: uncountability
---


# Question
Title: Is deciding whether the language of a TM contains all strings of length 4 computable?
I was going through some Halting Problem reduction and I found the following problem:

> Given a semi-decider TM $M$, does the language $L(M)$ contain all strings of exactly length $4$?

The question later asks to prove whether this is recursive or r.e. Going through some practicing, I came to the conclusion that this is must be r.e., since otherwise such problem would solve the Halting Problem.

So, I attempted this question by showing that $$HP \< 4LENGTH$$

My approach is to show that $4LENGTH$ is recursive and then showing the contraddiction, that $HP$ is not recursive, so is $4LENGTH$.

However I can't understand how to construct such machine. Moreover, by looking at some similar proof I see that they suggest to build a machine $M'$ that erases the tape, writes $I$ (input) on the tape and simulate $M$. However, I can't follow such proof.

Can someone describe how to solve such problem or give any direction?

# Answer
> 5 votes
This might help you understand a standard proof technique for such problems. An instance of HP is a pair, $(\langle M\rangle, x)$ where $\langle M\rangle$ is a description of a TM $M$ and $x$ is a string. To reduce HP to 4LENGTH we require a function $f$ that maps instances of HP to instances of 4LENGTH such that $(\langle M\rangle, x)\in HP\Longleftrightarrow f((\langle M\rangle, x))\in 4LENGTH$. In other words, an instance $I = (\langle M\rangle, x)$ will have a "yes" answer ($M$ halts on $x$) if and only if the transformed instance will have a "yes" answer ($f(I)$ accepts all strings of length 4).

Given $(\langle M\rangle, x)$, we'll define a TM $M'$, using $M$ and $x$, that acts as follows:

```
M'(y) =
   if |y| = 4
      erase y
      write x on the tape
      simulate M
      return accept

```

Now if $(\langle M\rangle, x)\in HP$, then $M$ will halt on $x$ and so $M'$ will accept any string of length 4, so $M'\in 4LENGTH$.

On the other hand, if $(\langle M\rangle, x)\notin HP$, then $M$ will never halt on $x$ and so $M'$ will never get to the `return accept` statement and so will accept nothing. Hence if $(\langle M\rangle, x)\notin HP$, then $M'\notin4LENGTH$.

To summarize, we have established a faithful mapping from instances of HP to instances of 4LENGTH.

---

Now to show that 4LENGTH is not recursive, we argue by contradiction. Suppose that 4LENGTH were recursive. Then there would be a decider, $D\_4$, for 4LENGTH namely, given any TM description $\langle N \rangle$, $D\_4$ would take that description as input and halt and either return "yes" if $\langle N \rangle\in 4LENGTH$ and "no" if $\langle N \rangle\notin 4LENGTH$.

We can then use $f$ and $D\_4$ to build a decider for HP. It would work like this:

1. Given an instance $I=(\langle M\rangle, x)$ of HP, use $f$ to produce an instance $f(I)=\langle N\rangle$ of 4LENGTH.
2. Run the decider $D\_4$ on $f(I)$.
3. If $D\_4$ answers "yes" to $f(I)$, then by the construction of $f$, $I$ must have been in HP. Similarly, if $D\_4$ answers "no", $I$ must not have been in HP. In short, we've built a decider for HP, contradicting the fact that HP is not recursive.

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


# Question
Title: Why doesn't parallelism necessarily imply non-determinism?
I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out.

I understand the difference between concurrency and parallelism. I get that concurrent programs are non-deterministic depending on the precise timing of events. "But parallelism doesn't necessarily imply non-determinism" - as said in the book. Why is that?

Does that imply that it's all dependent on the languages that support parallelism. Which implies that these languages should execute parallel programs in a deterministic manner?

Another question that I have is that the timing of events of concurrent programs depend on what exactly on what exactly? The architecture of the machine?

# Answer
The book is using the term *non-deterministic* in two different ways. In concurrent computations and parallel computations the *order* in which the computations occur is non-deterministic. The final *result* however may (or may not) be deterministic.

Consider the following example:

```
thread A        thread B
--------        --------
x = 0           y = 1

```

The `x` assignment might happen before the `y` assignment, or the `y` assignment might happen before the `x` assignment, so the *order* is non-deterministic, but the end result after both threads finish is that `x` contains the value `0` and `y` contains the value `1`. So the result is deterministic.

The two major ways in which we achieve deterministic results from non-deterministic ordering is (a) by performing completely independent computations in different threads and (b) by taking advantage of operations that are commutative and/or associative. An example of case (b) is if you have an atomic addition operator:

```
thread A               thread B
--------               --------
atomic_increment(x)    atomic_increment(x)

```

At the end of the computation x will have a value 2 larger than it had before the computation, no matter whether thread A's increment happened before thread B's increment, or the other way around.
> 4 votes

# Answer
Take matrix-matrix multiplication which can be done in parallel. Initially one node (thread, computer, or whatever), call it N0, divides the two matrices into blocks, and distribute those blocks to the other nodes. All nodes now compute the product of their matrix blocks, and send the result back to N0. Finally N0 constructs the matrix, resulting from the multiplication, by combining the blocks back together.

That is work done in parallel, with some overhead (distributing blocks, sending blocks back etc.), but completely deterministic!

Concurrency is usually found in multiplayer games, booking systems etc., whereas parallelism is often found when dividing a large problem into smaller problems, and distributing the small problems among nodes.
> 1 votes

# Answer
Parallelism studies systems that contain several parts where computations happen at the same time. Let's call these parts *nodes*. If all the nodes are deterministic (e.g. no random generator) and they all execute instructions at the same speed (i.e. they all have the same clock), then the system as a whole is deterministic: the state at time $t+1$ is fully determined by the behavior of the system at time $t$ and the way each node executes instructions.

An example of a parallel system is a microprocessor or microcontroller. All but the most basic processors have multiple subsystems that execute in parallel. Each instruction moves through the stages of a pipeline, and at any given time, the processor is in the process of executing many successive instructions, potentially one at each stage of the pipeline. It is essential for the design of the processor to know exactly when the data for an instruction will reach each component, and how much time (how many clock cycles) it takes to go from one component to the next.

Hard real time systems are also deterministic, and often parallel. For example, the controls of a vehicle consist of many processors, and the critical parts (engine, brakes — not e.g. the entertainment system) operate at a known speed with known reaction times. There is a class of programming languages, synchronous programming languages, designed to program such systems, which model parallel execution in a fully deterministic framework.

There are also higher-level parallel systems which are deterministic even though the lower-level layer isn't. This is typically the case when doing numerical processing. When a computation can be parallelized, the parts are dispatched to different processors, and the exact time they take to process their parts can depend on how fast each node is, how much communication bandwidth is available between the various nodes, on how the data is arranged, etc. The duration of the computation is not deterministic, but the result is: it's equivalent to running all the computations sequentially on a single processor. The reason such computations can be parallelized is that they contain parts that don't depend on each other, so it doesn't matter in what order these parts are executed — or whether some are executed at the same time on different nodes.

Terminology isn't completely standardized, but generally *parallelism* is used when systems are deterministic (at least as far as the result of the computation is concerned), and *concurrency* when systems are not deterministic. Concurrency studies systems where events can occur at unpredictable times, such as user input, network reception, etc. See also Distributed vs parallel computing
> 1 votes

---
Tags: parallel-computing, concurrency, nondeterminism
---


# Question
Title: Algorithm to recognize Strongly Regular Graph (SRG)
I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.

# Answer
There is a trivial $O(kn^2)$ algorithm:

1. Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.
2. Choose some neighbor $w$ of $v$ and calculate the number of common neighbors $\lambda$. Then verify that all other pairs of adjacent vertices have $\lambda$ common neighbors.
3. Choose some non-neighbor $x$ of $v$ and calculate the number of common neigbors $\mu$. Then verify that all other pairs of non-adjacent vertices have $\mu$ common neighbors.

If you like linear algebra, you can also compute the square $A^2$ of the adjacency matrix $A$. Then check that:

1. All diagonal entries of $A^2$ are equal to some constant $k$.
2. All off-diagonal entries $A^2\_{ij}$ such that $A\_{ij} = 1$ are equal to some constant $\lambda.
3. All off-diagonal entries $A^2\_{ij}$ such that $A\_{ij} = 0$ are equal to some constant $\mu$.

This algorithm takes time $O(n^\omega)$.
> 2 votes

---
Tags: algorithms, graphs, reference-request, check-my-answer
---


# Question
Title: Recursive language subtracted from recursively enumerable language
This is a homework problem but I am awfully confused. The problem reads as follows:

If $L\_1$ is recursively enumerable but not recursive, and $L\_2$ is recursive, then which of the following is the strongest true statement about the set difference $L\_1 - L\_2$?

a. It must be recursively enumerable and not recursive.

b. It might be neither recursively enumerable nor recursive.

c. It must be recursively enumerable and it might be recursive.

d. It must be recursive.

I understand exactly what a recursive language and recursively enumerable languages are. A recursive language is one for which there exists a Turing machine which halts and decides whether the string is in the language for all strings of the alphabet. A recursively enumerable language is one for which there exists a Turing machine which halts and accepts if the string is in the language, but may halt and reject or not halt for strings that are not on the language.

So an example of a recursively enumerable language would be all C programs which do not contain an infinite loop (since we obviously won't halt if the program does). I am a tad bit confused on finding an example of a recursive language.

So subtracting a recursive language from a recursively enumerable language means that, if I try to think this through, there exists a turing machine which may halt and accept all strings in the language, and removing a recursive language only means we remove some strings which would be halted on and accepted.

So I am leaning towards c, but I am very fuzzy. Any pointers?

# Answer
> 3 votes
The language that contains all input strings is recursive. Just create a Turing machine that always outputs true. So take that to be $L\_2$. $L\_1 - L\_2$ would be the empty no matter what $L\_1$ is. The empty language is also recursive. So now we have an example of a recursive language arising from $L\_1 - L\_2$.

The language that contains no input strings (the empty language) is recursive. Just create a Turing machine that always outputs false. So take that to be $L\_2$. Now $L\_1 - L\_2 = L\_1$ which is not recursive.

So $L\_1 - L\_2$ may or may not be recursive.

Now we are left with b) and c). To decide between these we can note that the language is always recursively enumerable. Proof:

Iterate outputs from $L\_1$ but only output them if they are not contained in $L\_2$ (check by a Turing machine which always terminates). We now have a Turing machine that outputs all elements of $L\_1 - L\_2$.

So $L\_1 - L\_2$ is always recursively enumerable.

# Answer
> 2 votes
If it is established that $L\_2$ is a proper $-$ and non-empty $-$ subset of $L\_1$, then $L\_1 - L\_2$ must be recursively enumerable, but not recursive. If that wasn't the case, you would be able to combine the Turing machines that decide for the presence of a word in $L\_1 - L\_2$ and $L\_2$ to have $L\_1$ proved recursive.

However, $L\_2$ might *not* be a proper subset of $L\_1$ (assuming you can even decide that!), so $L\_1 - L\_2$ brings us no additional information, and the strongest thing we can conclude, without knowing any further, is that $L\_1 - L\_2$ is recursively enumerable.

---
Tags: computability, undecidability
---


# Question
Title: What is the importance of c in big O notation?
From the definition of Big O, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n \> n\_0$. What I'm not able to understand is what is its importance in Big oh notation. Every question explains what is big-Oh and what how it uses useful. But I'm not able to understand what is $c$ actually in big-oh. There might be answer which I'm not able to get it due to its technical jargon.

Can someone explain me this in simple terms?

# Answer
> 4 votes
Let's suppose the constant $c$ wasn't there: let's say that $f(n)=O'(g(n))$ if $f(n)\leq g(n)$ for all large enoun $n$. So, for example, $n=O'(n^2)$ and $\log n = O'(n)$, as you'd expect. But let's look at some functions whose growth rates are closer. First, let $f(n)=n+1$ and $g(n)=n$: well, $f(n)\neq O'(g(n))$ because $n+1 \not\leq n$ for all $n$. Similarly, $2n\neq O'(n)$. SO, we see that the constant $c$ is absolutely essential to the definition of $O(-)$: it just doesn't do what we want it to do if we remove it.

$O(-)$ measures the growth rate of functions ignoring constant factors. It gives you notation to say things like "$f$ is linear" or "$f$ is quadratic". When we say "$f$ is linear", we don't distinguish between, say, $f(n)=n$ or $f(n)=4n$ or $f(n)=2n+12$: we ignore the constants. The constant $c$ in the definition of $O(-)$ allows it to ignore multiplicative constants and additive terms.

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


# Question
Title: Automatic translation between formal languages
There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar.

Would it be possible to make a general-purpose translator generator to automatically translate from a string in the language with production rules described by grammar $G\_1$ to a string in the language with production rules described by grammar $G\_2$? If so, what rules would have to be imposed? For practical purposes let's say these grammars must both be CFGs. Would a formalization of semantic rules for the grammars also have to specified for the translator generator?

An example of this hypothetical, general-purpose translator generator: the translator generator is given grammar $G\_1$ (which is a CFG representing a context-insenitive adaptation of the C programming language), $G\_2$ (which is a CFG representing a context-insenitive adaptation of the JavaScript programming language), and *a formalization of the semantic rules of the language with production rules described by grammar $G\_2$*1. The translator generator is expected to produce a translator which takes as input a string in the language with production rules described by grammar $G\_1$ and translates that string to a string in the language with production rules described by grammar $G\_2$.

---

1 I am not entirely sure of what this formalization of the language's semantic rules would look like, so if there exists some formalization which would make the existence of this general-purpose translator generator decidable, then I would also welcome suggestions on what this formalization would look like.

# Answer
Every reasonable, Turing-complete programming language is (in essence) an admissible numbering of all Turing-computable functions. As such, we know that there *is* indeed a computable compiler from (and to) any other such numbering/language.

"Computable" here means that the compiler can be expressed as Turing machine (or equivalent). It does *not* mean we that there is an algorithm that computes the compiler, given (representations of) both languages.

Finding this program by hand may be hard, too. I guess it won't be in practice, though, at least not for many pairs of languages. But the result need not be pretty; all we know is that we get *some* equivalent program. One look at uncompiled Java code tells you all you need to know.
> 5 votes

# Answer
I think you are asking this from a stand point of specific tools so let me answer this in two parts.

*Theory Part (ideal view):*

There is a notion of languages and a notion of computational systems that except these different classes of languages. Finite Automata can accept regular languages, Pushdown Automata can accept context-free languages. If we go all the way up in the Chomsky hierarchy we get recursively enumerable languages which are accepted by turing machines.

As long as the class of languages define by a certain syntax is less than or equal in power to the target syntax's class of languages then this is possible (at least in principal). Parser generators typically compile context-free grammars to turing machines (or turing complete systems rather) which is just jumping rather far in Chomsky hierarchy. Nicely however this allows us to use context-free grammars in settings where we need recursive enumerability like interpreters. I could in principal compile a context-free grammar to a context-free grammar but defined using a different syntax; this is just an issue of the syntax being used to define context-free grammars. What I could not however do is compile a context-free grammar to a regular expression. No semantic rules need apply in this ideal view.

*Practical part*:

Real parser generators don't just generate code that accepts a given context free language however. They add in bits of your code to produce abstract syntax trees for your programs to use. I think the details of translating something like Antlr 3 (LL grammars) to Bison (LR grammars which are more general) or some other parser generator would be a bit tricky; I wouldn't want to try it. They probably use slightly different template systems for your code for starters. It could be that they execute your code in different orders so unless your code was pure there would really be no hope of translating the code properly.

So I think the answer to "would semantic rules for the grammars also have to formally specified" would be yes. The code that generates the ASTs would need to be functional and pure or something like that. The substitution principal needs to apply I think which is not something that generally applies except in languages like Haskell where even their effectual code has the substitution property.

My bet is that something like this is possible between the right tools but I think it is a very tricky thing.
> 6 votes

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


# Question
Title: Can we check in polynomial time if the language of a DFA is closed against Kleene star?
I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^\*$). I think that yes, but I do not have an idea to do it.

# Answer
Assuming your DFA $A = (Q,q\_0,F,\delta)$ is minimal, here is one approach:

$L(A) = L(A)^\*$ iff $q\_0$ is accepting, and adding $\epsilon$-transitions from each accepting state $q$ to $q\_0$ does not change the language; the latter is true iff $L(A)\subseteq L(A\_q)$ for each $q\in F$, where $A\_q = (Q,q,F,\delta)$.

In order to check whether this holds, you can compute the product $A\times A$ and check whether the subset $F\times(Q\setminus F)$ is unreachable from $\\{q\_0\\}\times F$, which you can do in polynomial time. In some more detail:

The product automaton has the form $A\times A = (Q\times Q, (q\_0,q\_0), F\times F, \delta')$, where

* the set of states $Q\times Q$ consists of all pairs $(q\_1,q\_2)$ with $q\_1,q\_2\in Q$;
* the initial state is the pair $(q\_0,q\_0)$ (though we won't be needing it for our purposes);
* the accepting states are all pairs $(q\_1,q\_2)$ where both $q\_1,q\_2$ are accepting in $A$;
* the transition function $\delta'$ applies the original transition function to both components of a pair, i.e. $\delta'((q\_1,q\_2),a) = (\delta(q\_1,a),\delta(q\_2,a))$.

In order to check whether $L(A)\subseteq L(A\_q)$ for some $q\in F$, we start from the pair $(q\_0,q)$; there should be no word $w$ such that $\delta(q\_0,w)\in F$ and $\delta(q,w)\notin F$, which is equivalent to the set $F\times(Q\setminus F)$ being unreachable from $(q\_0,q)$ in $A\times A$.

For example, consider the language given by the regular expression $(a + ab + ba)^\*$ mentioned earlier by J-E. Pin. It is accepted by the automaton $A=(Q,q\_0,F,\delta)$, where

* $Q=\\{q\_0,q\_1,q\_2,q\_3\\}$,
* $F=\\{q\_0,q\_1\\}$,
* $\delta = \\{(q\_0,a,q\_1),(q\_1,a,q\_1),(q\_2,a,q\_0),(q\_3,a,q\_3),(q\_0,b,q\_2),(q\_1,b,q\_0),(q\_2,b,q\_3),(q\_3,b,q\_3)\\}$.

The only pair we have to check is $(q\_0,q\_1)$; exploring the states we can reach from it, we get:

* $\delta'((q\_0,q\_1),a) = (q\_1,q\_1)$ - note that both components are the same; since $A$ is deterministic, this will be also be the case for all states reachable from here, in particular we will never reach any $(q,r)$ with $q\in F$ and $r\notin F$. We therefore don't need to explore this branch any further.
* $\delta'((q\_0,q\_1),b) = (q\_2,q\_0)$. Fine because $q\_2\notin F$.
* $\delta'((q\_2,q\_0),a) = (q\_0,q\_1)$. Back to where we started.
* $\delta'((q\_2,q\_0),b) = (q\_3,q\_2)$. Not only is $q\_3\notin F$, but it is a trap state, i.e. all states we can reach from here are of the form $(q\_3,q)$ and therefore not in $F\times(Q\setminus F)$.

Since we cannot reach $F\times (Q\setminus F)$ from $(q\_0,q\_1)$, we now know $L(A)\subseteq L(A\_q)$ and therefore $L(A) = L(A)^\*$.
> 6 votes

---
Tags: algorithms, complexity-theory, regular-languages, time-complexity
---


title: Second Chance Page Replacement

text:
# Question
Title: Second Chance Page Replacement
In the second chance page replacement algorithm, if a page's reference bit is already set to 1, and the next page in line of the reference string is the same page, does the reference bit stay at 1 or is it reset to 0?

# Answer
The reference bit stays at 1, it is set to 0 only in two circumstances, when the page is read from disk, or when the algorithm gives a page a second chance.
> 1 votes

---
Tags: operating-systems, paging
---


# Question
Title: Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?
Is the language $L = \\{ a^ib^j \mid i\ \nmid\ j \ \\} $ context free ?

If we fix $n \in N$ then we know that the language $L = \\{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \\} $ is context free (as it can be presented as a finite union of context free languages in a similar way to the example here: Is $L= \\{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \\} $ context free?)

I think that it's not context free but have failed to prove it. By reading other questions on this site I noticed this interesting observation: CFL's in $a^\*b^\*$ are closed under complement as can be seen here: Are context-free languages in $a^\*b^\*$ closed under complement?

So our language $L$ is context free if and only if $ \bar L = \\{ a^ib^j \mid \ \ i\ \mid\ j \ \\} $ is context free. I tried using the pumping lemma but to no avail.

Thanks in advance

# Answer
> 5 votes
If I'm not mistaken, you can pump $\bar L$ using $\sigma = a^{n}b^{n^{2}}$, because $n \mod n^{2} = 0$. The result is that $\bar L$ is not context free. The property that you mentioned has an "iff", then $L$ is not context free.

# Answer
> 0 votes
Using $\sigma = a^nb^{n^2}$(in $\overline{L}$) you can pump any amount of b's you want and pumping lemma is fulfilled.

Consider $\sigma= uvwxy$ with $vx$ a secuence of b's and $\sigma'=uv^iwx^iy$ with $i \in \mathbb{N}\_0$.

Then the amount of a's in $\sigma'$ is constant $n$, the amount of b's is $n^2 + |vx| (i-1)$ and $1\leq|vx|\leq n$ (pumping lemma).

So if you choose the descomposition with $|vx|=n$ you can always divide $n^2+n(i-1)=n(n+i-1)$ with $n$ a's $\forall i$.

Finally we can't use pumping lemma in this demostration(Im doomed).

# Answer
> -2 votes
it is CFL. consider this CFG

S --\> X | Y

X --\> aXb | aX | a

Y --\> aYb | Yb | b

---
Tags: formal-languages, context-free, pumping-lemma, pushdown-automata
---


title: Application of the four color theorem

text:
# Question
Title: Application of the four color theorem
I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.)

I tried Googling for applications but couldn't find any.

# Answer
One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.
> 7 votes

# Answer
Graph coloring problems are widely applicable to the problem of scheduling.

Consider a University, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as possible, to run as many exams concurrently as you can.

You can represent this as a Graph coloring problem: you make $G=(V,E)$ where each class is a vertex, and an edge between vertices any time a two classes contain the same student. Your colors will represent different exam timeslots. The minimum number with which you can color that graph is the smallest number of timeslots you need to write all your exams.

The problem in general is NP hard, but if you had some knowledge about your schedule, say, that it was planar, then you could apply the 4-color theorem to write all of the exams together.

I'm not 100% certain you'd ever get a planar graph in a real-life scheduling problem, but there's a wider lesson here: graphs are widely applicable to things which aren't immediately obvious. The 4-color theorem isn't just about graphs and maps, it can be used to model real life problems where you're expressing some set of objects, and some binary relations between those objects.
> 3 votes

# Answer
yes planar graph $n$-coloring for low/fixed $n$ has minimal applications, mainly planar map coloring. however $n$-coloring for arbitrary $n$ is NP complete, it was one of the 1st problems proven NP complete, hence tying into the massive edifice of theory. but actually even $n$-coloring can be reduced to 3-coloring via a basic transformation.\[1\] so $n$ coloring for $n \geq 3$ is NP complete *(but not restricted to planar graphs)*. there are probably other reductions to 4-coloring & planar maps studied in the literature. ie to get a better feel of its significance one would have to study the possible reductions to it which is a complex/advanced/wideranging topic.

but another angle is that the question of 4-coloring of a planar map/graph was a difficult open problem in mathematics/computer science for many decades (actually over 1½ century old, and one of the earliest highly advanced graph problems). mathematics advances through solving unsolved problems. it fits into a common core pattern of "problems that are easy to state but the solutions/proofs were inaccessable for a long time and are very complex". this is a fundamental *asymmetry* widespread in math that shows the limits of mathematical/theoretical *leverage*.

the techniques that are found to succeed can be applied to other unsolved problems and sometimes open new theoretical/conceptual vistas/abstractions. sometimes remarkable proofs are valuable in their own right and the 4-Color theorem fits this category. it is one of the most sophisticated early automated theorem proofs. further work has gone into improved human-readable simplifications since it was discovered and caused a relative shock through the theoretical community on its announcement, and sparked much further analysis and commentary. it serves as a key benchmark/milestone/test case for improvements in automated theorem proving.

\[1\] 3 coloring is NP complete
> -3 votes

---
Tags: graphs, colorings
---


# Question
Title: Is the union of finite and infinite sequences over alphabet of length 1 countable?
Is the union of finite and countably infinite sequence over alphabet $\Sigma=\\{1\\}$, countably infinite as well?

I understand this is similar a question to the one of finite and countably infinite strings over $\\{0,1\\}$, however I think that the previous argument is not valid in this case.

Now, countably infinite strings over $\\{0,1\\}$ can be of any kind, e.g.

$$e\_i \in \Sigma^\*, e\_i=100000...$$ $$e\_k \in \Sigma^\*, e\_k=110000...$$

However, I noticed that if I pose the same question with an alphabet of a character only, say $\\{1\\}$, there is only 1 infinite sequence that I can generate $11.....$, hence:

$$S = \Sigma^\* \cup \\{111..\\}$$

From this assumption, I could map $0$ to the infinite $11...$ and assume that this set S is uncountable. Is this a valid argument? Can someone help me formalize this?

# Answer
You haven't defined what you mean by "finite or countably infinite sequence" over an alphabet $\Sigma$, so let me assume that a "finite sequence" is a word over $\Sigma$, while a "countably infinite sequence" is an $\omega$-word over $\Sigma$, that is, a mapping from $\omega$ (the set of natural numbers) to $\Sigma$.

In your case, there is exactly one word of each length $0,1,2,\ldots,\omega$, so the set of "finite and countably infinite sequences" is countable, since the set $\omega + 1 = \omega \cup \\{\omega\\}$ of possible lengths (which is in one-to-one correspondence with the possible "finite and countable infinite sequences") is countable.

If you want to be very formal, you can show that $\omega + 1$ is countable by giving an explicit bijection between $\omega$ and $\omega + 1$, such as $$ 0 \mapsto \omega, \quad n+1 \mapsto n \text{ for all } n \geq 0. $$
> 2 votes

---
Tags: sets, uncountability
---


# Question
Title: Turing Machine that computes maximum steps of halting machines
Suppose that $TM\_{halting}$ is the set of machines that halt.

Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in $TM\_{halting}$ can take on an input of length $n$.

Is the function $f(m,n)$ computable?

# Answer
Hint: If you could compute $f(m,n)$, then given a Turing machine $M$ with $m$ states and an input $x$ of length $n$, the Turing machine will either stop within $f(m,n)$ steps or never halt.

This argument actually shows that it is impossible to compute any *upper bound* on $f(m,n)$. In other words, $f(m,n)$ grows faster than any computable function.
> 6 votes

# Answer
You can simulate a Turing machine for any fixed number of states to see whether it will halt. If you could compute $f(m,n)$, you could solve the halting problem by simulating for $f(m,n)$ steps, then returning whether the test machine has halted yet or not.
> 3 votes

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


# Question
Title: Regular expression for language with even number of 0's and 1's
Let $\Sigma=\\{0,1\\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s?

If we only require an even number of $0$'s, the language $(1^\*)\mid(1^\*01^\*01^\*)^\*$ works. But once there is a requirement on both $0$'s and $1$'s, I'm not sure how to do it.

# Answer
> 0 votes
Constructing regular expressions is usually more complicated than programming finite state automata. The standard way would be to construct a FSA and translate that one into a regular expression using standard techniques.

But if you prefer, it can be done directly, in two steps. Start by making two regular expressions $\alpha$ and $\beta$.

* First $\alpha$ specifies strings with *even* number of $1$'s, and exactly two $0$'s, one of which is the last symbol of the string.
* Similarly $\beta$ specifies strings with *odd* number of $1$'s, and exactly two $0$'s, one of which is the last symbol of the string.

Then build an expression for strings that have an even number of $0$ ánd an even number of $1$'s based on $\alpha$ and $\beta$.

---
Tags: regular-expressions
---


# Question
Title: What are some of the best circuit separations that we know of and that we suspect?
We know that $\mathsf{non-uniformAC^0\subsetneq PSPACE}$, $\mathsf{non-uniformACC^0\subsetneq NEXP}$. We know that $\mathsf{uniformACC^0=PH}$ is a possibility.

What are some of circuit separations that we know of?

What are some circuit separations that seem farthest apart but cannot be separated? By this question I mean that even though $\mathsf{uniformTC^0\subsetneq PH}$ is a possibility, an answer with $\mathsf{uniformACC^0\subsetneq PH}$ suffices since $\mathsf{uniformACC^0\subsetneq uniformTC^0}$ is hypothesized.

# Answer
> 3 votes
For all uniform classes $\operatorname{UF}$, for essentially any non-uniform class $\operatorname{NU}$, one will
have $\\: \operatorname{NU} \not\subseteq \operatorname{UF} \\:$, $\\:$ since $\operatorname{NU}$ should be uncountable and $\operatorname{UF}$ is countable.
("Proof:" $\\;\\;\\;$ By any reasonable definition of being uniform, for a language to be in $\operatorname{UF}$
there must be something in a particular at-most-countable set of things such that the
thing determines the language, so there are at most countably many languages in $\operatorname{UF}$.
On the other hand, for each subset $S$ of $\\:\\{\hspace{-0.03 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.04 in}\\}\\:$,$\\:$ the definition of $\operatorname{NU}$ should
mean that \[the language consisting of exactly the strings whose length is in $S\hspace{.02 in}$\] is in $\operatorname{NU}$.
In that case, since those languages are all different, $\operatorname{UF}$ will be uncountable.
"Therefore," one will have $\\: \operatorname{NU} \not\subseteq \operatorname{UF} \\;$.)

In particular, $\\;\\;\\; \mathsf{non-uniformAC^0} \\: \not\subseteq \\: \operatorname{PSPACE} \\;\\;\\;$ and
$\mathsf{non-uniformACC^0} \\: \not\subseteq \\: \operatorname{NEXP} \\;\\;\\;$, $\\;\\;\\;$ so both claims in your initial sentence are false.
It is far more interesting to ask which uniform classes
are subsets of which non-uniform classes.
$\operatorname{REG}$ $\\: \not\subseteq \\: \mathsf{non-uniformAC^0} \\;\\;\\;$, $\\;\\;\\;$ since $\\;\\;\\;$ parity $\\: \not\in \\: \mathsf{non-uniformAC^0}$ $\\:\\:\\:\\:$.
$\operatorname{NEXP} \\: \not\subseteq \\: \mathsf{non-uniformACC^0} \\;\\;\\;$; $\\;\\;\\;$ which your question on cstheory was asking about.
$\operatorname{MA\_{exp}}$ $\cap \hspace{.03 in}\operatorname{co-MA\_{exp}}$ $\\: \not\subseteq \\:$ $\operatorname{P/poly}$ $\\;\\;\\;$, $\\;\\;\\;$ by page 16 of this paper.
$\operatorname{AM\_{exp}}$ $\\: \not\subseteq \\:$ $\operatorname{(NP\cap coNP)/poly}$ $\\;\\;\\;$, $\\;\\;\\;$ by this paper. $\\;\\;\\;\\;\\;$ (The right-hand-side of
the last non-containment is likely smaller than the class one would think it means.)
This paper shows that $\operatorname{MA\_{exp}}$ can't be decided by circuits with "half-exponential" size.

---
Tags: complexity-theory
---


# Question
Title: Sliding window protocol when number of packets is equivalent to the window size
I am currently taking a course in computer networking and I am curious about the following situation:

Given $n$ packets and a window size of $n$ (i.e., the number of packets is equivalent to the window size), what would happen in the following scenario?:

Packet 1 is sent by Host A and the corresponding ACK is received. Do the window boundaries need to be updated to $\[2:n + 1\]$ or would it remain as $\[1:n\]$ (as there would be $n - 1$ remaining packets (strictly less than the window size, $n$)?

# Answer
Definitely, the window boundaries will be updated, in other words, the window will be shifted regardless of the fact remaining packets are strictly less than window size.

But the main point is after shifting,**window will not be fully occupied**.The window in sliding window protocol is a buffer, which stores only those packets whose acknowledgement is not received. But because the packet 1's ack is received, it would no longer remain in the window.
> 2 votes

---
Tags: computer-networks, protocols
---


title: Oracle for an inverse function

text:
# Question
Title: Oracle for an inverse function
A. Let $F$ be a monotonically increasing real function from $\[0,1\]$ onto $\[0,1\]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the oracle?

I think the answer is no, because of a simple counting argument: there are uncountably many possible answers, and with a finite number of calls we can get only countably many answers. Is this correct?

B. Let $F, G$ be two functions as above, and let $H$ be their average: $H(x)=\[F(x)+G(x)\]/2$. Given an oracle to $F^{-1}$ and an oracle to $G^{-1}$ and a number $y$, is there a way to calculate $H^{-1}(y)$ in a finite number of calls?

I think the answer is no, but how can I formalize the counting argument?

Is this possible to reduce to this problem from problem A? Or from another problem which provably cannot be solved in finite time?

NOTE: It can be argued that any function on reals is inherently infinite because even the output of a real number might take infinite time. So for this question, assume that we have a computer that can input, output and do arithmetics on real numbers in constant time per operation.

similar question was posted in math.SE, no answers yet.

# Answer
I am skipping the first question, question A, as it is not clear to me how it can make sense formally, since I am not familiar with the formalizations the OP mentions in a comment: Are there established complexity classes with real numbers?

I am only adressing the relation between question A and question B, proving that question B can be reduced to question A, which the OP considers of interest in itself. And since we are supposed to deal with only one question at a time, this follows the local rules. **:)**

## Question B reduces to question A : B ≤ A

First I will rephrase both questions, so as to add a missing hypothesis (bijectivity of the function, though existence of an inverse implies it), and also to use notations that will make the proof easier to state.

**Question A**: Let $F$ be a bijective, monotonically increasing real function from $\[0,1\]$ onto $\[0,1\]$. Given an oracle to compute $F$ on any input and a number $y\in\[0,1\]$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the $F$ oracle?

**Question B**: Let $H, K$ be two functions like $F$ above, and let $G$ be their average: $G(x)=\[H(x)+K(x)\]/2$. Given an oracle to compute $H^{-1}$ and an oracle to compute $K^{-1}$ and a number $y\in\[0,1\]$, is there a way to calculate $G^{-1}(y)$ in a finite number of calls to the $H$ and $K$ oracles.?

Note: all functions considered are bijective monotonic, but for readability we leave implicit the related arguments, though they do matter in some of the inferences below.

The idea of the proof is that, if $x=G^{-1}(y)$ is a solution to problem B, then there are two numbers $h,k\in\[0,1\]$ such that

1. $y=(h+k)/2$, and
2. $h=H(x)$, and $k=K(x)$ for some $x\in \[0,1\]$

We try to resolve the problem by defining a variable $u\in\[0,1\]$, so that $h$ and $k$ are computed from $u$ to take all possible values while $u$ varies from $0$ to $1$.

From $y=(h+k)/2$ we get $h+k=2y$. So we define: $h\_u=2yu$ and $k\_u=2y(1-u)$.
This ensures that $y=(h\_u+k\_u)/2$, but will let $h\_u$ or $k\_u$ become greater than $1$ when $y$ is greater than $1/2$.

So, we must actually consider two somewhat similar cases, depending on the value of $y$, after noting that $h\_u$ and $k\_u$ are both monotonically increasing functions of $u$.

**case 1**: $y\leq 1/2$

What we want is to find $h$ and $k$ such that $h=H(x)$ and $k=K(x)$ for some value $x$.

We define the function $D(u)=H^{-1}(h\_u)-K^{-1}(k\_u)=H^{-1}(2yu)-K^{-1}(2y(1-u))$
Note that $H^{-1}(0)=K^{-1}(0)=0$.
Hence $D(0)=H^{-1}(0)-K^{-1}(2y)=-K^{-1}(2y)$,
and $D(1)=H^{-1}(2y)-K^{-1}(0)=H^{-1}(2y)$.

So the function $D(u)$ is increasing onto $\[-K^{-1}(2y),H^{-1}(2y)\]$, and the solution to finding the value of $u$ that corresponds to the right values of $h$ and $k$ is given by the equation $D(u)=0$.

However, we intend to resolve it using an algorithm to solve question A, so we must normalize the interval to make it $\[0,1\]$.

For that we define $F(u)=\frac{D(u)+K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$
The function $F$ satisfies the conditions of question A,
and we remark that $D(u)=0$ iff $F(u)=\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$.
So we have to compute $u\_0=F^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)})$, which can be done using the algorithm answering question A. Then $G^{-1}(y)=H^{-1}(2yu\_0)$, or to summarize in one formula:

$$G^{-1}(y)=H^{-1}(2yF^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}))$$

Each computation of $F(u)$ uses only a finite (small) number of calls to the oracles for $H^{-1}$ and $K^{-1}$. Thus a solution to question B can be computed with a finite number of oracle calls if that is the case for problem A.

**case 2**: $y\>1/2$

This case is a bit more complicated, as different bounds must be found for varying $u$ so that $h$ and $k$ do not get greater than $1$, since the functions $H$ and $K$ are defined only onto $\[0,1\]$.

Since $y=(h\_u+k\_u)/2$, we have $h\_u=2y-k\_u$. Thus, $k\_u\leq 1$ implies $h\_u\geq 2y-1$.

The same reasonning holds, exchanging $h$ and $k$, so that we have $h\_u,k\_u\in \[2y-1, 1\]$. Since $u=h\_u/(2y)$, we have $u\in\[u\_0,u\_1\]$ with $u\_0=1-1/(2y)$ and $u\_1=1/(2y)$.

In order to have a variable $v$ varying in $\[0,1\]$, we normalize by defining $v=(u-u\_0)/(u\_1-u\_0)$. But $u\_1-u\_0=1/(2y)-(1-1/(2y))=(1-y)/y$ which gives $v=(u-u\_0)y/(1-y)$. Hence, with $u=v(1-y)/y+u\_0$, $u$ is a function of $v$ monotonically increasing onto $\[u\_0,u\_1\]$ when $v\in\[0,1\]$.

Thus, considering $h$ and $k$ as functions of $v$ we have $h\_v=2y(v(1-y)/y+u\_0)$ and $k\_v=2y(1-(v(1-y)/y+u\_0))$, with $u\_0=1-1/(2y)$

Simplifying we get $h\_v=2y-1+2v(1-y)$ and $k\_v=1-2v(1-y)$, for $v\in\[0,1\]$

From here on the reasonning is the same as for the first case, since monotonically increasing functions are closed under composition, the variable being $v$ rather than $u$, considering the function: $D(v)=H^{-1}(h\_v)-K^{-1}(k\_v)=H^{-1}(2y-1+2v(1-y))-K^{-1}(1-2v(1-y))$

I hope that there is no error in symbol manipulations, but the line of reasonning should not be affected if that were the case.

The proof can be simplified by using a lemma that generalizes the question A, which is here a hypothesis, to any strictly increasing function from any closed interval to any other closed interval.
> 1 votes

---
Tags: complexity-theory, oracle-machines
---


title: Can I use ellipses in first order logic

text:
# Question
Title: Can I use ellipses in first order logic
I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is:

$$ \forall x \\; \exists y\_1, y\_2, \dots , y\_{n-1} \\; (x \neq y\_1) \land (x \neq y\_2) \land \dots \land (x \neq y\_{n-1})$$

I'm not sure if this is a valid first-order logic sentence or not.

# Answer
> 10 votes
Strictly speaking, your statement is invalid because $\ldots$ is not part of the syntax of first-order logic. However, your statement is an *abbreviation* of a statement in first-order logic. For example, when $n = 3$, your statement is an abbreviation of the bona fide statement $$ \forall x, \exists y\_1, y\_2 (x \neq y\_1) \land (x \neq y\_2). $$ As long as you understand this difference, you can use the statement. Your statement is stated in the *metalanguage*, and it corresponds to a bona fide statement of the *language*.

Here is a similar example. The following defines a number, for every integer $n \geq 1$: $$ \overbrace{11\cdots 1}^{\text{$n$ times}} $$ For example, when $n = 5$, this number is $11111$. While the notation above, which belongs to the metalanguage, is not in itself a valid number, for every specific $n$ it satisfies a valid number. You can think of it as a *pattern*, a *number scheme* (in your case, a *statement scheme*), or a function that takes $n$ and outputs a number (in your case, a statement).

That said, your statement (for every $n \> 1$) states that there are at least two different objects in the universe. So while it is a valid statement, it doesn't state what you intended it to.

# Answer
> 5 votes
### Short answer

Yes, you can use ellipses, as long as it is absolutely clear what they mean. In the example in your question, it is absolutely clear what the ellipses mean.

**Note.** The formula does not, in fact, express the property that the domain has exactly $n$ elements but this is a side-issue: your question was explicitly about the use of ellipses.

### Long answer

**Question 1.** Is $\\{1, \dots, 10\\}$ a set of natural numbers?

Interpreting the question literally, the answer is no. A set of natural numbers is a set all of whose elements are natural numbers. The elements of this set are one, ten, and dot-dot-dot: only the first two of those are natural numbers.1 But we can all, I think, agree that $\\{1, \dots, 10\\}$ *represents* a set of natural numbers: specifically, the set $\\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\\}$. The ellipsis isn't an element of the set: it's a short-hand we use when writing about sets. Everybody knows that it means "fill in the gap using the obvious pattern" and we've been conditioned to find intervals of the natural numbers obvious.2 Speaking a little more formally, the ellipsis is part of the *metalanguage*: the language we use to write down, describe and talk about sets.

**Question 2.** Is $\\{1, \dots, n\\}$ a set of natural numbers?

Literally, no. Neither dot-dot-dot nor the letter $n$ is a natural number. We've already discussed what the ellipsis is but what is $n$? $n$ is some kind of variable: it stands for something. We'd better restrict it to stand for a natural number because whatever $\\{1, \dots, \sqrt{2}\\}$ might mean, it certainly isn't a set of natural numbers. However, for every natural number $n$, $\\{1, \dots, n\\}$ represents a set of natural numbers.

**Question 3.** Let $\varphi\_n\equiv \forall x \exists y\_1 \cdots \exists y\_{n-1}\\,(x\neq y\_1)\land \dots \land (x\neq y\_{n-1})$. Is $\phi\_n$ a formula of first-order logic?

OK, you know the drill by now. Literally no but, for any fixed natural number $n$, $\varphi\_n$ is a formula. Now, at this point, I'd like to take issue with either the exercise you were set or your summary of what it says. There is no formula of first-order logic that says "The domain has exactly $n$ elements." Why? Because, as stated, $n$ is a free variable of the formula. It turns out that, even if your domain contains some encoding of the natural numbers, there is no formula you can write of the form $\psi(S,n)$ that is true if, and only if, $|S|=n$.3 What you *can* do is write a family of sentences $\varphi\_1, \varphi\_2, \dots$ such that, for each $n$, $\varphi\_n$ is true if, and only if, the domain contains exactly $n$ elements.

Here, $n$ is a variable in the metalanguage and you might have noticed a pattern: I'm quibbling with statements in which it's a free variable of the metalanguage and guiding towards statements where it's bound. It doesn't make sense to talk about $\varphi\_n$ in isolation, but only in a context where $n$ is defined. You're not really "writing down $\varphi\_n$" but, rather, giving a recipe that lets your reader figure out what $\varphi\_n$ is once they've decided what $n$ is.

So, to summarize, ellipses (and $n$s and so on) are not literally part of first-order logic. They're tools in the metalanguage that allow you to describe formulas. In the example I gave above, each of $\varphi\_1$, $\varphi\_2$, $\varphi\_{2376}$ etc. is a formula that can, in principal, be written down without ellipses. However, $\varphi\_n$ isn't literally a formula: it's sort of a recipe for writing down a formula once you've decided on a value for $n$. It describes a family of formulas with increasing numbers of variables and increasing quantifier depth. As such, it's not going to be possible to write down the "recipe" for such a family without using metalanguage devices such as ellipses.

---

1 Let's just agree that $1$ *is* a natural number, rather than being just a representation of some intrinsic concept of "one-ness". Philosophical logic worries about such things; mathematical logic doesn't.

2 Note that this is very much a human construct. There is no unique way of filling in the ellipsis in $\\{1, \dots, 10\\}$. I might be a jerk who's written that for the set of roots of the polynomial $(x-1)(x-3)(x-7)(x-10)$ but you, and all reasonable readers, assume I'm not a jerk (thanks! I appreciate that) and that I meant $\\{i\in\mathbb{N}\mid 1\leq i\leq 10\\}$.

3 This can be proven by various means, such as Ehrenfeucht–Fraïssé games or, as I recall, compactness.

# Answer
> 4 votes
Assuming you work with the usual definition of FOL, no, that iss *not* a syntactically valid formula. "$\dots$" does not appear in the formal grammar specifying the language.

However, "$\dots$" is commonly and implicitly accepted as a shorthand. As long as it is clear how to fill the gap with finitely many symbols, it is for many purposes¹ fair to save ink and time. This is to say that there is a reasonable extension to the formal language that is FOL *and* its semantics that would make such formulae valid. For instance, one could say

$\qquad\displaystyle \exists\\, y\_{\[a..b\]} : \varphi$

is a FOL formula if $\varphi$ is, and $1 \leq a \leq b$ natural numbers. We can easily define the semantics by noting that

$\qquad \exists\\, y\_{\[a..b\]} : \varphi \equiv \begin{cases} \exists\\, y\_b : \varphi, & a=b;\\ \exists\\, y\_a : \exists\\,y\_{\[a+1..b\]} : \varphi, & a \< b. \end{cases}$

Note that we implemented "$\dots$" by recursion, and that the "unfolded" formula for any $a$ and $b$ is a FOL formula by the usual definition.

Keep in mind that this only works for *fixed* $\[a..b\]$, or in your case, fixed $N$. If it's not fixed, then you implicitly say

$\qquad\displaystyle \exists\\,A \subseteq \mathbb{N} : \exists\\,y\_A : \varphi$.

Here you quantify over sets, and that is *not* within the power of FOL.

---

1. Not always: if you work with a proof assistant or any other automated system, you probably don't get to do this without rigorously defining all your shorthands.

# Answer
> 0 votes
Your question was: find a first-order logic sentence stating that there are exactly $n$ objects in the universe. The following formula should work: $$ \exists x\_1\ ... \exists x\_n\ \Bigl(\bigwedge\_{1 \leqslant i \< j \leqslant n} \neg(x\_i = x\_j)\Bigr) \wedge \forall x \ \Bigl(\bigvee\_{1 \leqslant i \leqslant n} (x = x\_i)\Bigr) $$ Intuitively, the first part of the sentence says that there exist at least $n$ distinct elements and the second part says there is no more than $n$ elements.

---
Tags: logic, first-order-logic, notation
---


# Question
Title: Can polymorphism be simulated by lazy type operators?
In the definition of lambda cubes, type polymorphism is distinguished from type operators/constructors.

I have the nagging feeling that type polymorphism can be constructed through type operators using lazyness. This may be extremely convoluted but I always felt polymorphic types where just functioning "as if" waiting for a concrete type.

Here's an example...

Take `(+1)::Num a => a -> a`, `(+1) pi` is `Floating` whilst `(+1) 1.1` is `Fractional`.

This level of polymorphism above can be constructed through the use of a "universal delayed type constructor" `F` and a type operator `G` designed for `(+1)`. Where,

`F :: X -> f -> a -> X a`

I've tried to upper case type signatures to represent types and lower case for terms.

And where, `G :: a -> B
G ( _ ::Integral) = Integral
G ( _ ::Fractional) = Fractional
G ( _ ::Floating) = Floating`

Note that G's implementation is partial, I've not actually said how `(+1)::Floating -> Floating`  is implemented differently from `(+1)::Integral -> Integral` .

Therefore, `F G (+1)` achieves the same as `(+1)` with polymorphism above. This is a simple example, I may need to go a second level (i.e. operators on type operators) to simulate polymorphic type operators.

So, is true that polymorphism can be simulated by type operators? I'm probably wrong but I don't understand why. Can anyone help?

\[EDIT\]

My question was ill-posed. I didn't have the concept quite formed in my mind. It actually was triggered by Pierce's comment

> when a polymorphic function meets a type argument, the type is actually substituted into the body of the function.

Based on that, polymorphic functions felt very close to type operators: type operators work on types, polymorphic functions crystalize into proper functions when given a type. I felt that polymorphic types could be replaced by some kind of (recursive) type operator that "fetched" the proper type. I forgot however that polymorphic types have kind $\*$ whilst type operators have kind $\* \rightarrow \*$. So that's at least one difference.

# Answer
> 1 votes
It's not entirely clear to me how your idea is supposed to work, but everything you're doing can just simply be done with a bit of more high-powered type theory. That is, if we allow quantification over types then we can talk about polymorphism. Let's go from easy examples to the ones you're talking about.

A function such as $$f \\, x = (x,x)$$ is polymorphic in the type of $x$: if $x$ has type $A$ then $f$ has type $A \to A \times A$. We can express this sort of dependency by intrducing an extra argument so that $f$ has type $\prod\_{A : \mathsf{Type}} A \to A \times A$ and is defined by $$f \\, A \\, x = (x, x).$$

Your example is like this, except a bit more complicated. To keep examples simple, let me instead used a simplified class (the whole `Num` is a bit large)

```
class Cow a where
  one :: a
  plus :: a -> a -> a

```

and consider a functio dependent on `Cow`:

```
plusOne :: Cow a => a -> a
plusOne x = plus x one

```

We can express `plusOne` as before, except that now it takes *three* extra parameters: a type $A$, an element of $A$, and a function $A \to A \to A$. So its type would be $$ \prod\_{A : \mathsf{Type}} A \to (A \to A \to A) \to A \to A $$ and it would be defined by $$\mathtt{plusOne} \\; A \\; \mathtt{one} \\; \mathtt{plus} \\; x = \mathtt{plus} \\; x \\; \mathtt{one}.$$ This is a general trick: polymorphism can always be replaced by passing around extra arguments, but the price you pay is that you will have *dependent* types and there might be many extra arguments.

---
Tags: lambda-calculus, type-theory, types-and-programming-languages
---


title: Why have a numeric type hierarchy?

text:
# Question
Title: Why have a numeric type hierarchy?
The more I think about it, the stranger the concept of having a `number` type, which is a super-type of integers, rationals and reals seems to be. One thing that comes to mind is the Wittgenstein's concept of class families (where objects are grouped into families, even though neither one is a sub-type of the other, but have some "common property", not necessarily common to all objects in the family). Certainly, not a *hierarchy*.

And yet, in languages like Java, Common Lisp, Haskell and possibly lots of others there is a concept of a numerical super-type for types like integers, reals, complex etc.

Is there any computer-science-related explanation of existence of such super-type, or is this simply a convenience, which has no deeper meaning?

# Answer
> 2 votes
To some extent it's a convenience. Not all languages have the hierachy you speak of. For instance Ocaml has no such hierarchy and you need to explicitly cast integers to floats. (This is the price you pay for having type inference with principal types in Ocaml.)

But there are other reasons as well. Numeric types are there because we want to do *math* with computers. In mathematics there are many kinds of numbers, and they are naturally organized according to what structure they carry: the integers form a ring, the rationals form a field, the reals form a complete field, and the complex numbers a complete algebraically closed field. So the *mathematical hierarchy* gets reflected in the organization of numeric types.

In Haskell there are a number of numeric type classes (`Num`, `Float`, `Rational`, ...) which give the programmer flexibility and modularity. In Haskell it is very easy to switch from one kind of `Num` to another – as opposed to other software systems where it takes years to switch the numeric data types (consider how big a project it was from 32-bit to 64-bit Windows).

# Answer
> 0 votes
If you want to simply have a "number" type, then the compiler (or JIT) would need to prove that a type must be within bounds for a 32-bit integer to use an efficient 32-bit integer representation that the CPU supports, etc. So on one hand, it's an optimization to use machine types. On the other, the types declared can be thought of as assertions on declared variable types (particularly on inputs). Some languages force explicit casts for assignments that will surely lose information (float assign to int).

If you are using float32 instead of int32, the operations (including addition) will no longer be exact.

---
Tags: type-theory
---


# Question
Title: What do we gain by having "dependent types"?
I thought I understood dependent typing (DT) properly, but the answer to this question: https://cstheory.stackexchange.com/questions/30651/why-was-there-a-need-for-martin-l%C3%B6f-to-create-intuitionistic-type-theory has had me thinking otherwise.

After reading up on DT and trying to understand what they are, I'm trying to wonder, what do we gain by this notion of DTs? They seem to be more flexible and powerful than simply typed lambda calculus (STLC), although I can't understand "how/why" exactly.

What is that we can do with DTs that cannot be done with STLC? Seems like adding DTs makes the theory more complicated, but what's the benefit?

From the answer to the above question:

> Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from propositional to first-order logic.

This seems to make sense at some level, but I'm still unable to grasp the big-picture of "how/why"? Maybe an example explicitly show this extension of the C-H correspondence to FO logic could help hit the point home in understanding what is the big deal with DTs? I'm not sure I comprehend this as well I ought to.

# Answer
> 22 votes
Expanding my comment: Dependent types can type more programs. "More" simply means that the set of programs typable with dependent types is a proper superset of the programs typable in the simply-typed $\lambda$-calculus (STLC). An example would be $List\_{2\*3+4}(\alpha)$, the lists of length $10$, carrying elements of type $\alpha$. The expression $2\*3+4$ is at the same time a program and part of a type. You cannot do this in the STLC.

The key rule that distinguishes dependent from non-dependent types is application:

$$ \newcommand{\TYPES}\[3\]{#1 \vdash #2 : #3} \newcommand{\SUBST}\[2\]{\\{#1/#2\\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} } $$

On the left you have the STLC, where programs in the premises 'flow' only into the program of the conclusion. In contrast, in the dependent application rule on the right, the program $N$ from the right premise 'flows' into the *type* in the conclusion$^1$.

In order to be able to parameterise types by programs, the syntax of dependent types must be richer, and to ensure that types are well-formed we use a second 'typing system' called kinds that constrains the types. This kinding system is essentially the STLC, but "one level up".

There are many explanations of dependent types. Some examples.

---

$^1$ In terms of colours: with non-dependent types, black expressions in the conclusion are constructed from black expressions in the premises while red expressions in the conclusion are constructed from red expressions in the premises. With dependent types the colours can be mixed by having black parts of the conclusion being constructed from red and black parts of the premise.

# Answer
> 1 votes
Think of type declarations as nothing more than assertions. Currently, all you can say is things like isInt32(), isCharPtr(), etc. These various assertions are chosen to be checkable at compile-time. But this concept can be expanded to things like: isCharPtr() && isNotNull(). Nullable pointers are a huge problem. Pointers should not be nullable as the default stance, with nullable pointers being a type that isn't dereferenceable without knowing whether it is null or not. Similar problems are things like: isPositiveInteger(), or isEvenNaturalNumber().

---
Tags: logic, type-theory, intuition
---


title: What exactly is a hash function?

text:
# Question
Title: What exactly is a hash function?
I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, and here's what I get:

* hash tables are nice because the index can be stored in a smaller array
* hash functions are kind of like uniform random number generators that always have the same seed but not really (and I don't get why)

But here are the parts that are still very ambiguous to me:

* Why use a hash function and not an RNG with a set seed and array size?
* Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?
* Why do we mod with array size at the end? Can't we just restrict the range of the hash function?
* what is the difference between a hash table and a pointer?
* If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?
* in the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?

Thanks for any insight!

# Answer
> 5 votes
A hash function is a pseudorandom function with a constant range. Ideally, one would like two central properties:

1. The hash function should be easy (fast) to compute.
2. The probability that two inputs $x,y$ hash to the same value is roughly $2^{-n}$, where $n$ is the output length.

The second property isn't stated rigorously. There are several ways to state it rigorously:

1. We can consider an *ensemble* (collection) of hash functions, and then the probability is over the choice of the hash function.
2. We can consider some distribution on pairs $x,y$.

The main difference between hash functions and pseudorandom number generators is that a hash function gives a unique value for each input. This is important for applications such as hash tables and message verification:

1. In hash tables, a hash function is used to choose the location at which an input is put. When you search for the same input, it is important that the hash function puts you in the same location. The pseudorandom property ensures that none of the cells gets to keep too many elements.
2. In message verification, you are sent separately a message and its hash, and you verify the integrity of the message by comparing its hash to the one given to you. Here the pseudorandom property ensures that it is hard to cheat.

---

Now to address your specific questions:

*Why use a hash function and not an RNG with a set seed and array size?*

A hash function has the property that each input is hashed to the same value, which is important in some applications (see above).

One way to guarantee the pseudorandom property is to have an ensemble of pseudorandom functions, and choose one at random; this is like choosing a seed at random. In practice, the seed is chosen at random once and for all, since this simplifies things.

Choosing the random seed ahead of time is OK for many applications. The main drawback is that the adversary gets to see the seed ahead of time, and can use this knowledge to try to cheat. When the hash function is easy to "break", this can actually cause problems. For example, it can allow Denial of Service attacks by sending some server some data which is all hashed to the same index, thus slowing things.

In settings when there is no adversary (say, a hash table used in your own program), a hash function with a fixed seed doesn't suffer from this drawback.

*Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?*

Collisions are unavoidable, unless you know the input ahead of time. Indeed, if you have more potential inputs than possible outputs (which is usually the case for hash functions), then collisions are bound to occur.

Consider the idealized hash function in which the hash of any given input is chosen completely randomly (but is fixed); such a function is not efficiently computable, but otherwise is an excellent hash function. Even such a function will have collisions. The goal in constructing a hash function is to imitate this behavior while keeping the function easily computable.

*Why do we mod with array size at the end? Can't we just restrict the range of the hash function?*

You don't want to construct a specialized hash function for each array size. Rather, you obtain such a hash function by taking a canonical hash function and then modding with the array size.

Another way to look at it is that you *are* restricting the range of the hash function. You constructed your hash function with restricted range by taking a canonical hash function and reducing its output modulo the array size.

*What is the difference between a hash table and a pointer?*

A hash table is a data structure for storing *entries* (whatever they are), supporting operations such as insertion, deletion, and lookup. This is rather different from a pointer.

*If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?*

Even if you know the number of unique keys in advance, you don't necessarily know what they are, and without this information you can't use direct addressing.

Even if you did have a list of unique keys in advance, it is not always easy to construct an efficient direct addressing scheme. Imagine that the input is the set of all binary trees on at most 20 vertices. How do you map such a binary tree to an integer? While such schemes are definitely possible, often it is faster to use a hash function; the overhead due to collisions is negligible compared to the cost of computing a direct addressing scheme.

*In the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?*

If you don't know ahead of time how many unique keys you have, then you use a dynamic hash table instead of a static one. A dynamic hash table can grow in size, though this is an expensive operation. The hash table is initialized at some fixed size, and once it gets too full, it grows in size; if it gets too empty, it shrinks. For an example, look up the Python implementation of dictionaries (dictionaries are the python name for hash tables).

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


# Question
Title: Can a recursive language be uncountable?
Does there exist a recursive language $L$ whose cardinality is uncountable?

I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to reject the initial question.

# Answer
Languages are collections of words. Words are finite strings.

As Shaull stated in his comment, *every* language over a finite alphabet is countable. (In fact, every language over a *countable* alphabet is also countable.)

Languages of infinite words, sometimes called $\omega$-languages, are considered in computer science. For example, they are the subject of $\omega$-automata theory. But the Turing machine formalism is about the usual notion of language.
> 5 votes

---
Tags: formal-languages, computability, uncountability
---


# Question
Title: Can I encode a graph in a unary alphabet
For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly.

Now, imagine the alphabet I am given is $\Sigma=\\{1\\}$, is there a way for me to encode any graph instance with such alphabet?

In my reasoning, I think you can, since if you can map any binary string, to a unary string, then you can transitively mapping one adjacency matrix to a unary string, hence a graph. Does this reasoning have any flaw? Is this a valid argument?

# Answer
As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say $$ \epsilon, 0, 1, 00, 01, 10, 11, \ldots. $$ Let $w\_i$ be the $i$th string in this order. You can convert from binary to unary by mapping $w\_i$ to $1^i$ and vice versa.

You mention that you are worried that this encoding is not efficient. From the perspective of complexity theory, this is not so clear, since if your representation is very large, then it is fair to allow you a lot of time to encode and decode it. In formal terms, for a representation of length $n$, you should be able to encode and decode in time polynomial in $n$.

Consider the example of graphs. In order to encode a graph in unary, you first encode it in binary, say using $m$ bits. Then you output $1^n$ for some $n \approx 2^m$. You can easily compute the output in time polynomial in $n$. Going the other way around, you can convert $1^n$ to the corresponding binary string $w\_n$ in time polynomial in $n$ as well, and decoding the binary representation only takes time polynomial in $m = O(\log n)$.
> 5 votes

---
Tags: turing-machines, encoding-scheme
---


# Question
Title: How to build a label flow graph for static analysis
I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler.

I've started with the build of the graph of the constraints of the program: The edges represent the flow of data through the program (according to the statements or function calls) and the nodes the run-time memory locations.

I'm wondering if for the labeling of the constraints I do need a symbol table with all the constraints and their labels. I found out that we can build a CFG on top of the LLVM by only parsing the LLVM IR.

for example, we could just have:

```
//Build list nodes without successors.
for (Function::iterator e = F.end() ; e != BB ; ++BB) {
    BI = BB->begin();
    for(BasicBlock::iterator BE = BB->end(); BI != BE; ++BI){
        Instruction * instruction = dyn_cast<Instruction>(BI);
        StaticAnalysis::ListNode* node = new StaticAnalysis::ListNode(counter++);
        node->inst = instruction;
        helper.insert(pair<Instruction*,StaticAnalysis::ListNode*>(instruction,node));
        CFGNodes.push_back(node);
    }
}

```

So, my question is: Would this be possible also for a flow graph? Or a symbol table is needed to construct one?

# Answer
> 1 votes
You want to build a graph where the vertices are the set of runtime locations in memory. Unfortunately, this isn't possible. The set of runtime locations can be an unbounded set.

For instance, consider code that creates a linked list to hold $n$ data items provided on the input; the number of memory locations is at least $n$, so if the data items are provided on the input, there is no upper bound on the number of memory locations. Or, consider code like

```
while (...) {
    char *p = malloc(..);
    ... do something with p ...
    free(p);
}

```

Each call to `malloc()` creates a new memory location, so the number of runtime memory locations is at least the number of iterations of the loop. There may be no fixed upper bound on the possible number of iterations of the loop.

Different static analysis techniques deal with this in different ways:

* Data flow analysis typically deals with this by ignoring everything in the heap, and only trying to reason about local variables. In this way, you obtain a finite graph.
* Points-to analysis deals with this using abstraction. It builds a points-to graph, where each node in the graph corresponds to a potentially unbounded number of runtime memory locations. At each node in the graph, we record facts that are known to be true for all of the runtime memory locations that correspond to that node. For instance, we might have one node per `malloc()` call site. In other words, we might have a single node for all runtime memory locations that are allocated by any of the calls to `malloc()` on line 79 (the first call to `malloc()` on that line, the second call to `malloc()` on that line, etc.; they're all merged into a single node).

You might want to spend some time reading up on how data flow analysis and points-to analysis work.

More generally, I suggest you ask a new question where you tell us what you're trying to achieve. Presumably the graph you were talking about was only a means to an end; what was the end goal? Presumably you wanted to build it only because you thought it'd help you with some task; what is it you really want to learn about the program? If you ask a new question telling us what your goal is (what you're trying to infer about the program), we might be able to suggest an appropriate static analysis technique that would be suitable for that goal.

---
Tags: graphs, compilers, static-analysis
---