# Question
Title: In what ways can we distinguish between a human and bot behavior?
**Updated based on comments:**

In what ways can we distinguish a human being doing certain activities online and a bot programmed to do similar activities, say checking email, downloading some music files, shopping on ebay, searching on Google etc., or maybe trying to deface/hack a website, brute force a log-in password etc.

To limit the scope of the question and make it more clear, let us restrict our observations *only* to network-oriented behavior, some examples being- the amount of time spent doing XYZ thing online, the amount/type of data downloaded (say) from a file sharing website, the number of friends/followers on Social media websites, etc.

I guess it should possible to obtain some 'patterns' which will distinguish human behavior and programmed behavior.

The Turing test is not what I am looking for.

What techniques can be useful here? Machine learning? Game theory?

References to relevant academic/research articles will also be good.

# Answer
The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA).

This kind of test is very effective{1} but falls under the HIP (Human Interactive Proofs) area: it's not transparent.

Typical, "simple" approaches to distinguish human website traffic from Bot are:

* time it takes to populate all the fields and click the submit button of an input form (frequently used but simple to bypass).

Watching the cadence / pace of the communication is a more secure alternative (this is one of the feature of Google's No CAPTCHA reCAPTCHA);
* honeypots (i.e. traps for bots that consist of a link or field present on the page that isn't visible to the human eye)
* analysis of *maximal continuous session length* (humans have to rest) and *correlation with time of day* (see Distinguishing Humans from Bots in Web Search Logs)

It must be considered that bot characteristics exhibit a wide variability for different crawler / different sites, therefore it's difficult to derive simple, deterministic heuristics: rule based systems imply a long list of static rules that are difficult to define and maintain (even by experts).

Machine learning techniques are often used:

Almost every available AI/ML "tool" has been experimented. The main problem using these supervised machine learning tools is labeling the training dataset.

Even restricting the analysis to network-oriented behavior, this is a question of tremendous scope, for this reason I'm giving some keywords for further searches.

---

**Notes**

1. Machine Learning based attacks are improving and CAPTCHAs also serves as a benchmark task for artificial intelligence technologies (e.g. The End is Nigh: Generic Solving of Text-based CAPTCHAs)

---

**Keywords**

HIP (Human Interactive Proofs), CAPTCHA, Keystroke dynamics, Keystroke cadence, typing dynamics, IDS (Intrusion Detection System), honeypot, click fraud, spambot

---

**References**
> 10 votes

---
Tags: machine-learning, artificial-intelligence, game-theory, computer-vs-human
---


# Question
Title: Turing Machine with additional finite memory of size $n$
**The question itself:**

> Let us define a generalization of Turing Machines to include a finite memory of \>size $n$.
>
> We denote such a Turing Machine formally as:
>
> $M\_{mem} = (Q, Σ, γ, δ\_{mem}, n, q\_0, q\_a, q\_r)$
>
> where all the definitions are identical to the standard Turing Machine except \>that there is the finite memory size n and the transition function δmem. At each \>step, the transition depends on the current state, the input on the tape and all the memory. The transition to the \>next step can update the entire memory.
>
> Formally: $δ\_{mem} : Q × Γ × Γ^n → Q × Γ × Γ^n × {L, R}$.
>
> Given a finite memory Turing Machine $M\_{mem}$, define $formally$ a (standard) Turing Machine $M$ such that $L(M) = L(M\_{mem})$. Namely, both Turing Machines accept the same language.

**my approach**

I am asked to give two different constructions of such a turing machine. The first way that I managed to come up with is to encode the memory into the states of the turing machine and I managed to do so. I thought that a second way to do it is to encode the memory into the tape itself by concating the string in the memory into the input char itself but this causes problems because the turing machine doesn't have access to the memory in such a way because it will write down the encoding and then move left or right so it won't see the encoding of the memory no more. please guide me with the second approach and/or suggest me another way to do it.

# Answer
> 3 votes
I don't think that you can "embed" the extra memory into the alphabet and "carry" it with the head moving around without a $|Q|$ blow-up (blow-up comparable to the one of approach 1).

So a (**weird!**) approach *to keep the size of $|Q|$ low*, that can work is the following:

* embed both the extra memory and $Q$ into the alphabet $\Gamma\_M = \\{H,h\\} \times Q \times \Gamma \times \Gamma^n$
* use only ONE cell (marked with embedded symbol $H$) to represent the current state of $M\_{mem}$ + symbol under its head + the content of the extra-memory
* use some additional states to SHIFT the tape around the cell $H$

Very informally you have:

```
                  q1
                  S
....0 1  1 1 0 0 [0] 1 1 0 0 0 ...
    h h  h h h h  H  h h h h h
                  ^
                  q_sim

```

In this condition, the (standard) Turing machine $M$ is on state $q\_{sim}$ and is on symbol $\langle H,q\_1,0,S \rangle$ that represents: head of $M\_{mem}$ is on state $q1$, reading a $0$ and the content of the extra memory is $S$

Now if $M\_{mem}$ writes a 1, writes $S'$ on the extra memory, moves $L$eft and enters $q\_2$; the standard $M$ on state $q\_{sim}$ writes $\langle H,q\_2,1,S' \rangle$ and enters a sequence of states $q\_{r\_1},...,q\_{r\_k}$ that shift the whole tape one cell to the right and returns back on the cell marked with $H$ and state $q\_{sim}$; simulating in this way the movement of the $M\_{mem}$'s head:

```
                  q2
                  S'
....  0 1  1 1 0 [0] 1 1 1 0 0 0 ... << tape shifted right
      h h  h h h  H  h h h h h h
                  ^
                  q_sim

```

Note that the standard $M$ simulates $M\_{mem}$ transitions using only a single state $q\_{sim}$ (plus two extra-states for accept/reject).

Also note that the symbol corresponding to the extra memory $S'$ is NOT MOVED, so the total number of states of $Q\_M$ required to shift the "underlying" tape (simulating the move of the head of $M\_{mem}$) depends only on $\Gamma$, not on $n$:

$\Gamma\_M = \\{H, h\\} \times Q \times \Gamma \times \Gamma^n $

$\delta\_M = Q\_M \times \Gamma\_M \to Q\_M \times \Gamma\_M \times \\{L,R\\}$

and $|Q\_M| = k |\Gamma|+c$

You can also choose to embed the states of $M\_{mem}$ into $Q\_M$: in this case the alphabet is: $\Gamma\_M = \\{H, h\\} \times \Gamma \times \Gamma^n $, but you must use more states: $|Q\_M| = k |Q| |\Gamma|+c$

The above construction can also be generalized to standard Turing machines and (very informally) it roughly represents a switch from:

$\delta : Q \times \Gamma \to Q \times \Gamma \times \\{L,R\\}$ to

$\delta : \Gamma \times Q \to \Gamma \times Q \times \\{L,R\\}$

---
Tags: turing-machines, computation-models, simulation
---


# Question
Title: What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?
Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A\[1\],\dots,A\[n\]$ are all distinct. What is a fast way to find a partition $A\_1,\dots,A\_k$ of $A$ with $|A\_i| = m$ for all $i$, such that $x\<y$, if $x\in A\_i$ and $y\in A\_j$ with $1\leq i\<j$?

I have the following rough idea:

1. find the $i\cdot m$-th order statistic for $i = 1,\dots, k$ and put them into an (automatically) ordered list $\operatorname{pvt}$
2. iterate through the elements of $A$ and find for every such element (via binary search) the corresponding interval in $\operatorname{pvt}$ and insert it into the corresponding $A\_i$

The first step can be done in $O(nk)$ (finding the $l$-th order statistic can be done in $O(n)$) and the second step in $O(n\log k)$, giving us $O(nk)$ in total.

Is there an obvious faster algorithm? (provided this idea works at all)

# Answer
You can do $O(n \log k)$ by finding $mk/2$-order statistic, partitioning the array into two parts of size $mk/2$ and recursing on each side until $k = 1$. You get the recurrence on running time $T(m, k) = 2 T(m,k/2) + \Theta(m k)$ and $T(m, 1) = \Theta(1)$, which solves to $T(m,k) = O(m k \log k) = O(n \log k)$.
> 3 votes

# Answer
What you're describing is similar to the first phase of Samplesort. Counting takes $O(n log k)$, not $O(nk)$. If you want to do the permutation in-place you can look at Cycle Sort; doing it out of place is simpler. Either way that part is $O(n)$.

The number of permutations of a k-way split is ${n!}/{(m!)^k}$, so if we take the log we get $\Omega(n \log k)$ comparisons after a bit of algebra. So there's no faster comparison-based algorithm.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Introductory book on Logic and Computation
Can you give me some suggestions about a good introductory (but comprehensive) book
about Logic and Computation?

Some fuzzy topics that I have in mind are:

* Presburger artihm., PA, ZF, ZFC, HOL
* Set theory, Type theory
* Modeling Computation (Turing machines) in different theories
* Links with computational complexity (FMT, descriptive complexity)

# Answer
I suggest one of the book I recently bought:

Pavel Pudlak: Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction; Springer Monographs in Mathematics; 2013

I had not ("still haven't" :-) a strong background on logic and this book is helping me to better understand some "fundamental" aspects of logic and its relation with computation and complexity. Doubtless a good introductory book.

The TOC and preface of the book are downloadable from the Pudlak's home page and you can also find some excerpts of the book on http://books.google.com.

From the **Introduction**:

> ... The first two chapters are an introduction to the foundations of mathematics and mathematical logic. The material is explained very informally and more detailed presentation is deferred to later chapters....
> Chapter 3 is devoted to set theory, which is the most important part of the foundations of mathematics. The two main themes in this chapter are: (1) higher infinities as a source of powerful axioms, and (2) alternative axioms, such as the Axiom of Determinacy...
> Proofs of impossibility, the topic of Chapter 4, are proofs that certain tasks are impossible, contrary to the original intuition. Nowadays we tend to equate impossibility with unprovability and non-computability, which is a rather narrow view. Therefore, it is worth recalling that the first important impossibility results were obtained in different contexts: geometry and algebra. The most important result presented in this chapter is the Incompleteness Theorem of Kurt Godel...
> Proofs of impossibility are, clearly, important in foundations. One field in which the most basic problems are about proving impossibility is computational complexity theory, the topic of Chapter 5. But there are more connections between computational complexity and the foundations....
> In fact, there is a field of research that studies connections between computational complexity and logic. It is called ‘Proof Complexity’ and it is presented in Chapter 6. Although we do have indications that complexity should play a relevant role in the foundations, we do not have any results proving this connection. ...
> Every book about the foundations of mathematics should mention the basic philosophical approaches to the foundations of mathematics. I also do it in Chapter 7, but as I am not a philosopher, the main part of the chapter rather concentrates on mathematical results and problems that are at the border of mathematics and philosophy ...

It doesn't cover FMT and descriptive complexity, but there are a few good books that are focused on those topics (e.g. Leonid Libkin: Elements of Finite Model Theory; Texts in Theoretical Computer Science. An EATCS Series; 2004 )

I accept my answer because I hadn't the opportunity to read the book suggested by Trung Ta, yet.
> 4 votes

# Answer
My answer could be late for this question, but I hope it will be helpful for other people looking for similar information.

I had taken a course about Mathematical Logic at National University of Singapore, in which the lecturer used this textbook:

**A Concise Introduction to Mathematical Logic, 3rd edition, by Wolfgang Rautenberg**

Personally, I like both the textbook and the course a lot.

The textbook initially appears to be quite difficult to read. However, once getting familiar with it, it is much easier to follow since the system of notation is very clear, the content is self-contained and the approach is by starting from foundation, no vague assumption. For example, this book develops the natural deduction calculus and Hilbert calculus, or prove two incompleteness theorems of Kurt Gödel from scratch.
> 7 votes

# Answer
I like Tom Stuart's book "Understanding computation" with respect to modeling computation. He offers a nice progressive overview of models for computation. If I recall correctly: \- deterministic finite-state machines \- non-deterministic FSM \- FSM with a stack (deterministic and non-deterministic) \- Turing machines (with a tape)

It's pretty interactive and hands-on as he simultaneously builds a simple implementation of each model in Ruby.
> 2 votes

---
Tags: reference-request, logic, books
---


# Question
Title: KD-Tree implementation with lat/lon coordinates
I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use euclidean distance instead ?

If not, can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ?

# Answer
> 5 votes
Short answer: No, you will not get the same results.

It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into rectangle and save all data (angles and distances) at the same time.
Haversine formula is prepared to operate on circles, 3D distance on sphere, while Euclidean distance will treat them as 2D points, so the result must differ.

Haversine is one of methods to get actual distance on sphere, to use it on Earth, it is only approximation so in such case I would suggest Vincenty formula.

The errors depend on coordinates given and the distance between points.

Take reference point $A =\\{40^{\circ}N, 40^{\circ}E\\} = \\{40, 40\\}$, $B =\\{42^{\circ}N, 40^{\circ}E\\} = \\{42, 40\\}$, $C =\\{40^{\circ}N, 42^{\circ}E\\} = \\{40, 42\\}$, treating them as $X, Y$ tells that they are equidistant - this is how Euclidean distance would see raw coordinates.

According to Haversine formula distance from $A$ to $B$ is ~$222.4 km$ (~$222,108 km$ *Vincenty*), distance from $A$ to $C$ is ~$170.4 km$ (~$170,784 km$ *Vincenty*), so it kinda fails.

The idea with ruler on the map, this gets heavy, it will fail as the above, but it depends on map projection (errors change, some projections save angles, some tries to save distances).

---
Tags: algorithms, binary-trees, search-trees
---


# Question
Title: IS Array of Positive Integers Always 'Equalizable' With This Strategy?
A little bit of history first. I have asked this question here some days ago. Quoting from there:

> An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\\{2,2,3,7\\}$ and $D=\\{1,2,5\\}$ we can equalize $A$ in two steps, first adding $A=\\{5,5,5,0\\}$ to get $A=\\{7,7,8,7\\}$ and then adding $\\{1,1,0,1\\}$ to get $A=\\{8,8,8,8\\}$.

If $A$ has just two elements, this reduces to something like a change-making problem. If $\Delta=min(A\[0\],A\[1\])$, if I can make change for $\Delta$ using only the given steps from $D=\\{1,2,5\\}$, I can equalize the array by holding the larger element constant while incrementing the smaller element by the same values that I used to make change for $\Delta$. However,if it's not possible to make change for delta, it's not clear if the two elements can converge two some larger value following this strategy.

I would like to know if this strategy of withholding one element and incrementing the rest by a chosen 'delta' will always make all elements equal in some finite number of steps.

# Answer
If the GCD of the array D is larger than 1, then this cannot always be done. The simplest example is $A = \\{1,2\\},D=\\{2\\}$. In contrast, if the GCD of the array D is 1, then it is known that large enough integers can be represented as positive linear combinations of elements of D. In particular, there is an integer $N$ such that $N-a$ can be represented for all $a \in A$. Summing all these representations will equalize the array.

For example, when $A = \\{2,3,7\\}$ and $D = \\{1,2,5\\}$, we can add $\\{1,0,0\\}$ once and $\\{1,1,0\\}$ four times, reflecting the representations $7-2=5 \times 1$, $7-3=4 \times 1$, $7-7 = 0 \times 1$. Even when $D = \\{2,5\\}$ this has a solution: using $11 = 3 \times 2 + 1 \times 5$, $10 = 2 \times 5$, $6 = 3 \times 2$, we can add $\\{2,0,2\\}$ three times, $\\{5,5,0\\}$ once, and $\\{0,5,0\\}$ once to get $\\{13,13,13\\}$.
> 4 votes

# Answer
Note that $A +\\{x,x,0,x\\}$ is equivalent to $A + \\{x,x,x,x\\}-\\{0,0,x,0\\}$. Since adding the same value does not affect equalization, so step is isomorphic to subtracting a value in $A$ from a number in $D$.

Furthermore, we could subtract $\min A$ from the array since this does not affect equalization either. Now equalizing the array is equivalent to bring the whole array to zero. Using your example, we have $$A\_\text{original} = \\{2,2,3,7\\} \implies A\_\text{reduced} = \\{0,0,1,5\\} $$ We use two steps `A[2] -= 1` and `A[3] -= 5` to equalize the array. Note that every step work with independent entries of $A$.

So yes equalization is the same as solving the change-making problem, and we don't need to worry about convergence between values because they are independent after the transformation.

Note that $\min A$ is not always the correct offset to subtract. For instance, the equalization problem is solvable with $A=\\{0,1\\}$ and $D=\\{3,4\\}$ but the change-making problem can be solved only with an offset of $-3$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: How similar are two DFAs? -not just binary equivalence-
Are there any measures to compute similarity (or distance) between two DFAs?

If yes, which are the main references?

I need a measure of similarity, not only a (binary) equivalence test.

"Similarity" is an intuitive concept. There are different ways to formalize it; i'm looking for ready-to-use formalizations with regard to DFAs (not NFAs, weighted automata, or general graphs!). Furthermore, good solutions may exploit recognized languages.

I found some studies about this problem, which help to clarify the question. They involve two approaches: one from model-testing field aiming at compare languages, a second defined by authors aiming at compare structure of DFAs.

* Bogdanov, Kirill, and Neil Walkinshaw. "***Computing the structural difference between state-based models.***" Reverse Engineering, 2009. WCRE'09. 16th Working Conference on. IEEE, 2009.
* Walkinshaw, Neil, Kirill Bogdanov, and Ken Johnson. "***Evaluation and comparison of inferred regular grammars.***" Grammatical Inference: Algorithms and Applications. Springer Berlin Heidelberg, 2008. 252-265.
* Walkinshaw, Neil, and Kirill Bogdanov. "***Automated comparison of state-based software models in terms of their language and structure***." ACM Transactions on Software Engineering and Methodology (TOSEM) 22.2 (2013): 13.

They compute exactly what I was looking for, a metrics among DFAs, adopting the techniques developed in the model-testing field.

Does there exist any other approaches, ready-to-use, to compute similarity between DFAs? (Both in terms of language both of structure).

# Answer
> 9 votes
This problem seems to ask for co-development of a reasonable *distance function* and an algorithm to compute it for a given pair of languages.

The paper "**The Cost of Traveling between Languages**" by *Michael Benedikt, Gabriele Puppis, and Cristian Riveros* defines one such notion, where we are searching for the largest value $d$ such that there exists a word $w$ in the language of the first automaton such that the edit distance of $w$ to any word in the second language is at least $|w| \cdot d$. The paper gives an algorithm to solve this problem, which involves distance automata.

The paper also has an interesting related work section, with a reference to the paper "**Edit-distance of weighted automata: general definitions and algorithms**" by *Mohri*, which seems to solve the same problem without the multiplication with the word length.

Both of these definitions are reasonable from a theoretical point of view - you now only have to evaluate whether they make sense for your particular application.

---

Both of the paper have author-archived versions available without pay-wall on the web which you should easily find with your favorite search engine.

# Answer
> 0 votes
I accepted the DCTLib's answer because is the best-one so far.

Here, I will add some other references that I am going to find during my researche and which satisfy the need of a ready-to-use metric/algorithm for intuitive notion of similarity between DFAs.

* Van den Bos et al. "***Enhancing Automata Learning by Log-Based Metrics***".
From abstract: \<\< *We study a general class of distance metrics for deterministic Mealy machines. \[...\] By choosing an appropriate weight function we may fine-tune our metric so that it captures some intuitive notion of quality.*\>\>

---
Tags: regular-languages, automata, reference-request, finite-automata
---


# Question
Title: Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?
$L\subseteq \\{0,1\\}^\*$

Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides the language, you can arbitrarily extend this Turing Machine (by adding redundant states), which means there are a countably infinite number of Turing Machines that semi-decide L. Does this reasoning sound right, or does the answer depend on what the language L is?

# Answer
> 5 votes
You are correct.

One can always add redundant states to obtain different Turing machines deciding (or semi deciding) the same language. This yields countably infinite Turing machines deciding $L$ (for any decidable $L\subseteq \Sigma^\*)$.

# Answer
> 0 votes
Yes; every computable function has infinitey many Turing machines that compute it. That is a fundamental property of *all* Turing-complete models/formalisms.

It is a consequence of the s-m-n theorem and (a stronger version of) Kleene's recursion theorem taken together, two properties that all Turing-complete models of computation share.

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


# Question
Title: Is the system of measuring length in the US Turing complete?
The author here writes:

> Little known fact, the system of measuring length in the US is Turing complete

My question is: **Is the system of measuring length in the US Turing complete?**

# Answer
The post you're referring to is a joke: the US (and similar British Imperial) measurement systems are not Turing complete and the claim is an example of hyperbole.

A key feature that's necessary for a system to be Turing complete is that the system must include computations that do not terminate ("infinite loops"). Although it's not clear exactly what computations can be modeled by unit conversions (or what that even means!), any unit conversion within the diagram takes a finite number of steps.
> 9 votes

---
Tags: computability, computation-models, turing-completeness
---


# Question
Title: At what point do electrical signals become actually logic and programmable language?
I get that one transistor can store a value of 1 or 0. That's not the problem. What I don't get is how the fact that a transistor represents a 0 can translate into logic? How do these transistors turn each other one or of? Is there a uniform pattern to the circuit? how do these electrical signals magically transform into mathematical equations? Is there a specific set of transistors that deal with addition? Another set for subtraction? How does the kernel transform this into programmable language? How the hell do these transistors know which pixels to colour and what to colour them with? WHAT VOODOO MAGIC IS THIS? I am pretty curious as to how this magical transformation happens, but I'm also pretty stupid, so please dumb it down a lot...

# Answer
> 1 votes
Most your questions are covered by the field of "Switching Circuits" (and more generally, "Circuits and Logic Design", which are both part of computer engineering.

Try to find a textbook on switching circuits: it will explain how to take transistors and create AND / OR / NOT gates out of them. Then find a book on logic design: it will explain how to use AND/OR/NOT gates to build more sophisticated logic primitives such as flip-flops and latches (as well as adders, subtractors, or even a CPU)

Then you will (hopefully) have more insight regarding how the low-level works to realize the high-level ideas.

---
Tags: digital-circuits
---


# Question
Title: choose minimum number of M professors in polynomial time in order to design all N course exams
Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N courses exams.

I try to hard but I only could model this question in a bipartite graph that one sections are professors and the other sections includes courses every professors are connected to every courses that they can design question for them.

we wish to choose minimum professors to cover all courses. one easy method is to check all cases and pick the minimum one in exponentioal time order...

could any one help me to solve it in polynomial time?

thanks

# Answer
It's a variant of Set cover which is Classical NP-Complete problem. Here is the problem definition.

Reduction: Take All courses as a Universal set U which you want to cover. Then make collection of sets $S=\\{P\_1,P\_2,...,P\_m\\}$ where, $P\_i$ is the set of subjects for which a professor $i$ can design a question. and you can go similarly in reverse direction.

So there is no polynomial time algorithm for your problem unless P=NP.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs
---


title: An one-sentence proof of P ⊆ NP

text:
# Question
Title: An one-sentence proof of P ⊆ NP
Recently I am reading a document \[1\]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence:

> It is trivial to show that $\mathbf{P} \subseteq \mathbf{NP}$, since for each language $L$ over $\Sigma$, if $L \in \mathbf{P}$ then we can define the polynomial-time checking relation $R \subseteq \Sigma^\* \cup \Sigma^\*$ by $$R(w, y) \Longleftrightarrow w \in L$$ for all $w, y \in \Sigma^\*$.

I know the definitions of $\mathbf{P}$ and $\mathbf{NP}$, as in \[1\], but I still can't understand this proof. Could any one explain the proof to me? Even one sentence is good.

By the way, I think $\Sigma^\* \cup \Sigma^\*$ should be $\Sigma^\* \times \Sigma^\*$. Am I right?

### Reference

\[1\] S. Cook, *The P versus NP problem*, \[Online\] http://www.claymath.org/sites/default/files/pvsnp.pdf.

# Answer
> 12 votes
Since L is in P, you can answer the word problem in polynomial time. To show that L is in NP as well, we need to provide a polynomial checking relation $R$ such that

$$ w\in L \Leftrightarrow \exists y.(|y|\le |w^k| \text{ and } R(w,y))$$

Now Prof. Cook says to take a very simple $R$. For every $w$ in $L$, no matter what $y\in \Sigma^\*$ you take, $R(w,y)$ is true and for every $w$ not in $L$, $R(w,y)$ is false, regardless of the $y$. This is a polynomial time relation, since we can decide whether $w\in L$ or not in polynomial time (since $L \in P$), without looking at $y$ at all. And as any $y$ works, there are also some $y$ that are short enough to satisfy the length restriction in the above definition.

# Answer
> 3 votes
$P=\\{L : L\ \text{is decided by a }\mathbf{deterministic}\text{ Turing machine in polynomial time}\\}$

$NP=\\{L : L\text{ is decided by a (possibly non-deterministic) Turing machine in polynomial time}\\}$

With these definitions, $P\subseteq NP$ is fairly obvious.

Let's call $\widetilde{NP}=\\{L : \text{There is some } R \text{ so that } L\_R\in P\\}$ where $R\subseteq \Sigma^\*\times \Sigma'^\*$ and $L\_R=\\{u\\#v : (u,v)\in R\\}$. The idea here is that $u$ is the "real" input and $v$ is some extra information to help us know why we should accept $u$. For example, if the problem is $SAT$, $u$ is the formula and $v$ can be a valuation.

* $\widetilde{NP}\subseteq NP$ : Guess $v$ and then verify $u\\#v$ it.
* $NP\subseteq\widetilde{NP}$ : Given $u$, $v$ will be the list transitions taken in an execution accepting $u$. To verify $u\\#v$, you just need to simulate the execution of the non-deterministic machine on $u$ while using $v$ to remove non-determinism.

The proof you're referring to is just saying that $P\subseteq \widetilde{NP}$ and you don't even need $v$ because there is no non-determinism to remove.

And yes, it should be $\Sigma^\* \times \Sigma^\*$.

---
Tags: complexity-theory, np
---


# Question
Title: Mutation and crossover operations in discrete differential evolutionary operations?
I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of vector $X$ could take the same values of other elements. My question is if we have a population of size $NP$ with each vector $X$ in the population of size $D$. How do we actually apply the mutation operand:

$$V\_{j,i}^{G+1} = X\_{j, r\_1}^{G} + F\cdot (X\_{j, r\_2}^{G}-X\_{j, r\_3}^{G})$$

where $i$, $r\_1$, $r\_2$, $r\_3$ are references to vectors in $NP$ and none is equal to the other, $J$ is an index in vector $X$, and $F$ is a random number between $0$ and $1.2$.

Suppose $X\_{r\_1}^{G}$ is equal to $\\{4, 1, 3, 2, 2, 0\\}$ and $X\_{r\_2}^{G}$ is equal to $\\{2, 2, 3, 0, 4, 2\\}$ and $X\_{r\_3}^{G}$ is equal to $\\{1, 2, 3, 3, 0, 1\\}$ Could anyone explain in detail the steps (through example if possible) on how to get the mutant vector $V\_{j,i}^{G+1}$

# Answer
There isn't a single way in which one can approach a discrete optimization problem using Differential Evolution (DE).

Widespread techniques listed under the Discrete Differential Evolution label aren't DE-specific.

You can allow variables to take values in a continuous range and use penalty functions to enforce integer values:

$$ \bar{f}(w) = f(w) - \sum\_i{k\_i \cdot (w\_i - \operatorname{round}(w\_i))^2} $$

$w$ is the vector of parameters (chromosome values), $f: \mathbb R^n \rightarrow \mathbb R$ the basic fitness function (here assuming "greater is better"), $k$ a problem-specific scaling vector, $\bar{f}(\cdot)$ the "penalized" fitness function.

In this way the DE algorithm (*DE/rand/1*) stays the same:

$$\begin{align} X\_{j,r2}^G - X\_{j,r3}^G & = \\{2,2,3,0,4,2\\} - \\{1,2,3,3,0,1\\} = \\{1,0,0,-3,4,1\\} \\ F \cdot (X\_{j,r2}^G - X\_{j,r3}^G) & = 0.5 \cdot \\{1,0,0,-3,4,1\\} = \\{0.5,0,0,-1.5,2,0.5\\} \\ V\_{j,i}^{G+1} & = \\{4,1,3,2,2,0\\} + \\{0.5,0,0,-1.5,2,0.5\\} = \\{4.5,1,3,0.5,4,0.5\\} \end{align} $$

The trial vector $U$ is obtained via crossover between the *donor vector* $V\_{j,i}^{G+1}$ and a *target vector* $X$:

$$U\_{j,i}^{G+1} = \operatorname{crossover}(V\_{j,i}^{G+1}, X\_{j,i}^{G}) $$

The *target vector* is compared with the *trial vector* and the best one is admitted to the next generation.

This is the recommended procedure with R DEOptim Package (via the optional `fnMap` parameter).

---

You can round all the real-valued parameters before evaluating the fitness function:

$$\bar{f}(w) = f(\operatorname{round}(w))$$

(`round` acts as a *repair operator*)

This is the technique used by *Mathematica*'s functions `NMinimize` / `NMaximize` with the options `Method → "DifferentialEvolution"` and `Element[w,Integers]`

---

There are also many variations of DE named *something*-Discrete-DE:

* **Binary Discrete Differential Evolution**: the solution of a problem is presented as a binary string instead of a real-valued vector
* **Real Value based Discrete Differential Evolution** introduces forward/backward transformations to map integer into real number and viceversa
* **Exchange based Discrete Differential Evolution**: here the crossover operator doesn't change but mutation, being the primary operator acting on elements of vector in continuous space, is replaced.
* ...

So you should specify what form of Discrete DE you're interested in for a step by step example.

Meanwhile A Comparative Study of Discrete Differential Evolution on Binary Constraint Satisfaction Problems by Qingyun Yang (2008 IEEE Congress on Evolutionary Computation) is a good starting point with many references.
> 1 votes

---
Tags: algorithms, optimization, heuristics, evolutionary-computing
---


# Question
Title: What is the expressive power of finite-state transducers and pushdown transducers?
One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from CFG grammars.

I am, however, unsure about this because we can construct a finite state transducer which translates a string of the form $ab$ to $\\{ a^n b^n : n \ge 1 \\}$, which is irregular.

Is this the case? If so, can anyone provide the relevant literature?

# Answer
> we can construct a finite state transducer \[that maps $\\{ab\\}$ to $\\{a^nb^n n \geq 1\\}$\].

No, we can't. REG is closed against finite-state transduction.

Wikipedia hints as much without citation; planetmath.org lists some standard references, in particular Hopcroft/Ullman.
> 1 votes

# Answer
Any string is from (the language of) a regular grammar since the language of all words is regular. Regular and context-free only make sense when you talk about entire languages.

If you take as input always the language of all words, then indeed the output will always be regular for finite state transducers and cf for pushdown transducers.

If your input can be arbitrary languages L and you just take the set

```
{v:(u,v) is in the transduction for u\in L}

```

then you can obtain arbitrarily complex languages by inputting them and just performing the identity transduction.
> 0 votes

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


# Question
Title: What is the closest result relating perfect shuffle closure of primitive words?
A perfect shuffle of two words $u=a\_{1}a\_{2} \cdots a\_{n}$ and $v=b\_{1}b\_{2} \cdots b\_{n}$ where $a\_{i}$'s and $b\_{j}$'s are letters from the alphabet $\Sigma$ is defined as $u \diamond v=a\_{1}b\_{1} \cdots a\_{n} b\_{n}$.

It is obvious that if for two primitive words $u$ and $v$, their shuffle $u \diamond v$ need not be primitive. (e.g., for $u=abc$, $v=cab$, $u \diamond v=acbacb$ is not primitive.

So, my question is is there any result that proves that under certain conditions set of all primitive words is closed under this perfect shuffle? (There are results in the literature that talks about square-free shuffle but not primitivity, at least I didn't come across any.)

Please help.

# Answer
> 1 votes
I am not aware of any result of this type. And as your example shows, the set Q of all primitive words is not closed under this operation.

You can find subsets of Q which will result only in primitive words. For example a a+ b b+. The perfect shuffles will be from a a+ (ba)+ b b+ and all of these are primitive again (though not from the original set).

The results on square-free shuffle seem to be not about the perfect shuffle, but the general case. Then they say that at least one square-free word is in the shuffle. That should be easy to show for primtive words. In your example, all resulting words are primitve except the one from the perfect shuffle.

---
Tags: word-combinatorics
---


# Question
Title: Is it possible to design a programming task that is unsolvable?
Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least one of those outputs is incorrect.

That is, the program need not terminate for all outputs, but the outputs it does generate must all be correct, and there must be an infinite number of inputs for which it will terminate.

Not too sure about this, but my intuition says that the question may be related to the Halting problem/Turing machines.

As an example, the halting problem, (as far as I understand) does not meet this requirement, as one could run the input program, and output "terminated" if it terminates. If the input program never terminates, nor does the solution, so it never generates an incorrect output.

# Answer
> 3 votes
A simplified example can be the following:

$$T( n ) = \begin{cases} \max \\{ M(n) \mid |M| \leq n \\} + 1 & \text{if such max exists}\\ 0 &\text{otherwise.} \end{cases}$$

In other words the "unprogrammable" (uncomputable) task $T$ (or better *uncomputable function* $T$) simply picks all programs $M$ of size at most $n$ as "input" and outputs the maximum value that they output on input $n$, plus 1.

Given a program $M\_i$ that satisfies your assumption ( *... which produce an answer in finite time for a (countably) infinite number of inputs ...*), there will always be an $x\_0$ such that $|M\_i| \< x\_0$ and $M\_i$ on $x\_0$ halts, and we have:

$$M\_i(x\_0) \leq \max \\{ M(x\_0) \mid |M| \leq x\_0 \\} \< T(x\_0)\\,.$$

# Answer
> 0 votes
The halting problem can be solution to your question.

You are saying that the algorithm for halting problem never terminates (or it terminates for a finite number of inputs) when the input is a "non-terminating" program. But this is not quite right. Because, you can actually devise an algorithm for halting problem that outputs "non-terminating" for some of the "non-terminating" inputs, but not all of them.

Let's say, I devise an algorithm that checks if the following code is reachable in the input program,

```
while (true):
   continue;
end-while

```

if it is reachable in an input program, the program has an infinite loop and does not terminate at all; otherwise, it may or may not terminate (I assume that this is a reachable part of program without loss of generality; there is an infinite number of programs with such reachable segment).

**Therefore, there are an infinite number of "non-terminating" input programs, for which, my algorithm can actually find out that they are not going to terminate. But my algorithm is not able to find all input programs that are "non-terminating" (which means that the problem is still undecidable).**

---
Tags: computability, undecidability
---


title: Reconciling NP and the decision problem

text:
# Question
Title: Reconciling NP and the decision problem
So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the solution of an NP problem can be checked in polynomial time?

For example, for a graph G, the max cut decision problem: "Does a cut of size at least k exist?" is NP-Complete. However, given a particular solution, "yes", the problem of *checking* that the solution is "yes" would require you to find a max cut of size k, so how can this be in NP?

# Answer
By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than an apple.

A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that:

* If $x \in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $\langle x,y \rangle \in B$.
* If $x \notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $\langle x,y \rangle \notin B$.

The string $y$ is called a *witness*.

This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $\langle G,k \rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $\langle \langle G,k \rangle, C \rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $\langle G,k \rangle$.

As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent.

Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded.

For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.
> 14 votes

# Answer
Saying that the problems can be checked in polynomial time is a simplification that people use to give intuition as to what NP is without nondeterministic Turing Machines, but it's incomplete.

The actual definition is that there is an algorithm which, given a certifier string polynomial in the length of your input can we check if it is a valid certification that a given string is in the language in polynomial time?

For example, in your example of cut size, a certifier is a possible cut. We can't find a cut of size k, but if you give us a some set, we can check if it's a cut and if it has size k, in polynomial time.

This structure is common to the "Does there the x such that y" problems: we use as a certifier a potential x, and then check if y holds. In general, since NP is defined as polynomial time, we can use the trace of a nondeterministic Turing Machine, accepting our language, when run on our input, as certifier to polynomially verify that a given input is accepted.
> 6 votes

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


# Question
Title: Average length and entropy of a code from a probabilistic source
I'm trying to do this exercise but I have some doubts.

> A binary memoryless source emits the symbols 0 and 1 with probability 0.8 and 0.2 respectively. It encodes three blocks messages: 000 is encoded with 0; any other xyz block with 1xyz.
>
> 1. The obtained code is UD?
> 2. It is instantaneous?
> 3. Calculate the average length (binary symbol) of the code and compare that to the entropy of the source.

The code is UD and instantaneous. I tried to calculate the average length and the entropy in this way:

The question marks indicate that I don't know how to go on to make the calculations.

Could someone help me? Thanks a lot!

---

This is what I've done:

$p(000) = 0.8^3 = 0.512$

$p(001) = 0.8^2 + 0.2 = 0.84$

$p(010) = 0.8^2 + 0.2 = 0.84$

$p(011) = 0.8 + 0.2^2 = 0.84$

$p(100) = 0.8^2 + 0.2 = 0.84$

$p(101) = 0.8 + 0.2^2 = 0.84$

$p(110) = 0.8 + 0.2^2 = 0.84$

$p(111) = 0.2^3 = 0.008$

$\bar{l} = \sum\_{i}^{ } l\_i p(a\_i) $ $ = 1\cdot p(000) + 4\sum\_{x^{(3)}\neq 000}^{ } p(x^{(3)})$ $ = 0.512 + 4\[3Pr(\\#1=1) + 3Pr(\\#1=2) + 1Pr(\\#1=3)\]$ $ = 0.512 + 4\[3\cdot 0.2+3\cdot 0.2^2+0.2^3\]=3.424$

$H(X) = -\sum\_{i}^{ } p(a\_i) \log\_{2}p(a\_i)$ $= -0.512 \log\_{2} 0.512 -6(0.84 \log\_{2} 0.84) -0.008 \log\_{2} 0.008 = 1.81$

It's right? I think is not..

---

$p(000) = 0.8^3 = 0.512$

$p(001) = 0.8^2 \cdot 0.2 = 0.128$

$p(010) = 0.8^2 \cdot 0.2 = 0.128$

$p(011) = 0.8 \cdot 0.2^2 = 0.032$

$p(100) = 0.8^2 \cdot 0.2 = 0.128$

$p(101) = 0.8 \cdot 0.2^2 = 0.032$

$p(110) = 0.8 \cdot 0.2^2 = 0.032$

$p(111) = 0.2^3 = 0.008$

$\bar{l} = \sum\_{i}^{ } l\_i p(a\_i) $ $ = 1\cdot p(000) + 4\sum\_{x^{(3)}\neq 000}^{ } p(x^{(3)})$ $ = 0.512 + 4\[3Pr(\\#1=1) + 3Pr(\\#1=2) + 1Pr(\\#1=3)\]$ $ = 0.512 + 4\[3\cdot 0.2+3\cdot 0.2^2+0.2^3\]=3.424$

$H(X) = -\sum\_{i}^{ } p(a\_i) \log\_{2}p(a\_i)$ $= -0.512 \log\_{2} 0.512 -3(0.128 \log\_{2} 0.128) -3(0.032 \log\_{2} 0.032) -0.008 \log\_{2} 0.008 = 2.16$

I don't know what else to do, I feel very stupid.

# Answer
> 1 votes
$\sum\_{x\ne 000} p(x)$ is the probability of at least one 1 in the word. It's easy to break it according the number of ones ($\\#1$) in $x$ $$=3 \Pr\[\\#1 =1\] + 3\Pr\[\\#1=2\] + 1\Pr\[\\#1=3\]= 0.488$$

Which is indeed equal to $(1-(p\_0)^3)$ as you wrote yourself.

The entropy is being computed similarly. Just plug in $\Pr(x)$ for any possible $x\in \\{0,1\\}^3$. BTW, your formula is written incorrectly (I assume it is a typo). Should be $$ H(X) = -\sum\_{a\_i} p(a\_i) \log\_2(p(a\_i)).$$

---
Tags: information-theory
---


# Question
Title: The Chomsky–Schützenberger representation theorem
I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give me hints how to construct proper language?

# Answer
> 1 votes
If you start with a pushdown automaton, then its instruction diagram can be interpreted as a finite state automaton. The instruction $(p,a,A,q,\alpha)$ — in state $p$ reading $a$ we pop $A$ go to state $q$ and push $\alpha$ — has an edge from $p$ to $q$ with label $(a,A,\alpha)$. This defines a regular language of possible instruction sequences (ignoring popping and pushing).

Now recode $(a,A,\alpha)$ by bracket symbols. $A$ is popped and is coded with the closing bracket $\bar A$, the symbols $\alpha$ are pushed and coded as opening brackets. If we code the instruction by the string $\bar A\alpha$ the (regular) language of instructions is a perfect matched bracket sequence (Dyck) if it is a legal sequence of popping and pushing. (Add $Z$ the initial stack symbol as first letter)

Now we forgot about the input letter $a$. This has to be inserted to the instruction, without losing the bracket structure. This is done by adding a virtual closing bracket $\bar a$ for each $a$. Thus, the finite state edge is now as follows: $(p,a\bar a \bar A\alpha,q)$.

Chomsky-Schutzerberger intersects with Dyck for the popping and pushing as I said, and retrieves the symbol $a$ using an homomorphism that deletes all other symbols.

It is also possible to start with a CF grammar in Greibach NF. Then the states totally disappear, the coding is similar, and the regular language is very simple: $S \\{\\; a\bar a \bar A \alpha^R \mid A\to \alpha \\;\\}^\*$

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


# Question
Title: Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?
Karlheinz Brandenburg depicts a MP3 encoder like this:

Source: MP3 and AAC Explained

I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the psychoacoustic model be applyed to the so called lines after the modified discrete cosine transform (MDCT) without performing a FFT?

I have some literature here, saying the frequency resolution is not accurate enough. Does this mean, dividing the original signal into 576 lines (like the filterbank and the MDCT do) is not accurate enough for the psychoacoustic model to work properly? Is the FFT more accurate?

# Answer
> 8 votes
I would suggest a more detailed explanation of mp3 codec.

FFT is applied on the time domain signal, so in fact it does not use the result from the MDCT. The input to the psychoacoustic models is in the frequency domain, hence the FFT.

There at least several reasons to do it. MDCT with filterbanks operates on very short overlapping chunks, maximizing the compression – the FFT uses longer samples and has better spectral resolution. (It is hard to compare since MDCT operates as short-term transform; if this is of big importance to you I will have to make that comparison.)

You can think of filterbank MDCT in the same way as JPEG quantization (it is a very good analogy, since both use DCT) and FFT to detect DCT artifacts from compression. Then, the psychoacoustic model smooths the errors to fall under the "hearable" threshold, but in order to do that, the time domain samples (here PCM – Pulse Code Modulation is not enough, because sudden frequency shifts are heard as cracks) - so it uses the frequency domain to detect such discontinuities and then smooth it in time domain.

Two things are not explained in articles but are crucial. When PCM differences, are high the speaker has more distance to travel, so there is time delay and depending on speaker abilities it might just cause additional vibrations, which are quite distinct noises from speaker. The second part is between lines, the quantized version of signal is transformed back to compare it with original sound and check how much it deviates.

Based on the masking type of windows (based on comparison of FFT and inverted MDCT) is chosen to compensate better for audible deviations from the original.

Humans perceive frequency shifts better than amplitude changes, so the filter operates in the both domains at once, and the quantized signal is reversed and smoothing is done back in time domain.

Yes, the resolution of MDCT with filterbanks is not enough, but this is the part where a fair share of the compression happens, and then it is masked. But the psychoacoustic model has spectral resolution as given in the paper.

Yes, FFT is more accurate because it gets longer samples, so it has better resolution between bins.

*Footnote*
The (M)DCT is commonly implemented by performing FFT, so this has nothing to do with transform used. MDCT can be seen as a bit-modified Short-Term Fourier Transform with a specially chosen filter (the filterbanks resemble Mel scale for speech recognition).

FFT is used longer, provides easier algorithms for pitch shifting and is easier to apply on sound. (M)DCT minimizes the number of components, meaning that we can cut more data from the result than from FFT.

But in the case of sound those components are not stable, cutting always e.g. two bins out will give bigger disortion between consecutive frames than doing equivalent operation on FFT results. So, the connection between FFT and what we hear is bigger than (M)DCT and what we hear, but available compression is the other way around.

---
Tags: algorithms, data-compression, fourier-transform
---


# Question
Title: What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics?
Revising for an exam and I'm trying to get to grips with operational semantics. Here's the exam question that prompted me posting this:

# Exam Question:

We add to the language $\mathsf{SIMP}$ two new commands, with abstract syntax defined by the grammar rule:

$$C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$$

The small step semantics of $\mathsf{SIMP}$ is extended with the following rules:

$$\frac{\langle B, s \rangle \to \\!\\, \langle B', s' \rangle}{\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \\!\\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ C, s\rangle \to \\!\\, \langle C, s \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{False}\ \mathsf{before}\ C, s\rangle \to \\!\\, \langle \mathsf{abort}, s \rangle}$$

The configuration $\langle \mathsf{abort}, s \rangle$ is stuck (no transitions are available from this configuration). Explain with your own words the behaviour of the new commands.

# Given $\mathsf{SIMP}$ Language:

$$ \begin{align\*} C &::= \mathsf{skip} \mid l\ \mathsf{:=}\ E \mid C;\\, C \mid \mathsf{if}\ B\ \mathsf{then}\ C\ \mathsf{else}\ C \mid \mathsf{while}\ B\ \mathsf{do}\ C \\ E &::= \mathsf{!}l \mid n \mid E\ op\ E \\ op &::= \mathsf{+} \mid \mathsf{-} \mid \mathsf{\*} \mid \mathsf{/} \\ B &::= \mathsf{True} \mid \mathsf{False} \mid E\ bop\ E \mid \neg B \mid B \wedge B \\ bop &::= \mathsf{\>} \mid \mathsf{\<} \mid \mathsf{=} \\ \end{align\*} $$

# My Question:

Firstly let me get my understanding of the question out of the way: We're adding a new command $(C)$ to the list of commands we have defined in our $\mathsf{SIMP}$ language. $C$ asserts $B$ before $C$ or aborts the program/process running. Using small step semantics the question has shown us each step of the process as it runs. Here's my issue:

Assuming my knowledge is correct, every rule written below the line holds if what is written above it holds. If this is the case, what is the importance of the first line

$$\langle B,\ s \rangle \ \to \\!\ \ \langle B',\ s' \rangle$$

The rule we have implemented makes no reference of a $B$ in some state $s$ becoming/transitioning into $B'$ in some state $s'$. How can that suddenly be what decides the rule

$$\langle \mathsf{assert}\ B\ \mathsf{before}\ C,\ s \rangle\ \to \\!\ \ \langle \mathsf{assert}\ B'\ \mathsf{before}\ C,\ s' \rangle$$

I feel like that rule should be what we start with, not what comes in second. The rule we decided to add to $\mathsf{SIMP}$'s grammar seemed to be more about checking with $B$ before we continue on to $C$, not checking with $B$ so we can go to $B$ (or something to that effect?).

I know that it's not directly related to the exam question at hand but I feel like understanding why might clear up some gaps in my knowledge regarding operational semantics on the whole. That said, here is my answer to the exam question itself:

'The behaviour of the command $C$ ($C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$) is such that when $B$ is asserted it must return either $\mathsf{True}$ or $\mathsf{False}$, as it is a Boolean command. When it returns $\mathsf{False}$ the program/process is aborted, meaning to transitions from this state cannot be made. If it returns $\mathsf{True}$ then you are able to continue on to $C$ in some state $s$.'

Is this correct? If not, where did I go wrong? Like I said, I don't understand the top two rules and as such I feel it hurts my answer not being able to include them in my reasoning.

# Answer
It seems you have some doubts about the first added evaluation rule $$ \frac {\langle B, s \rangle \to \\!\\, \langle B', s' \rangle} {\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \\!\\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle} $$

It might be redundant, but I ought to point out it's *one* rule: the top part is called a *premise* of the rule, the bottom part is called a *conclusion*.

We call rules of this type *rules of congruence* (and the next two are *computation rules*). One needs rules of congruence to reduce subparts of a bigger expression or command, i.e. reduce something in its context. Usually, one applies rules of congruence until one can use a computation rule to dispose of some parts of the context. Here, the premise serves you as a means of reducing a Boolean expression $B$ to its value $(\mathsf{True}$ or $\mathsf{False})$.

Let me illustrate this by example: if you have a command $\mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}$, and an initial state $s$, then you reduce it to $\mathsf{skip}$ (without changing $s$) using the second added rule: $$ \langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle \to \\!\\, \langle \mathsf{skip}, s \rangle $$

But what should we do if the command we've got is $\mathsf{assert}\ \mathsf{True \wedge \mathsf{True}}\ \mathsf{before}\ \mathsf{skip}$? There is no computation rules for this, i.e. rules that are able to get rid of the $\mathsf{assert}$... part. Here comes the congruence rule: first you reduce $\mathsf{True \wedge \mathsf{True}}$ to $\mathsf{True}$, using some evaluation rule defined for Booleans (not shown here) -- that's why you need the premise ${\langle B, s \rangle \to \\!\\, \langle B', s' \rangle}$ -- then you use the 2nd added rule to finish off your computation:

$$ \langle \mathsf{assert}\ \mathsf{True} \wedge \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle \to \langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle \to \\!\\, \langle \mathsf{skip}, s \rangle $$
> 2 votes

---
Tags: semantics, operational-semantics, small-step-semantics
---


title: What's the definition of ACTL?

text:
# Question
Title: What's the definition of ACTL?
I have been looking for the definition of ACTL, but Google has given me very little to go with.

So far, I know ACTL is another form of CTL model checking, and CTL includes the following operators:

* Always
* Exist
* Global
* Finally
* Next
* AND / OR
* NOT

So what does ACTL include and how is it different from CTL?

Many thanks

# Answer
> 4 votes
ACTL is the universal fragment of CTL. Thus, existential path quantification is not allowed. So a path formula is of the form $AF\psi$, $AG\psi$, or $AX\psi$ (or a conjunction or disjunction of path formulas).

Moreover, you are not allowed a general NOT operator, but rather negations have to be on the atomic propositions (otherwise this fragment would be equal to CTL).

---
Tags: model-checking, temporal-logic
---


# Question
Title: What Exactly is "Improvement" in Seed AI?
From LessWrongWiki, a seed AI

> \[I\]mproves itself by recursively rewriting its own source code without human intervention.

Some would even say this could bring about an Intelligence Explosion. Many of these sources mention that it recursively "improves" itself. What exactly does that mean? How do you define "improve"?

Many people say that since it "improves" itself recursively, the jumps in intelligence would be ever-increasing. However, they also mention that an AI like this would have a goal; for example maximizing knowledge or maximizing human happiness. How would this translate into maximizing of the ability to maximize? You could also maximize for speed, let's say. How do you measure speed? A test, like the TSP? But then wouldn't the machine optimize specifically for solving the TSP, and nothing else? How would that translate into an increasing ability to optimize itself?

In other words, what would one maximize for in an implementation of Seed AI?

# Answer
> Improves itself by recursively rewriting its own source code without human intervention.

A machine learning technique that has some of the properties of a *Seed AI* is Meta Genetic Programming.

With **Genetic Programming** (GP) the system automatically writes code to solve a predefined task. GP evolves computer programs according to a natural evolution paradigm, using various operators and parameters.

**Meta-GP** allows simultaneous evolution of operators and parameters along with the population of programs.

Of course one can imagine multiple meta-levels in an evolutionary computation system: more levels of populations acting on each other and/or populations that act upon themselves.

It's worth noting that there can be a Free Lunch for Meta-GP / Hyper-Heuristics, but these techniques:

* introduce extra computational cost, which have to be weighed against potential advantages;
* seem very sensitive to biases in the syntax from which the operators are generated and thus less robust.

Anyway it's an open research field.

> How do you define "improve"?

Usually GP has an objective function (*fitness function*) to translate a desired behaviour.

Writing these fitness functions is a formidable task and it happens than your GP system optimizes for something other than it was intended for (may it happen for a Seed-AI-system?)

It's not clear if there is a way of doing without defining an objective function.

You can try to mimic Nature using a local, distributed, asynchronous form of competition or, according to the idea that "*to achieve your highest goals, you must be willing to abandon them*", applying Novelty Search,

but often fitness is still there (although behind the scene).
> 2 votes

---
Tags: artificial-intelligence, recursion
---


# Question
Title: Understanding Jeff Erickson's analysis of a basic tree traversal algorithm
I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems very easy to grasp for me so, lets coming to the point there was this section on his notes where he tells:

> **Traversing connected graphs:**
>
> The generic graph traversal algorithm stores a set of candidate edges in some data structure that I’ll call a “bag”. The only important properties of a “bag” are that we can put stuff into it and then later take stuff back out. A stack is a particular type of bag, but certainly not the only one. Here is the generic traversal algorithm:

```
Traverse(s):
  put (∅,s) in bag
  while the bag is not empty
    take (p, v) from the bag (?)
    if v is unmarked
      mark v
      parent(v) ← p
      for each edge vw (†)
        put (v, w) into the bag (??)

```

Seems fine and understandable to me till now then, he goes on to explain the running time of these algorithm which for me is the most important part:

> The exact running time of the traversal algorithm depends on how the graph is represented and what data structure is used as the ‘bag’, but we can make a few general observations. Because each vertex is marked at most once, the for loop (†) is executed at most V times. Each edge uv is put into the bag exactly twice; once as the pair (u, v) and once as the pair (v, u), so line (??) is executed at most 2E times. Finally, we can’t take more things out of the bag than we put in, so line (?) is executed at most 2E + 1 times.

And now the bells ring, the two confusing part for me is:

1. Why line(?) is executed 2E + 1 times? why not 2E? as there are 2E edged, from where this extra 1 is coming from?
2. The most confusing part now is the statement about line(†). Suppose I assume that he is correct.

Now, lets go further:

> Let’s first assume that the graph is represented by a standard adjacency list, so that the overhead of the for loop (†) is only constant time per edge.
>
> • If we implement the ‘bag’ using a stack, we recover our original depth-first search algorithm. Each execution of (?) or (??) takes constant time, so the algorithms runs in O(V + E) time . If the graph is connected, we have V ≤ E + 1, and so we can simplify the running time to O(E). The spanning tree formed by the parent edges is called a depth-first spanning tree. The exact shape of the tree depends on the start vertex and on the order that neighbors are visited in the for loop (†), but in general, depth-first spanning trees are long and skinny

According to me he took the statement (?) and (†) which corresponds to 2E+1 and V respectively to get the running time of the algorithms(I am still hand waving).

The scenario becomes more confusing as he explains what happens when we use adjacency matrix instead of an adjacency list he states:

> If the graph is represented using an adjacency matrix instead of an adjacency list, finding all the neighbors of each vertex in line (†) takes O(V) time. Thus, depth- and breadth-first search each run in O(V^ 2 ) time, and ‘shortest-first search’ runs in O(V^2 + E log E) = O(V^2 log V) time.

I agree that its one of the simplest example of the running time and I understand most part of it but the major confusing part for me is the **statement including the for loop**. Till date I have never included for the loop in the algorithm analysis but the statement inside the for loop for some reason I am not able to digest the reasoning involving the for loop in both the cases.

I have tried to read and understand the statement since couple of days but no success. I am not studying in the university hence I am of my own and no one discuss that's why some may think that my post is so long but maybe I wanted to discuss my doubt clearly.

PS: Correct me if I am missing any mental model or analogy regarding the for loop because right now I am staring it blankly and nothing coming to my mind. I am sound stupid but I need to understand graph theory and I have made up my mind for it.

Here is the relevant lecture note:

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/18-graphs.pdf

# Answer
> 1 votes
I suspect that our reference question contains all you need, but let me address your questions.

> Why line(?) is executed 2E + 1 times? why not 2E?

We start with $(\\\_, s)$ in the bag -- that's a virtual edge not in the tree, hence we get $2|E| + 1$.

> > the for loop (†) is executed at most V times.
>
> The most confusing part now is the statement about line(†)

Are we clear that the meaning is "we get to that loop exactly $|V|$ times", not "there are $|V|$ iterations of that loop in total"?

> > so the algorithms runs in O(V + E) time .
>
> (I am still hand waving)

He's just adding up things. JeffE applies the execution count technique. You can make that explicit by writing the number of executions next to each line; then add up the figures (which gives the correct result up to a constant factor assuming that each line takes time $O(1)$).

> The scenario becomes more confusing as he explains what happens when we use adjacency matrix instead of an adjacency list

You can approach this by unfolding (†) for each specific graph representation, then apply the method as above.

---

*Meta comment:* This analysis is a good example for what I dislike in many textbook analyses. It combines proof of correctness and running-time analysis in a handwaving way -- note how much smoother the analysis can go if we *first* prove that each node gets visited exactly once (for a reasonable definition of what "visit" means)! Then, the algorithm is not even given in as much detail as is necessary to derive the cost at the level of precision we want to, and we expect the reader to fill the gaps.
That said, it's certainly one of the better write-ups with these properties. I'm really criticizing the culture of the field, not the author.

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


# Question
Title: Is there a standard (common) notation for the following operation on binary strings?
Typically, we use the notation $S = \\{0, 1\\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For example, I could try defining $S' = \\{s= s\_n\ldots s\_1 \in S : s\_2 = 1, s\_4=0, s\_n = 1 \\}$ to denote the set of $n$-bit strings where $s\_2$, $s\_4$ and $s\_n$ have the specified values.

Given that I am going to need to define many such subsets, it would be useful to have some better notation.... say $S\_{\\{s\_2 = 1, s\_4 = 0, s\_n = 1\\}}$, though this doesn't look very appealing. For those perhaps more familiar with the literature than I am, is there a set of notation that is typically used to denote such subsets? If not, what might be a compact and appealing way to denote such a subset?

# Answer
There are *pattern* languages \[1\].

A *pattern* is a string over a terminal alphabet $\Sigma$ and an (infinite) variable alphabet $V = \\{x\_i \mid i \in \mathbb{N} \\}$. Let $p = \alpha\_1 x\_{i\_1} \alpha\_2 \dots x\_{i\_k} \alpha\_{k\_1}$ be a pattern with $\alpha\_i \in \Sigma^\*$ for $i \in \[1..k+1\]$ and $x\_j \in V^\*$ for $j \in \\{i\_1, \dots, i\_k\\}$; its language is defined as

$\qquad\displaystyle L(p) = \\{ \alpha\_1 \beta\_{i\_1} \alpha\_2 \dots \beta\_{i\_k} \alpha\_{k+1} \mid \beta\_{i\_1}, \dots, \beta\_{i\_k} \in \Sigma^\* \\}$.

Note that the $i\_j$ need not be pairwise distinct in general -- that is $L(x\_1x\_1) = \\{ww \mid w \in \Sigma^\*\\}$ -- but one can make that restriction.

This is stronger than what you need; you want to restrict the language of possible replacements to individual symbols, and you want the variables to be independent (i.e. the $i\_j$ to be pairwise distinct). It is easy to adapt the definition:

A *bit-pattern* is a string over a terminal alphabet $\Sigma$ and a *wildcard* $\star$. Let $p = \alpha\_1 \star \alpha\_2 \dots \star \alpha\_{k\_1}$ be a pattern with $\alpha\_i \in \Sigma^\*$ for $i \in \[1..k+1\]$; its language is defined as

$\qquad\displaystyle L(p) = \\{ \alpha\_1 x\_1 \alpha\_2 \dots x\_k \alpha\_{k+1} \mid x\_1, \dots, x\_k \in \Sigma \\}$.

This is so straight-forward and the concept of wildcards is so wide-spread that, actually, I don't think you even need a reference; just define whatever you need. If you *do* find a reference it does not hurt to cite it, of course.

---

1. Polynomial time inference of extended regular pattern languages by T. Shinohara (1982)
> 3 votes

# Answer
What Raphael calls bit-pattern here has been treated extensively for general alphabets under the name *partial word* mainly in combinatorics on words. Look for the work of Francine Blanchet-Sadri and co-authors.

What you are looking for would be called the set of all full words *compatible* with a given partial word. In my example from above, the partial word would be \_0\_11 where "\_" represents the "hole" as they call it.

You always have to spell out the entire string of length n in this; no compact notation.
> 1 votes

# Answer
I do not think that there is a standard notation for this. A more compact notation would be taking the two decimal numbers that

1. have the bits that you want and all others zero
2. have ones exactly on the bits you want.

This way you could represent any variant with two numbers.

Example for n=5 and S{s2=1,s4=0,sn=1}: first number 00011 = 3; second number 01011 = 11. So S{3;11}. For fixed n, this would give a unique representation for each possible mask that you want. Anf for large n with many selected bits it would be much smaller, though less direct to understand.

Taking HEX numbers would be a bit more readable because every digit woudl correspond to three bits.
> 0 votes

---
Tags: formal-languages, strings, notation
---


# Question
Title: Convert 24(decimal) to modified IEEE 754 floating point format?
Here's what I have as the tweaked format I'm to use:

* S EEE MMMM (excess 8 format)
* s = sign bit, E = exponent bits, M = mantissa/fraction bits Otherwise, it follows the IEEE 754 in principle. The values:

(-1)^s x 0.0: e == 0, && m == 0

(-1)^s x 0.M x 2^-2: e == 0, && M != 0

(-1)^s x 1.N x 2^(e - 3): 0 \< e \< 7

(-1)^s x infinity: e == 7 && m == 0

NaN: e == 7 && m != 0

That's the formula I've been provided. I need to change 24(decimal) into a floating point binary value, but I continually end up with NaN. Am I doing something wrong?

It is technically a homework question, so if you don't want to provide an exact answer, I'd still be very appreciative if someone can tell me if I'm doing this right or wrong.

# Answer
Since $e=111$ is saved for indicating NaN and $\infty$, then the maximal number that can be represented with this 8bit-floating point structure is $$ (-1)^0 \cdot (1.1111)\_b \cdot 2^{6-3} = 15.5$$

Therefore, you *cannot* represent 24(Dec) using the above system.

However, the correct translation would be infinity rather than a NaN, that is, 24 should be represented as $0\ 111\ 0000 \equiv \infty$.
> 2 votes

---
Tags: floating-point, number-formats
---


# Question
Title: improving java 8's implement to hash map using avl tree
Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup.

Will changing this implement to an avl tree change this O(n) case to something better (without changing the other complexities)?

here are some notes on it:

> This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.
>
> Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same "class C implements Comparable", type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this -- see method comparableClassFor). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)

# Answer
> 4 votes
This page on Oracle's website says:

> The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins containing a large number of colliding keys improve performance by storing their entries in a **balanced tree** instead of a linked list. This JDK 8 change applies only to HashMap, LinkedHashMap, and ConcurrentHashMap.

"Balanced tree" typically means either an AVL tree or a red-black tree. I would expect red-black tree, since TreeMap is already implemented as a red-black tree, and this Stack Overflow answer agrees. In that case, using an AVL tree wouldn't change much because AVL trees and red-black trees have basically the same complexity characteristics: search, insertion, and deletion are all worst case $O(\log n)$.

If the worst case for lookup in Java 8 HashMaps is $O(n)$, I'm not seeing how it could be the tree's fault. The motive behind this change is that HashMap buckets normally use linked lists, but linked lists are worst case $O(n)$ for lookup. Ordinary binary search trees have pathological cases where they become $O(n)$, but red black trees are specifically designed to prevent these cases. In a HashMap with linked lists, if you have a really really awful hash function, you could end up with all the items hashing to the same bucket and get $O(n)$ lookup, but it seems like with this red-black tree scheme, even if all the items hashed into the same bucket, you should get $O(\log n)$ lookup.

---
Tags: data-structures, search-trees, efficiency, hash-tables, java
---


# Question
Title: The transition function in a Markov decision process
A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where

* $A$ is the state space
* $U$ is the action space
* $T: A \times U \times A \mapsto \[0,\infty) $ is the state transition probability function
* $R:A \times U \times A \mapsto \mathbb{R}$ is the reward function

What does this $A \times U \times A$ actually mean in terms of the MDP? It is written in all the papers, but never explained. Does it mean that all the states $a \in A$ are multiplied with all the action $u \in U$? Or something completely different?

# Answer
The notation $T\colon A\times U\times A\to\[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real.

It is somewhat strange that the range is stated as $\[0,\infty)$ rather than $\[0,1\]$. In fact, a perhaps better way of thinking of $T$ is as a function from $A \times U$ to the set of distributions over $A$. That is, $T$ gets a state and an action, and outputs a distribution over the set of states.

The semantics of $T$ are as follows: when at state $a$ and performing action $u$, the probability of moving to state $b$ is $T(a,u,b)$. Thus for all $a \in A$ and $u \in U$ we must have $\sum\_{b \in A} T(a,u,b) = 1$.
> 4 votes

# Answer
Elements of $A\times U\times A$ are triples $(a\_1,u,a\_2)$, where $a\_1$ and $ a\_2$ are elements of $A$ and $u$ is an element of $U$. The $\times$ gives the Cartesian product of its arguments.
> 4 votes

---
Tags: probability-theory, markov-chains
---


# Question
Title: Differences and relations between high-performance/throughput computing and parallel computing?
I wonder if high-performance computing and parallel computing always mean the same? If not,

* what are the differences and relations between them?
* what are some examples of high-performance computing that are not parallel computing?
* what are some examples of parallel computing that are not high-performance computing?

Are high-throughput computing and high-performance computing the same concept?

# Answer
As noted by @JukkaSuomela, you can do parallel computing on low-end resources such as your laptop and even on your mobile phone (if they are equipped with a multicore processor). However, HPC (High Performance Computing) is, roughly stated, parallel computing on high-end resources, such as small to medium sized clusters (ten to hundreds of nodes) up to supercomputers (thousands of nodes) costing millions of dollars. Therefore, the difference is mainly in the hardware used.

Finally, HTC (High Throughput Computing) refers to executing the maximum number of tasks (or jobs if you prefer) per time unit. A classical example of HTC computation is the so called *parameter sweep*, in which you must run the same executable, but varying in each execution a set of parameters (thus the sweep spans the whole parameter space).
> 5 votes

# Answer
I would say parallelism is included in HPC. HPC uses subsidiary tools other than paralelism, the most important being vectorization, including matrix operations with diagonalisation and more general SVD speed boost. So HPC wherewithal are often engaged for big problems only well fitted for matrix(Linpack), well conditioned : simulation, PDE. So it ranges from weather predictions, brain simulation, PDE resolution in near real time for High Frequency Trading, and so on. Further applications on www.top500.org
> 1 votes

# Answer
the field of supercomputing has undergone a significant paradigm shift in the last decade or so such that it used to require highly specialized hardware and designs. a supercomputing company that embodied this approach is Cray supercomputers.

however a new concept/trend has emerged that extremely high performance can be achieved with "off-the-shelf" components such as those used in consumer electronics and heavy internetworking using standard networking components. supercomputer designs have always utilized a large amount of parallelism but this trend has been amplified with the proliferation of the off-the-shelf type approach. also parallelism is much more being supported with sophisticated software architectures such as MPI, MapReduce, etc

so the systems are still highly parallel but the particular means of achieving that parallelism has shifted in the hardware and software. the parallelism is more visible at the application layer and not abstracted away.

also recently power consumption has become much more of an issue and supercomputers are starting to focus on energy-efficient designs and low-energy CPUs such as those used in mobile computing. \[1\] is a nice ref on key issues in current trends/barriers on high performance computing scalability.

\[1\] Next-Generation Supercomputers Kogge
> -2 votes

---
Tags: terminology, parallel-computing
---


# Question
Title: Why does merging two sorted arrays take 2N - 1 comparisons?
A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons

> Prove that merging two sorted arrays of N items requires at least 2N-1 comparisons.

```
 /*
 * An example program that merges two arrays to prove that merging two
 * sorted arrays takes 2N - 1 comparisons.
 */
public class MergeComparisons
{
    private int comparisonCounter;
    public MergeComparisons(){
        this.comparisonCounter = 0;
    }
    public int[] merge(int[] a, int[] b) // MERGE TWO ARRAYS
    {
        int[] arr = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
        {
            comparisonCounter++;
            if (a[i] < b[j])
                arr[k++] = a[i++];
            else
                arr[k++] = b[j++];
        }
        while (i < a.length)
            arr[k++] = a[i++];
        while (j < b.length)
            arr[k++] = b[j++];
        return arr;
    }
    public int getComparisons(){
        return comparisonCounter;
    }
    public static void main(String[] args){
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 7, 8, 9, 10};
        MergeComparisons ms = new MergeComparisons();
        //N = 10 because we have 10 elements.
        //Comparisons should be 19.
        int[] merged = ms.merge(a, b);
        System.out.println("After merging two arrays: ");
        for(int i=0; i<merged.length; i++){
            System.out.print(merged[i] + " ");
        }
        System.out.println("\nUsed " + ms.getComparisons() + " comparisons");
    }
}

```

I wrote the code above to try and test the statement but it does not show. Here is the output

> After merging two arrays: 1 2 3 4 5 6 7 8 9 10 Used 5 comparisons

I was assuming it should be at least 9 comparisons from the way the question was posed.

# Answer
> 10 votes
The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what **comparison-based** algorithm you use, it has to make $2N-1$ comparisons, otherwise it would make an error on **some** input, i.e., it's a worst-case analysis. An algorithm that you come up with might as well do fewer comparisons on some inputs, you just need to show it can't make fewer comparisons on **all** inputs.

Since we are counting comparisons, I assume we are in a so-called comparison model. Assume your arrays are $A\_1 \< A\_2 \< \ldots \< A\_N$ and $B\_1 \< B\_2 \< \ldots \< B\_N$. Usually proofs in this model are information-theoretic. Imagine your algorithm as a comparison tree, where each node queries $A\_i \< B\_j$ for some indices $i, j \in \[N\]$. Then each leaf has to correspond to a correct interleaving of the two arrays $A$ and $B$. How many interleavings are possible? Well you need to choose positions for elements of $A$ and fill in the rest with elements of $B$ (elements of $A$ and $B$ have to appear in order, so there is only one way of doing so). This leads to $2N \choose N$ possible interleavings - these should all appear as leaves in your comparison tree. If a tree has $K$ leaves it has depth at least $\log\_2 K$ (since it's binary). Unfortunately, using Stirling's approximation it leads to a lower bound of $2N - \frac{1}{2} \log N - 1$, which does not match the upper bound of $2N-1$. This is surprising, because for sorting, the information-theoretic bound is optimal in the comparison model.

Knuth describes an adversarial argument (which he in turn attributes to Graham and Karp) in The Art of Computer Programming, Volume 3. It goes like this. Consider answering a query $A\_i \< B\_j$ as "YES" when $i \< j$ and "NO" as $i \ge j$. Then the algorithm will terminate at a leaf $$ B\_1 \< A\_1 \< B\_2 \< A\_2 \< \cdots \< B\_N \< A\_N.$$ Moreover, the algorithm has to make all $2N-1$ comparisons $B\_1$ vs $A\_1$, $A\_1$ vs $B\_2$, $B\_2$ vs $A\_2$, and so on. Why? Suppose it doesn't perform all these comparisons. For instance it does not compare $A\_1$ with $B\_2$, then the following order is also consistent with our responses: $$ B\_1 \< B\_2 \< A\_1 \< A\_2 \< B\_3 \< \cdots \< B\_N \< A\_N.$$

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


# Question
Title: Why does Skiena reserve space for n+1 adjacency lists?
I am reading up on graph theory from the book *Algorithm Design Manual - Skiena*. And he shows a structure of a graph as follows :

```
#define MAXV        100     /* maximum number of vertices */
#define MAXDEGREE   50      /* maximum outdegree of a vertex */

typedef struct {
    int v;              /* neighboring vertex */
    int weight;         /* edge weight */
} edge;

typedef struct {
    edge edges[MAXV+1][MAXDEGREE];  /* adjacency info */
    int degree[MAXV+1];     /* outdegree of each vertex */
    int nvertices;          /* number of vertices in the graph */
    int nedges;         /* number of edges in the graph */
} graph;

```

I am confused about why the size of adjacency list or the degree is MAXV+1. Is it to handle edges that begin and end in the same vertex E(v,v) ?

# Answer
Note that the author uses 1 instead of 0 as the starting point of an array $A$. In other words, $A\[0\]$ is wasted. For example, to initialize a graph:

```
for (i=1; i<=MAXV; i++) g->degree[i] = 0;

```

---

By the way, in the *second edition* of this book, it is (Section 5.2):

```
#define MAXV 1000            /* maximum number of vertices*/

typedef struct {
  int y;                    /* adjacency info */
  int weight;               /* edge weight, if any */
  struct edgenode *next;    /* next edge in list */
} edgenode;

typedef struct {
  edgenode *edges[MAXV+1]; /* adjacency info */
  int degree[MAXV+1];      /* outdegree of each vertex */
  int nvertices;           /* number of vertices in graph */
  int nedges;              /* number of edges in graph */
  bool directed;           /* is the graph directed? */
} graph;

```
> 1 votes

---
Tags: graphs, data-structures
---


# Question
Title: Order classic notions of computability by power
I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question:

**Order the following formalisms (but one) according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state which, if any, of them are equivalent. Point out the formalism that does not fit into the ordering.**

* Context Free Grammars ( CFG )
* Deterministic Finite Automata (DFA)
* Deterministic Pushdown Automata (DPDA)
* LR(0) grammars
* LR(1) grammars
* Nondeterministic Finite Automata ( NFA)
* Nondeterministic Finite Automata with epsilon-transitions ( NFA - epsilon)
* Nondeterministic Turing Machines ( NTM )
* Pushdown Automata ( PDA )
* Regular Expressions ( reg. exp )
* Turing Machines ( TM )
* Turing Machines with two heads ( TM 2h )

The trick here is to find the one that does not fit into the ordering and why. I'm just not able to find that one.

# Answer
I think that LR(0) is incomparable to the regular languages, see the answers to question Are regular expressions $LR(k)$? . Thus it does not fit in a linear hierarchy with all the rest. It could be the bottom element, but for REG there are several characterizations; thus more than one class would not fit in the hierarchy. Therefore they probably mean LR(0).
> 1 votes

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


title: Voronoi Diagram: Exactly 2n-5 vertices

text:
# Question
Title: Voronoi Diagram: Exactly 2n-5 vertices
I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.

I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:

$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?

# Answer
> 2 votes
You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a new vertex and making all rays incident to this "apex". Plugging this into Euler's formula yields

$$ 2n-4 - e + n = 2 \quad \Rightarrow \quad e= 3n - 6.$$

A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula – just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram has degree~3 and there are three rays.

---
Tags: graphs, computational-geometry, voronoi-diagrams
---


title: Undecidable vs Unsolvable?

text:
# Question
Title: Undecidable vs Unsolvable?
In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is what does "undecidable" mean ? I read the "undecidable" applies to problems that *have* Turing Machines but cannot definitively tell us whether an input is valid or not(i.e. it outputs "yes" for valid inputs, and keep going for others indefinitely such that we will not know when, if ever, it will output anything). Then does "undecidable" applies to problems that **can not** be represented by Turing Machines at all, also? What is the difference between unsolvable and undecidable ?

**EDIT:** I was reading my textbook(Introduction to Automata Theory, Hopcroft) and I ran into this: "Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable(i.e., that it has no algorithm, or TM that always halts"(pg 388). This seems to imply undecidable problems do not include ones without any TMs. Am I interpreting this correctly ?

# Answer
Yes, undecidable also applies to problems that cannot be represented by TM at all. The ones where a YES can always be found are a subclass of these called *(recursively) enumerable*. Unsolvable is a less common term which I know mostly to be used synonymous to undecidable.

So *decidable - undecidable but enumerable - non-enumerable* is a partition of the class of all problems into three classes, where the middle one is intuitively somthing like the easiest undecidable problems.
> 1 votes

---
Tags: computability, terminology, undecidability
---


# Question
Title: Theoretical justification of "halting problem avoidance"
The wikipedia page for the Halting problem mentioned *practical solutions* to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities of general-purpose (Turing-complete) programming language, it is possible to guarantee the completion of all sub-routines (written under the restriction)".

What seems unclear to me is the underlying computation model of such restricted programming languages.

Say, if we remove -- from a general-purpose (Turing-complete) programming language -- the capability to conduct infinite loops (i.e. making the loop variable to always enumerate a finite list of elements, avoiding circular function recursions, etc), what would be the *expressiveness* of the resulting programming language or (the capabilities of) the corresponding computation model.

Possibly related questions

Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

# Answer
It is absolutely theoretically justified.

First realize that a loop is just a form of recursion: do the loop body, then either stop or do the loop body again with different variable values.

System F is a lambda calculus (programming language) with no recursion built in, and it is known to be strongly normalization. That is well typed every computation in this system halts. It's also powerful enough to compute basically every function you can think of, including the infamous Ackerman function.

In this system, you can use Church numerals to simulate the finite looping you mention in your question.

If you take a programming language without loops, you can model it in System F, which will give you a guarantee that all programs in this system halt.

It's implicit that if you remove loops, you also remove GOTO, which can be used to build loops.
> 2 votes

---
Tags: computability, computation-models, halting-problem
---


# Question
Title: Convex hull algorithm in $O(\min(mn, n\log n))$
I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$.

My first guess was QuickHull, which has a best case running time of $O(n \log n ) $ and a worst case running time time of $O(n^2)$. However, I am a little bit confused about the fact that this convex hull does not have to contain all points. Can I ignore this? I guess yes because I must assume the worst case and this would include all points.

Any ideas or hints?

# Answer
> 4 votes
The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other one. This runs in time $O(\min(mn,n\log n))$.

In fact, you can do better – Wikipedia lists several $O(n\log m)$ algorithms, which is strictly better than the guarantee you are looking for.

---
Tags: algorithms, computational-geometry, convex-hull
---


# Question
Title: Prove that language of possible stack content is regular
So, here's the problem:

Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \\{ \gamma \in \Gamma^\* \hspace{5pt}|\hspace{5pt} \exists\_{x,y\in \Sigma^\*} \exists\_{q\in Q}: (s,x,\bot)\vdash\_A^\*(q,y,\gamma)\\}$$

Show that $L$ is regular.

So far solution has been eluding me, any hints are welcome.

# Answer
Here is the basic idea. Assume for simplicity that each transition increases the size of the stack by at most one (you can always arrange that using epsilon transitions).

Suppose that the stack at some point is (bottom to top) $A\_1 \ldots A\_n$. At the time $t$ of the snapshot, $A\_1$ is at the bottom of the stack. Consider the earliest time $t\_1$ such that from time $t\_1$ to time $t$, $A\_1$ was always the bottom of the stack. At time $t\_1$, the stack is simply $A\_1$.

Similarly, there is an earliest time $t\_2$ at which $A\_2$ was second from last symbol on the stack, and at time $t\_2$, the stack is $A\_1 A\_2$. We can similarly define times $t\_3,\ldots,t\_n$. We can describe the state of the stack schematically as follows: $$ \bot \vdash^\* A\_1 \vdash^\* A\_1 A\_2 \vdash^\* \cdots \vdash^\* A\_1 A\_2 \ldots A\_n. $$ The first step is special, so let's consider any other step. Think about what information is required to known whether you can get from $A\_1 A\_2 \ldots A\_i$ to $A\_1 A\_2 \ldots A\_{i+1}$, without every removing $A\_1 A\_2 \ldots A\_i$. If the amount of information is finite, then you can use it to construct an automaton for your language.
> 2 votes

---
Tags: formal-languages, regular-languages, automata, pushdown-automata
---


# Question
Title: What functions can combinator calculus expressions compute?
A combinator expression (let's say in the SK basis) can be thought of as a function that maps combinator calculus expressions to combinator calculus expressions. That is, one can think of an expression $X$ as a function $X:L \to L$, where $L$ is the set of all syntactically valid combinator expressions in the SK basis. This mapping is performed by applying the input to the expression, and then reducing to normal form to get the output.

Since the SK basis is Turing complete, one might naïvely think that there exists a an SK expression $X$ that implements any computable function from $L$ to $L$. However, this clearly isn't the case, since the result of reduction will always be in normal form. This means there is no way for an expression to have an output that isn't in normal form.

So instead, I could think of SK calculus expressions as mapping $L'$ to $L'$, where $L'$ is the set of SK expressions in normal form. Is it the case that, for any computable map $f:L'\to L'$, there is an SK expression $X$ that implements this map? Or are there further restrictions on the set of functions that can be computed by combinator calculus expressions in this way?

# Answer
> 7 votes
To get the ball rolling, and in hopes of other people giving deeper and more detailed answers on the structure of the $\lambda$-definable functions $L'\to L'$, let me cite Corollary 20.3.3 from Barendregts' *The Lambda Calculus, Its Syntax and Semantics* (aka "the bible").

> Corollary 20.3.3: The function $\delta:L'^2\to L'$, defined by $$ \delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=\_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$$ is not definable in the untyped $\lambda$-calculus, i.e. there is no term $D$ such that $$D\ M\ N =\_{\beta\eta} \delta(M,N)$$ for all $M,N\in L'$.

The proof involves considerations on Böhm trees which give a rather strong characterization of the possible "actions" of arbitrary lambda terms on normal forms. In particular, for any non-constant closed term $F$, on can find $n\in\mathbb{N}$ and $P\_1,\ldots,P\_n$ such that $$ F\ x\ P\_1\ldots P\_n =\_{\beta\eta} x\ Q\_1\ldots Q\_k$$

For some $k$, $Q\_1,\ldots,Q\_k$. This drastically constrains the possible forms of a hypothetical $D$ that implements $\delta$, showing with a little work that such a $D$ cannot exist.

---
Tags: lambda-calculus, combinatory-logic
---