# Question
Title: What makes a language "optimized" for a specific task?
Often there are programming languages that are specialized for specific tasks. Some programming languages are excellent at array arithmetic (such as matrices and the use of multidimensional arrays), yet some are much better at higher-level mathematics that is hard to reproduce in other languages (yet still possible all the same).

What about a language makes it better for a specific task or end-goal than other languages, given that most simply compile down to assembly anyways?

I am talking about Turing complete languages, ones that are Turing equivalent.

# Answer
There are a few things to consider:

* Abstraction: what does the language treat as "special"? Are matrices first-class values, like in Matlab, or do you encode them using simpler types like arrays, as in C? C makes you think about how matrices are implemented, Matlab doesn't.

Likewise, if you've got a complicated system of asynchronous communications, you probably want first-class functions so that you can do callbacks.

The more features that are added, the more complex the language gets. So while there are some "multi-paradigm" languages like C++ and D, most languages pick a niche, choose the things that are important to that niche, and prioritize those as their main abstractions.
* Performance: all abstraction comes with a cost, whether it be compile-time or run-time. Some languages limit themselves in a way that makes them less abstract but more performant.

Early Fortran didn't allow for pointers or recursion, so it was great at number crunching, faster than a language like C, where you were running lots of loops. But it was terrible at encoding large data structures, like trees, where you needed pointers for indirection. (Note that I don't know much about modern Fortran.)

Essentially, there are always tradeoffs. More abstract means either slower runtime or more complexity at compile-time. More features means a more complex language. Some features make certain things fast and others slow, like pointers and recursion. There's no perfect language, so each language will reach a sort of local maximum in the space of language qualities.
> 19 votes

# Answer
The constraints of some languages makes it easier to implement faster code (e.g. Fortran vs C and the pointers aliasing) which is a tradeoff between out-of-the-box performance and possibilities).

The language is not "optimized" for specific tasks, but the implementation, compilers and constraints that make it easier to understand the code by compiler makes so. The real deal is about specific libraries, algorithms implemented to speed up the process with switches depending on the problem length makes it optimal.

For example the multiplication uses various cases (see GMP multiplication.

When the language specifies the higher level mathematic operations it's implementation is optimal (efficient in this case), but that is not the part of language specification.

Please take a look at matrix rank computation in Matlab, Mathematica and Maple (I cannot perform all the tests myself right now, but these are consistent with my tests). All these languages (environments) implement the same higher level operation but the implementation details differ which gives various times.

When some domain specific task (here also domain specific language) is oriented at particular calculations they get improved and optimized (over the years) for the target audience. But being optimal is not always the case. For example Perl has a long history of handling strings, but the PCRE (here simply Perl's regular expressions) are not the fastest existing ones (and use a lot of memory), but are extremely expressive and powerful.

The constraints of the language makes a difference in the compilation process, the mentioned pointer aliasing prevents the possibility of the code reordering and enforces reloading of variables.
> 8 votes

# Answer
In my opinion this can actually be formulated quite precisely: A tool (for example, a programming language together with its standard libraries) is the optimal tool for a particular class of problems when it minimises, over all possible tools that could be employed, the expected cost of getting a sufficiently correct and performant solution, where the expectation is taken over some given probability distribution over all problems in the problem class. Mostly this cost comes in the form of *programmer time*, and includes expected design time, expected debugging time, expected time needed to educate someone not already familiar with the tool, etc.

In practice, almost none of these quantities can actually be measured. Still, I think it's the right way to think about the problem.
> 5 votes

# Answer
It's an excellent question and not easily answered. Is there anything about the Erlang language that makes it suitable for real-time telecommunications applications? Or is it something about the Erlang compiler? Or is it something about the Erlang community and ecosystem? Perhaps it's that people who know how to write telecomms applications are expert in Erlang, and the people who know Erlang are expert in telecomms applications? I suspect that all these factors play a role.

There are probably two features in Erlang that make it suited to such applications (caveat: I've never used the language myself) - it has good support for concurrency, and support for dynamic software upgrade. Those features would be useful in many other areas too, but telecomms engineers are fanatical about uptime. Perhaps if people building web sites were as concerned about high availability as people building telephone exchanges, Erlang would be popular there too.
> 4 votes

# Answer
The other answers miss the point of optimising a language for a specific task - it isn't just about what makes code run faster on given hardware; it's about how clearly and succinctly a particular language allows you to express the solution to a problem. That very much depends on the problem domain, and (along with marketing hype, ignorance of existing solutions, and the ego trip of writing a new language) is why we have multiple languages - the goal is for the programmer to write less code, which is both less error prone and easier for the next programmer to read/understand/fix/enhance.

For example, both C and C++ can be used for object orientated programming - and indeed, the GObject library is a good example of OO C. A C struct containing function pointers can serve the same purpose as virtual methods on a C++ class, and can perform better; the development penalty is glue code to allocate memory, initialise the function pointers, and choosing a strategy for calling 'parent' methods. Most of the time it's clearer/safer to type `Class klass * = new class()` than `struct class *klass = malloc(sizeof(struct class));klass->fn1 = ...;klass->fnN = ...`.
> 3 votes

---
Tags: programming-languages
---


title: Merging two complete heaps

text:
# Question
Title: Merging two complete heaps
Suppose you have two heaps each containing $2^k - 1$ elements.

Design an efficient algorithm for merging these two heaps into a single heap.

My approach was to assume two heaps are maxheap. Create one node with value $-\infty$ and attach one heap as left subtree and another as right subtree, and call the heapify procedure. So it should take $O(\log(2(2^k-1)+1))=\log(k)$ time.

But my confusion is $-\infty$ valued node doesn't necessarily go at the last node of heap.

# Answer
Calling heapify once isn't going to build a heap in one iteration . Instead merge the two arrays which contain both heaps initially and call BuildHeap() procedure. You will get a heap in O(n) time.
> 1 votes

---
Tags: algorithms, trees, heaps
---


# Question
Title: How does one program crashing not crash the entire system?
In Windows, if you write a random assembly program that has a random jump to an address that doesn't exist, the program crashes and Windows says something went wrong with the program.

Since each computer system is essentially a constant execution of assembly, how does the one program crashing not cause the entire system to crash with it?

# Answer
Probably you should read something about OS memory management.

If the program is running it has memory which is readable, memory which is writable and both. If it tries to go beyond its permissions, OS kills it and reports to you in a way you call "crash".

That's all was very roughly speaking.
> 2 votes

# Answer
As I understand it, the program runs in "protected mode". Presumeably this means that every memory call or address is checked against the memory assigned to it. If it is outside this range, an error is reported.
> 0 votes

---
Tags: operating-systems
---


title: What is a final state?

text:
# Question
Title: What is a final state?
I am studying DFA's, but I've been struggling to find an explanation of what does the final state mean? I know that it is indicated by double circle on the graph, but what does it imply?

# Answer
If you want to know what a mathematical object is, you need to read its definition. So, I imagine you've seen the definition of finite automata, and it has something called a "set of final states", and the definition probably doesn't say what that means.

OK, that means that, for now, the author is just giving a name to this set of states. They surely wouldn't bother naming something if it was never going to be used, so we need to keep reading. The very next thing you read is probably a desciption of how an automaton processes its input by moving from state to state as it reads the characters. That doesn't seem to involve the concept of final states, so we keep reading some more. The next thing is probably a definition of what inputs are accepted by the automaton. That definition does involve final states, and it tells you exactly what their role is.

The moral of the tale is that, if you want to know what a mathematical object *is*, you need to read its definition. If you want to know what it's *for*, you might have to read a bit more, after its definition. (A good writer will warn you if the point of something isn't going to be revealed for a while.) If you want to know why anyone should care about the object, you might have to do a lot of reading, or find someone (or somewhere! ;-) ) to ask questions.
> 5 votes

# Answer
When the automaton has processed the entire input, it *accepts* the input if (and only if) it s in a state marked as final.

It is really no more complicated than that.
> 5 votes

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


# Question
Title: What is the purpose of interpreting elements in the proof of reduction of PCP to validity decidability problem of predicate logic?
Since my question relates directly to a part of the text from a 2004 book, *Logic in Computer Science: Modelling and Reasoning about Systems (2nd Edition) by Michael Huth and Mark Ryan*, in order to provide context for the following discussion, I'm partially quoting the book verbatim:

> The decision problem of validity in predicate logic is undecidable: no program exists which, given any $\varphi$, decides whether $\varphi$.
>
> PROOF: As said before, we pretend that validity is decidable for predicate logic and thereby solve the (insoluble) Post correspondence problem. Given a correspondence problem instance $C$: $$s\_1 s\_2 ... s\_k$$ $$t\_1 t\_2 ... t\_k$$ we need to be able to construct, within finite space and time and uniformly so for all instances, some formula $\varphi$ of predicate logic such that $\varphi$ holds iff the correspondence problem instance $C$ above has a solution.
>
> As function symbols, we choose a constant $e$ and two function symbols $f\_0$ and $f\_1$ each of which requires one argument. We think of $e$ as the empty string, or word, and $f\_0$ and $f\_1$ symbolically stand for concatenation with 0, respectively 1. So if $b\_1 b\_2 ... b\_l$ is a binary string of bits, we can code that up as the term $f\_{b\_l}(f\_{b\_{l−1}}...(f\_{b\_2}(f\_{b\_1}(e)))...)$. Note that this coding spells that word backwards. To facilitate reading those formulas, we abbreviate terms like $f\_{b\_l}(f\_{b\_{l−1}}...(f\_{b\_2}(f\_{b\_1}(t)))...)$ by $f\_{{b\_1}{b\_2}...{b\_l}}(t)$.
>
> We also require a predicate symbol $P$ which expects two arguments. The intended meaning of $P(s,t)$ is that there is some sequence of indices $(i\_1,i\_2,...,i\_m)$ such that $s$ is the term representing $s\_{i\_1} s\_{i\_2}...s\_{i\_m}$ and $t$ represents $t\_{i\_1} t\_{i\_2}...t\_{i\_m}$. Thus, $s$ constructs a string using the same sequence of indices as does $t$; only $s$ uses the $s\_i$ whereas $t$ uses the $t\_i$.
>
> Our sentence $\varphi$ has the coarse structure $\varphi\_1 \wedge \varphi\_2 \implies \varphi\_3$ where we set
>
> $$\varphi\_1 \stackrel{def}{=} \bigwedge\limits\_{i=1}^k P\left(f\_{s\_i}(e),f\_{t\_i}(e)\right)$$
>
> $$\varphi\_2 \stackrel{def}{=} \forall v,w \hspace{1mm} P(v,w)\rightarrow\bigwedge\limits\_{i=1}^kP(f\_{s\_i}(v),f\_{t\_i}(w))$$
>
> $$\varphi\_3 \stackrel{def}{=} \exists z\hspace{1mm} P(z,z)$$.
>
> Our claim is $\varphi$ holds iff the Post correspondence problem $C$ has a solution.

In proving PCP ⟹ Validity:

> Conversely, let us assume that the Post correspondence problem C has some solution, \[...\] The way we proceed here is by *interpreting* finite, binary strings in the domain of values $A′$ of the model $M′$. This is not unlike the coding of an interpreter for one programming language in another. The interpretation is done by a function **interpret** which is defined inductively on the data structure of finite, binary strings:
>
> $$\text{interpret}(\epsilon) \stackrel{def}{=} e^{M′}$$
>
> $$\text{interpret}(s0) \stackrel{def}{=} {f\_0}^{M′}(\text{interpret}(s))$$
>
> $$\text{interpret}(s1) \stackrel{def}{=} {f\_1}^{M′}(\text{interpret}(s))$$.
>
> \[...\] Using \[$\text{interpret}(b\_1 b\_2...b\_l) = f\_{b\_l}^{M′}(f\_{b\_{l-1}}^{M′}(...(f\_{b\_1}^{M′}(e{M′})...)))$\] and the fact that $M\models\varphi\_1$, we conclude that $(\text{interpret}(s\_i), \text{interpret}(t\_i)) \in P^{M′}$ for $i = 1,2,...,k$. \[...\] since $M′ \models \varphi\_2$, we know that for all $(s,t) \in P^{M′}$ we have that $(\text{interpret}(ss\_i),\text{interpret}(tt\_i)) \in P^{M′}$ for $i=1,2,...,k$. Using these two facts, starting with $(s, t) = (s\_{i\_1}, t\_{i\_1})$, we repeatedly use the latter observation to obtain
>
> (2.9) $(\text{interpret}(s\_{i\_1}s\_{i\_2}...s\_{i\_n}),\text{interpret}(t\_{i\_1}t\_{i\_2}...t\_{i\_n})) \in P^{M′}$.
>
> \[...\] Hence (2.9) verifies $\exists{z} P(z,z)$ in $M′$ and thus $M′ \models \varphi\_3$.

In proving that the validity of predicate logic is undecidable, according to the approach I learned from school, which is based on that of the *Huth & Ryan book (2nd edition, page 135)*, when constructing the reduction of PCP to Validity problem, the "finite binary strings" of the universe are interpreted with a "**interpret** function", which encodes binary strings into composites of functions of the model.

Then it goes on to show that, using the fact that the antecedent of $\varphi$ must hold for it to be non-trivial, both sub-formulae of the antecedent can be expressed with the said "**interpret** function". From there, it follows that the consequence holds, too, since it can also be expressed in a way with the **interpret** function that follows from the previous expressions with **interpret**.

My question is: what is the purpose of this "**interpret** function"? Why can't we just use the previously devised φ and get the same result? What do we get out of using **interpret** to express our elements?

And also, what if our universe contains some arbitrary elements; that is, what if they are not binary strings? Do we just construct some mapping of the two?

# Answer
> 7 votes
Lets start with what exactly you are trying to prove.

You're dealing with a signature $\sigma$ which consists of one constant $e$, two function symbols $f\_0,f\_1$, and one binary predicate $P(s,t)$. We denote by $\mathcal{C}$ the set of all "yes" instances to the post correspondence problem, i.e. all sequences of ordered pairs of binary strings $(s\_1,t\_1),...,(s\_k,t\_k)$ such that there exists indices $i\_1,...,i\_n$ for some $n\in\mathbb{N}$ which satisfy $s\_{i\_1}\cdot...\cdot s\_{i\_n}=t\_{i\_1}\cdot...\cdot t\_{i\_n}$ ($\cdot$ stands for concatenation).

You want to show that given an instance $c=(s\_1,t\_1),...,(s\_k,t\_k)$ to the post correspondence problem, then

$c\in\mathcal{C} \iff$ If $\mathcal{M}$ is any model interpreting $\sigma$, then $\mathcal{M\models\ \varphi(c)}$

Where $\varphi(c)=\varphi\_1(c)\land\varphi\_2(c)\rightarrow \varphi\_3(c)$, and

$\varphi\_1(c)=\bigwedge\limits\_{i=1}^k P\left(f\_{s\_i}(e),f\_{t\_i}(e)\right)$,

$\varphi\_2(c)=\forall v,w \hspace{1mm} P(v,w)\rightarrow\bigwedge\limits\_{i=1}^kP(f\_{s\_i}(v),f\_{t\_i}(w))$,

$\varphi\_3(c)=\exists z\hspace{1mm} P(z,z)$.

In the above, given a binary string $s=s\_1,...,s\_l$, $f\_s$ denotes the composition $f\_{s\_l}\circ f\_{s\_{l-1}}\circ ...\circ f\_{s\_1}$. This is the reduction from PCP to validity in predicate logic described in "logic in computer science" by Huth & Ryan.

We think of $f\_0,f\_1$ as concatenation with $0,1$ correspondingly, and of $e$ as the empty string. In that case, we can think of $f\_s(e)$ as a representation of the string $s$ in the world of $\mathcal{M}$. Intuitively, $\varphi\_1,\varphi\_2$ force the predicate $P(v,w)$ to hold when (perhaps in some other cases as well, but we wont care) $v=f\_s(e), w=f\_t(e)$ (meaning that $v,w$ are the interpretations of some finite strings $s,t$ in the world of $\mathcal{M}$) and there exists a sequence of indices $i\_1...i\_n$ such that $s=s\_{i\_1}\cdot...\cdot s\_{i\_n}$ and $t=t\_{i\_1}\cdot...\cdot t\_{i\_n}$. If $P(v,w)$ indeed has that meaning (which is what happens if $\mathcal{M}$ satisfies $\varphi\_1\land\varphi\_2$), then $c\in\mathcal{C}\iff \exists z P(z,z)$.

You ask about the $\Rightarrow$ direction of the proof, so you must handle arbitrary models which interpret $\sigma$, where the world can have elements which have nothing to do with strings (this relates to your second question). This is where the interpretation function comes in. We give a correspondence between all finite strings and a subset of the world of $\mathcal{M}$, which is rather natural given the nature of our signature. A string $s$ is mapped to the element $f\_s(e)$, which can be a string/number/table or anything you like.

Now, when we have the ability to think of elements of the form $f\_s(e)$ in $\mathcal{A}\_{\mathcal{M}}$ (the world of $\mathcal{M}$) as finite strings, we can go on and prove the $\Rightarrow$ implication. If $\mathcal{M}$ satisfies $\varphi\_1,\varphi\_2$, then as we mentioned, $P(v,w)$ holds when $v=f\_s(e), w=f\_t(e)$ (now we can think of $v,w$ as strings), and there exists a sequence of indices $i\_1...i\_n$ such that $s=s\_{i\_1}\cdot...\cdot s\_{i\_n}$ and $t=t\_{i\_1}\cdot...\cdot t\_{i\_n}$. Thus, if $c\in \mathcal{C}$, and $i\_1...i\_n$ is a sequence of indices with $s=s\_{i\_1}...s\_{i\_n}=t\_{i\_1}...t\_{i\_n}=t$, then $P(f\_s(e),f\_t(e))$ holds, and we have $\mathcal{M}\models \varphi\_3$, since $s=t$ implies $f\_s(e)=f\_t(e)$.

---
Tags: reductions, logic, proof-techniques, undecidability
---


# Question
Title: How to write a regular expression to match a string that starts with the same pattern that it ends with
Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with.

Let's say that we have an alphabet composed of the binary symbols: {0,1}

We should make a regular expression to create a language that is composed of words (W) with the following pattern:

W=w1w2w1 and w1 and w2 are words from the closure of the {0,1} alphabet.

I do not know how to approach this task. I am not convinced it is even possible because there is no way we can memorize anything inside a regex.

The only operators that we should use are the following three: -Concatenation -Star (closure) -OR

# Answer
Since you asked how to approach it, a good starting point for these sorts of problems is to start by *understanding the language*. Try writing down all words in the language of length 1; all words of length 2; all words of length 3; all words of length 4; and see if you can spot any possible patterns (about which words are in the language and which aren't). Then, see if you can prove your guess.

Finally, use that to help you brainstorm ideas for how to express this as a regular expression.

Make sure to read How to prove a language is regular? carefully.
> 1 votes

---
Tags: formal-languages, regular-languages, finite-automata, formal-grammars, regular-expressions
---


# Question
Title: Digraph without circuits with negative cost
Let $D=(V,E)$ be a digraph and let $a\colon E\to\mathbb{R}$ be a cost function on the edges.

How can I prove that $D$ has no circuits with negative costs **only if** there exists a function $\pi\colon V\to\mathbb{R}$ such that $a(uv) + \pi(u) − \pi(v) \ge 0$, for all $uv\in E$?

I realised that this is true by some examples, but I can't realise how can I prove that this is true in general?

# Answer
Sum up the value of $a(uv)+\pi(u)-\pi(v)$ over all the edges in some circuit. What can you say about the result? What does this imply about whether that circuit was a negative circuit?
> 1 votes

---
Tags: graphs
---


# Question
Title: Write a regex to match string that does NOT contain a certain pattern
Let's say our alphabet is 0 and 1.

How would you approach writing a regex to generate a language of words that do NOT contain 101.

The only regex operators allowed are concatenation , star * and OR |.

I am stuck now and I want to know if anybody has an idea.

# Answer
> 3 votes
If a string does not contain $101$, then every $10$ either terminates the string or is followed by $0$. So if $r$ is a regular expression for all strings not containing $10$, then a regular expression for all strings not containing $101$ is $$ (r100)^\*r(10+\epsilon). $$ You take it from here. Note that there are also other solutions.

---

Complementing a regular expression can be a very costly operation. For example, the set of strings over $\\{1,\ldots,n\\}$ not containing all symbols has a regular expression of length $O(n^2)$ (exercise), but its complement requires a regular expression of exponential size $\Omega(2^n)$. This follows from the "fooling set" lower bound on NFAs, and the fact that regular expressions can be converted into NFAs with constant multiplicative overhead.

A fooling set for a language $L$ is a collection of pairs $(x\_i,y\_i)$ such that $x\_iy\_i \in L$ but for $i \neq j$, either $x\_iy\_j$ or $x\_jy\_i$ is not in $L$. If $L$ has a fooling set of size $n$ then every NFA for $L$ has size $n$ (exercise). In the case of all strings over $\\{1,\ldots,n\\}$ containing all symbols, there is a fooling set of size $2^n$: $\\{(S,\overline{S}) : S \subseteq \\{1,\ldots,n\\}\\}$, where we identify a set of symbols with the word containing these symbols in order.

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


# Question
Title: Prim's algorithm on graph with weights of only $1$ and $2$ on each edge
I have this version of Prim's algorithm

Prim$(G=(V,E),s\in V,w)\\ 1.\ d(s)\leftarrow 0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\ 2.\ \forall u \in V:p(u)\leftarrow \text{null}\quad \color{red}{O(|V|)}\\ 3.\ s\leftarrow \emptyset,T\leftarrow \emptyset\quad \color{red}{O(1)}\\ 4.\ Q \leftarrow \text{Makeheap}(V)\quad \color{red}{O(|V|)}\\ 5.\ \text{while}\ Q\neq \emptyset\\ 6.\qquad u\leftarrow Q.\text{ExtractMin()}\quad \color{red}{O(\log(|V|))}\\ 7.\qquad S\leftarrow S\cup\\{u\\},\ T\leftarrow T\cup\\{(u,p(u))\\}\quad \color{red}{O(1)}\\ 8.\qquad \text{for each}\ (u,z)\in E,z\in Q\\ 9.\qquad\qquad \text{if}\ d(z)\>w(u,z)\ \text{then}\\ 10.\qquad\qquad\qquad Q.\text{Remove}(z);Q.\text{Insert}(z,w(u,z))\quad \color{red}{O(\log(|V|))}\\ 11.\qquad\qquad\qquad d(z)\leftarrow w(u,z),\ p(z)\leftarrow \quad \color{red}{O(1)}\\ 12.\ \text{return }T$

Total time: $O(|E|\log(|V|))$

---

Given a weighted, connected, simple undirected graph $G$ with weights of only $1$ and $2$ on each edge, why in this case the running time of the algorithm is $O(|E|+|V|\log(|V|))$?

I really not understand why the running time is not the same in this case, any help?

# Answer
The running time depends on how you implement the queue data structure.

Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are much faster, if you're given the knowledge that every edge has weight either 1 or 2?
> 1 votes

---
Tags: algorithms, time-complexity, spanning-trees, minimum-spanning-tree, prims-algorithm
---


# Question
Title: How would one implement a Frequently Used algorithm?
The iOS emoji keyboard has a Frequently Used section. Notably, this is different from a Recently Used implementation - the data structure behind it is not an array of emoji where once you use an emoji it is inserted in the array (after first removing it if it already exists). But neither does it appear to be implemented as if it were titled Most Often Used - it doesn't appear to simply be sorting by the symbols you've used the highest number of times. There are more smarts to it. It seems the algorithm is taking into consideration how many times you've used each symbol, but also when it was used, and sorting it on some combination. For example I recently used an emoji just one time and yet it appears in my Frequently Used list towards the end but before other emojis that I know I've used multiple times in the past but haven't used very recently.

If one wished to recreate the iOS Frequently Used algorithm, how would one do so, what exactly does this algorithm do?

# Answer
You are running into a situation where the task is not "here is a specification of what constitutes a good value, find the best one", but "find a result that is as useful as possible to the user, with no clear specification what 'useful' means".

It's a difficult problem. You can't even ask the users what they think is most useful - because they don't know, and even if they have an opinion what they *think* is most useful, that doesn't necessarily agree with reality.

You might also consider that *changing* the set of emojis is of slight negative value because it's harder to find one if the set is changing. On the other hand, emojis that are easy to find anyway (for example smileys that come first in the ordinary list) are less useful. And you might consider context, a user might use different emojis depending who is going to receive the message. Imagine the software knows the receiver, and knows it is their birthday, and suddenly the set of "most useful" emojis totally changes.

I'm not sure if I would count this under "algorithm", because the real problem is not the algorithm, but producing heuristics what makes a good set of useful items.
> 1 votes

---
Tags: algorithms
---


# Question
Title: A context-free grammar for a language of strings with occurrence properties?
Creating a context-free grammar for the language

$L\_1 = \\{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge m \equiv n \mod 3\\}$

is quite easy. A grammar is

$$ S \rightarrow \epsilon \mid 0A $$ $$ A \rightarrow 1 \mid 0B $$ $$ B \rightarrow 11 \mid 0S $$

But I am now trying to create a context-free grammar for

$L\_2 = \\{ w \in \\{0 ,1 \\}^{\*} \mid |w|\_1 \equiv |w|\_0 \mod 3 \\}$

Here, $|w|\_1$ denotes the number of occurrences of the character $1$ in the string $w$, and $|w|\_0$ is defined similarly.

How does one construct a context-free grammar? All my attempts have lead to completely wrong results. At the moment I am stuck.

# Answer
> 2 votes
Both $L\_1$ and $L\_2$ are regular languages. To construct a context-free grammar for them, you can first construct a DFA or NFA accepting them, and then convert it to a regular grammar.

# Answer
> 1 votes
Assuming you want the strings where m is the number of digits 1 in the string, n is the number of digits 0 in the string, and m = n modulo 3.

Have symbols that derive the following:

```
A -> "string where m = n modulo 3"
B -> "string where m = (n + 1) modulo 3"
C -> "string where m = (n + 2) modulo 3"
D -> "string where (m+1) = n modulo 3"
E -> "string where (m+1) = (n + 1) modulo 3"
F -> "string where (m+1) = (n + 2) modulo 3"
G -> "string where (m+2) = n modulo 3"
H -> "string where (m+2) = (n + 1) modulo 3"
J -> "string where (m+2) = (n + 2) modulo 3"

```

Now it's simple:

```
S -> A
A -> 0B | 1D |
B -> 0C | 1E
C -> 0A | 1F
D -> 0E | 1G
E -> 0F | 1H |
F -> 0D | 1J
G -> 0H
H -> 0J
J -> 0G |

```

---
Tags: formal-languages, finite-automata, formal-grammars
---


# Question
Title: Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers
I was just thinking about Turing-completeness and its relationship with modern computers. I've always thought that a real computer is not technically Turing-complete. It is equivalent to a linear-bounded automaton; a Turing machine has infinite memory, whereas a real computer has only finite memory.

However, you can add memory to a computer through expansion cards, external mass storage drives, etc. The limiting factor then becomes the maximum size of pointers. Obviously, a 64-bit CPU can store a 64-bit pointer in its general-purpose registers, and languages like C/C++ can easily be modified to support 64-bit pointers. However, I'm not sure if they would be able to manipulate arbitrarily large pointers, and thus an arbitrarily large address space.

My thoughts are as follows: Most modern CPUs include instructions that allow for arithmetic involving arbitrarily large integers. For example, the Intel architecture has the `ADC` and `SBB` instructions, where the carry flag from the last operation is added or subtracted from the result of the current operation. This allows for addition and subtraction of arbitrarily large numbers in a piecewise fashion.

Theoretically, this could also be done with pointers. Say you want to increment a 1024-bit pointer by some amount. You simply add an immediately addressed value to the pointer using the `ADC` instruction in 16 successive operations.

The problem comes when you actually have to dereference the pointer. Intel CPUs, and probably most other CPUs as well, are incapable of operating directly on variables in memory, while simultaneously being incapable of storing an entire arbitrarily large pointer in the registers all at once. You can't dereference a pointer in a piecewise fashion; you have to dereference the entire thing. So it all boils down to the question of whether a pointer can be dereferenced in this fashion. It has occurred to me that I don't actually understand how pointer dereferencing is done at the machine level, and I would like someone to explain how this works.

Of course, this question is of no practical importance, because simply having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence. I am simply interested in this question from a theoretical standpoint.

# Answer
> 1 votes
The universe is finite, so you can't build a *real* turing complete computer.

The best you can do is build a computer which observes whether the program it is running is getting close to the limitations of the computer, and when it exceeds them, builds a new, bigger computer, with higher limits, transfers the code to the new computer, and starts all over again.

PS. It is quite possible (and not really very difficult) to build a computer with 256 bit pointers. Since the universe is not just finite, but has a known size, 256 bit pointers are enough for anything.

# Answer
> 0 votes
Only in any a hardware specific systematic way that I have ever found and I have been looking for examples of anything like this for sometime. I am an amateur, you may well know most of this but here goes;

Computing numbers larger than the wordsize can accommodate is called "bignums" and, as been commented, there are various software solutions to making use of large numbers easily found with google.

There is floating point which basically uses however many bits to represent the number of digits in an exceedingly large or miniscule number but this representation is obviously inaccurate as it represents every one of them as a zero and therefore cannot be used as an address scheme.

"having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence" I believe it is about 8Tb. As far as I know the 4GB limit is for programs assigning a memory location and is restricted for system security issues.

I googled "dereferencing pointers at the machine level instruction set" and found there is no current machine that can surpass this mechanically as the mechanical limit is set by the number of wires. The hardware itself can only use the timing and control signals that have been built into it.

You can, however, decide on which number of bits each address points to in various ways.

Addressing Modes How are bits of an address ﬁeld interpreted to ﬁnd the operand?

1.Immediate addressing.

2.Direct addressing.

**3.Register addressing. Operand address is not contained in instruction but in a register**

4.Register indirect addressing.

5.Indexed addressing.

6.Based-indexed addressing.

7.Stack addressing.

8.Addressing modes for branch instructions

If you look to point at individual bits the overall address space will be much smaller than if your addressing scheme points to whole words i.e. 64 bits per address, effectively transforming all of memory into a very large array. This as a hardware implementation makes looking for or setting the value of any particular bit necessitate a mask.

The wordsize can be extended to arbitrary amounts, I have no doubt, in that an instruction can use one, two or three dwords of 32 bits each - that is 32, 64 or 96 bits. For example. Instructions must be aligned to dword addresses. The first two bits (most significant bits) of the first dword of an instruction indicates the length: 00 = 1 dword 01 = 1 dword 10 = 2 dwords 11 = 3 dwords so your instruction could be "11 ...." and have an address 3 words long but to balance the computational effort of various tasks and security of the system they are hardwired to specific sizes. I might be mixing things up some.

I personally have envisaged hardware with a systematic structure allowing the address scheme to accommodate an insane number of user defined geometric volumes where the defined space, net or cubespace can also define the complexity of the calculation in order to represent and relate massively parallel 3Dimentional co-ordinates, rotations, waveforms and whatever else but any questions I have proposed on the subject have been closed remarkably quickly.

Hope ive been helpful.

---
Tags: arithmetic, turing-completeness
---


title: Proving tautology with coq

text:
# Question
Title: Proving tautology with coq
Currently I have to learn Coq and don't know how to deal with an `or` :

As an example, as simple as it is, I don't see how to prove:

```
Theorem T0: x \/ ~x.

```

I would really appreciate it, if someone could help me.

For reference I use this cheat sheet.

Also an example of a proof I have in mind: Here for double negation:

```
Require Import Classical_Prop.

Parameters x: Prop.

Theorem T7: (~~x) -> x.
intro H.
apply NNPP.
exact H.
Qed.

```

# Answer
You cannot prove it in "vanilla" Coq, because it is based on intuitionistic logic:

> From a proof-theoretic perspective, intuitionistic logic is a restriction of classical logic in which the *law of excluded middle* and double negation elimination are not valid logical rules.

There are several ways you can deal with a situation like this.

* Introduce the law of excluded middle as an axiom:

```
Axiom excluded_middle : forall P:Prop, P \/ ~ P.

```

There is no more need to prove anything after this point.
* Introduce some axiom equivalent to the law of excluded middle and prove their equivalence. Here is just a few examples.
> 15 votes

# Answer
As others informed you, your tautology is not a tautology unless you assume classical logic. But since you're doing tautologies on decidable truth values, you could use `bool` instead of `Prop`. Then your tautology holds:

```
Require Import Bool.

Lemma how_about_bool: forall (p : bool), Is_true (p || negb p).
Proof.
  now intros [|].
Qed.

```
> 6 votes

---
Tags: logic, coq
---


# Question
Title: Proving the undecidability of a language knowing the language of polynomials evaluating to 0 is undecidable
Knowing **D={p|p is a polynomial evaluating to 0 for some assignment of integers to its variables}** is not decidable, how can I prove that **E={p|p is a polynomial evaluating to a prime for some assignment of integers to its variables}** is not decidable?

Proving that D is mapping reducible or Turing reducible to E would be enough, since if D \< E ( where \< means mapping reducible), then E decidable =\> D decidable, and using the contrapositive we get D not decidable =\> E not decidable.

Is showing that D is mapping or Turing reducible to E the right approach? I don't see how it can be proved. Thanks!

# Answer
> 2 votes
Yes like you say, you have to show that an algorithm that solves $E$ can be used to solve $D$.

A practical approach is to give a polynomial $p\_E$ for every polynomial $p$ such that $p$ evaluates to $0$ iff $p\_E$ evaluates to a prime number.

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


# Question
Title: what is the need for valid/invalid bit in paged memory technique?
How is the valid/invalid bit in paged memory useful? I am not able to understand the significance. Is it also somehow used to share the processes among different users.

# Answer
> 7 votes
In a typical multilevel page table implementation on a typical modern operating system, any attempt to access memory for a page whose page table entry set to "invalid" (typically 0) causes a page fault. This is a hardware trap which transfers control to the operating system.

The most obvious use for this is to represent a region of address space for which there is genuinely nothing there. When a user-space application starts, it will have some of its virtual address space allocated (e.g. for program text, data, BSS, stack, etc). Additional memory (e.g. memory for heap storage or memory-mapped files) needs to be requested from the operating system. This means that a lot of the address space of the process is "blank", and any attempt to access those addresses should fail. The page table entries for these addresses are therefore marked as invalid.

(As an aside, most modern operating systems also use this to support the NULL pointer in C. The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system. Even the first 1MB is not unknown.)

An alternative way to think of the validity bit is that if a program tries to access an invalid page, this causes a trap to the operating system. So the question you might want to ask is: Why would an operating system want that?

One use is to represent a page which is valid (in the sense that it is correct for the user program to access that address) but not currently backed by a physical page. For example:

* Demand-paged memory, where the address represents part of a memory-mapped file (that might include the program that is running), or a page that has been swapped to secondary storage. In this case, attempting to access the memory causes the operating system to read in the data before the program continues.
* Most modern operating systems support zero-fill memory. When an application allocates memory, the typical default is that this is not backed by physical memory until it is first used. The way this is supported by using the invalid bit.
* A related idea is copy-on-write memory, which is used (for example) to implement fork() in Unix.

And there are a bunch of related operating system housekeeping-like tasks for which manipulating the valid bit is useful. For example:

* Paging out memory requires detecting what pages have been recently used so that infrequently used pages can be paged out. One way to do this is to mark the page as invalid for a short time. If the page is used in that time, operating system knows that it was accessed because a page fault occurred. (Modern Intel CPUs have a more efficient mechanism for this, but the valid bit works if you're using a CPU where that isn't supported.)
* An operating system will often mark a dirty page (e.g. a modified page which represents a memory-mapped file) as invalid while it is being flushed to secondary storage. Any program which tries to modify a page which is in the process of being flushed should wait until the write is complete, so that the data being written is in a known state.
* Operating systems can use the validity bit to help debuggers. Many modern debuggers let you set a breakpoint which fires if a certain variable is read or modified. One way to implement this is through the page fault mechanism.

Basically, any time that it would be useful to handle a memory operation by trapping to the operating system is a time when it would be useful to mark a page as invalid.

---
Tags: operating-systems, memory-management
---


# Question
Title: Condition for perfect matching in bipartite graphs
Let $G = (S, T, E)$ be a bipartite graph without isolated vertices.

For each edge $e ∈ E$, $e = st$ (where $s ∈ S$, $t ∈ T$), the inequality $d\_G (s) ≥ d\_G (t)$ holds. Prove that there is a matching in $G$ saturating all of $S$'s vertices.

# Answer
Here is a proof for the following related result:

> A $d$-regular bipartite graph contains a perfect matching.

According to Hall's criterion, a perfect matching exists if for all $A \subseteq S$, $|N(A)| \geq |A|$. Take any $A \subseteq S$. There are $d|A|$ edges connecting vertices in $A$ to $T$. A given vertex $t \in T$ can be the target of at most $d$ such edges. Hence there are at least $d|A|/d = |A|$ such targets, that is, $|N(A)| \geq |A|$.

Try modifying this proof for your case.
> 2 votes

---
Tags: graphs
---


# Question
Title: Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?
A CFG is in strong GNF when all rewrite rules are in the following form:

$A \rightarrow aA\_1...A\_n$

where $n \leq 2$.

# Answer
> 2 votes
Such an algorithm is described in Koch and Blum, Greibach Normal Form Transformation, Revisited.

---
Tags: formal-languages, context-free, formal-grammars, normal-forms
---


# Question
Title: How to define an approximation algorithm when it fails?
I have an NP-hard problem P where we are trying to minimize some objective function subject to some constraints. Problem P is very hard in the sense that even finding *a feasible solution* is NP-hard! (i.e., finding a solution that satisfies the constraints is NP-hard).

Let OPT denotes the optimal algorithm for P. That is, OPT will return, given an instance of P, the best possible solution, or will report none exist. Now, suppose I designed an approximation algorithm, denoted ALG, that solves P (of course not to optimality).

Given an instance I1 of P, ALG may fail to find a feasible solution when actually one exists and of course OPT finds it. So, if I would like to measure the performance of ALG in terms of its approximation ratio, how would I do that? Should I ignore the instance I1? As far as I know, an approximation algorithm, by definition, must return, **for any instance of the problem**, a solution that has a bounded value compared to the optimal value. But in this case, given an instance of P, ALG may not be able to find any value and hence reports none.

For short, if an algorithm fails to find a solution to a problem, how do we measure its performance ratio? Is it even considered an approximation algorithm? Is there something related to this in the literature?

# Answer
> 3 votes
The usual way out in such circumstances is *bicriteria approximation algorithms*. Suppose that given a set of possible solutions $S$, a constraint function $f$, and an objective function $g$, your goal is to find a solution $x \in S$ such that $f(x) \leq 1$ minimizing $g(x)$. A bicriteria approximation algorithm will find a solution $x \in S$ such that $f(x) \leq \alpha$ and $g(x) \leq \beta \mathrm{OPT}$, where OPT is the optimal solution to the original problem.

The quality of bicriteria approximation algorithms is thus measured by *two* parameters. The parameter $\beta$ corresponds to the approximation ratio, and $\alpha$ controls by how much the solution violates the constraints.

---
Tags: algorithms, approximation
---


# Question
Title: Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?
So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division.

For these operations/operators, we have some properties like commutativity, associativity and distributivity.

Is there an analogue set of properties for the operations/operators on that we do with Regular Expressions?

I also believe that the set of all regular expressions together with its operations that are defined on the members of regular expression set form an algebraic structure similar to the integers and common operators that we learn about at arithmetics.

# Answer
> 2 votes
There are several known axiomatizations of the *equational theory of Kleene algebra*, see lecture notes from a course by Dexter Kozen. These axiomatizations give you a complete set of rules that can be used to deduce any identity involving regular expressions. The first ones were given in a classic paper of Salomaa, and others are also known.

---
Tags: formal-languages, regular-languages, automata, formal-grammars, regular-expressions
---


# Question
Title: deterministic finite automaton for "does contain substring $w$" is of linear size
A (non-deterministic) finite state automaton for "all strings that contain substring $w$" is very simple. Just make the path for $w$ and add looped transitions for all letters at the first initial state and the last final state.

When asked to make a deterministic automaton in general we might expect that the automaton can be of exponential size (see the warning of Yuval in the case where $w=101$: Write a regex to match string that does NOT contain a certain pattern).

However, Knuth-Morris-Pratt tells us that a pattern match automaton for $w$ is of linear size, and can be constructed in linear time. That means that the deterministic automaton for "contains substring $w$" is of linear size too (failure links can be replaced by transitions, on for each mismatching letter). Luke has used KMP to provide an automaton for the example "not ABCDABD" in his answer Automaton for substring matching.

My question is the following: **will the standard determinization of a "substring $w$" automaton always lead to a linear sized automaton?** Here I mean the practical version of the construction, where unreachable states are not constructed (so not the full $2^Q$ subset construction). Is the answer direct from the construction, or do we need KMP?

A little observation. In the construction there might be many states that contain the original final state. As they all will accept and also all transitions for ever will lead to accepting states (once we have seen $w$) these states can be grouped into one single state. I do not know whether that is a necessary trick to avoid exponential explosion, see https://cs.stackexchange.com/a/11842/4287

# Answer
> 2 votes
Consider the following NFA: the states are $q\_0,\ldots,q\_{|w|}$, there are transitions $q\_{i-1} \to q\_i$ on $w\_i$, there are self-loops on $q\_0,q\_{|w|}$ (for all alphabet symbols), the initial state is $q\_0$, and the unique final state is $q\_{|w|}$.

Assuming $w \neq \epsilon$, the determinization generates $2|w|$ states:

* For each location $0 \leq i \< |w|$, a state consisting of $q\_0$, $q\_i$, and $q\_j$ for $j \< i$ such that $w\_1\ldots w\_j$ is a suffix of $w\_1\ldots w\_i$.
* Same as before, with $q\_{|w|}$ added.

When $w = \epsilon$, the NFA is already deterministic, and contains only one state.

---
Tags: finite-automata, nondeterminism, pattern-recognition
---


# Question
Title: what is variable capture in nominal logic?
While reading a paper Nominal Unification from a Higher-Order Perspective, in the abstract I noticed something feel bit confusing,

> Nominal Logic is an extension of first-order logic with equality, name-binding, name-swapping, and freshness of names. Contrarily to higher-order logic, bound variables are treated as atoms, and only free variables are proper unknowns in nominal unification. This allows “variable capture”, breaking a fundamental principle of lambda-calculus.

I know a bit about nominal logic, but as I know it respects $\alpha$-conversion, such as $\lambda x.x \approx\_\alpha \lambda y.y$. but I could not understand above statement.

I understand the notion of variable capture which leads to a wrong result during the substitution.

So does variable capture not lead to an incorrect result in nominal logic?

what does it mean saying breaking "variable capture" here?

Can anyone explain with examples?

# Answer
Variable capture is the phenomenon which "breaks" things when you do your substitutions in a naive way. For example:

1. **Correct:** in the expression $$\int\_0^1 (a + x)^2 dx$$ substitute $t^2$ for $a$, to get $$\int\_0^1 (t^2 + x)^2 dx.$$
2. **Correct:** in the expression $$\int\_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int\_0^1 (t^2 + u)^2 du$$ (we renamed the bound variable $t$ to $u$ on the fly to avoid capturing $t$).
3. **Incorrect:** in the expression $$\int\_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int\_0^1 (t^2 + t)^2 dt.$$ (We ended up with a different intergral because $t$ was *captured* by $dt$).

Similarly, in $\lambda$-calculus:

1. **Correct:** $(\lambda x . \lambda y . y x)) y = \lambda z . z y$
2. **Incorrect:** $(\lambda x . \lambda y . y x)) y = \lambda y . y y$ (because $y$ was captured).
> 5 votes

# Answer
I find out it. in the higher-order unification, some function is found for variable $X$ such as $ \[X \mapsto \lambda y.y \]$, substituting this for $X$ will not lead to variable capture.

in nominal unification, $\lambda a.X \approx \lambda b.b$ yields substitution $\[X \mapsto a\]$, applying this to original problem yields $\lambda a.a \approx \lambda b.b$ where $a$ is captured.
> 1 votes

---
Tags: programming-languages, logic, variable-binding
---


# Question
Title: Branch and bound for minimum linear arrangement
I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.

Let's say $G$ is a graph of $n$ nodes $\\{1, 2, 3, \ldots , n\\}$. For a permutation $f$ of the nodes of $G$, the weight of each edge $(x,y)$ will be $|f(x)-f(y)|$. The total weight of $G$ will be the sum of the weights of its edges. You can think of $f$ as a relabeling of the nodes of $G$, where $f(x)$ is the new label of node $x$.

I am trying to find a permutation $f$ that results in a minimum total weight of $G$.

Now trying to solve this, all I could come up with is finding the approximate cost that is the sum of weights of each edge completed till now (for each backtracking tree node) and proceed from the minimum cost node. I am wondering if someone can help me with a better approximation formula.

# Answer
> 7 votes
One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage it yourself.

I have seen it solved in two ways using this technique. We can slightly improve your bounding algorithm as well.

## The textbook method

Using binary variables $x\_{ij}$ representing $f(i) = j$, you can define continuous variables $f(i) = \sum\_{j=1}^n j x\_{ij}$

Add constraints $\sum\_i x\_{ij} = 1$ and $\sum\_j x\_{ij} = 1$ representing that one position is assigned one and only one node.

For each edge, the cost $c\_e$ has two constraints : $c\_e \geq f(i) - f(j)$ and $c\_e \geq f(j) - f(i)$, and you want to minimize $\sum\_e c\_e$

You can give this problem to an integer programming solver, which will be happy to do the backtracking for you and more - or you can solve the linear programming relaxation yourself each time (just if you want to learn, the solver optimizes it internally).

## Another relaxation

Instead of using the positions as binary variables, you can use $f(i) \< f(j)$ i.e. node $i$ goes before node $j$. This is more adapted if you want to do the branching yourself and don't specify those variables explicitly.

With this approach, you can sometimes have a faster problem to solve at each node - here it can be solved as a simpler minimum-cost flow problem as shown by this paper. I wouldn't recomment it unless you are willing to investigate much time and research into your problem.

## Other techniques

For branch-and-bound, any **lower bound** on your cost function will do. For small problems your bounding approach is perfectly fine.

You could make it tighter: for each edge with an unplaced node, pick the best possible free labeling to estimate its cost. Several edges may use the same placement for different nodes, but this will be better than estimating their cost as 0.

There are many possible variations on this scheme: pick the best free label for each unlabeled node (irrespective of overlaps) or consider overlaps only inside small groups of nodes.

---
Tags: algorithms, graphs, optimization, backtracking, branch-and-bound
---


# Question
Title: Why is A implies B true if A is false and B is false?
It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday language use.

Let's take two examples:

> If today is Monday then tomorrow is Tuesday.

This is *true*.

But if we say:

> If the sun is green then the grass is green.

This is also considered true. *Why?* What is the 'logic' in natural English behind this? It blows my mind.

# Answer
> 41 votes
Humans are bad at logic until they have to employ it to figure out human affairs. Think of "*if $A$ then $B$*" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would *not* make me a liar.

For instance, suppose your mother tells you:

> *If you clean up your room I will make pancakes.*

And let us say that you did not clean up your room, but when you walked into the kitchen your mom was making pancakes. Ask yourself, whether this makes your mom a liar. It does not! She would be a liar only if you cleaned the room but she refused to make pancakes. There might be other reasons that she decided to make pancakes (perhaps your sister cleaned up her room). Your mom did not tell you "If you do not clean up the room I will not make pancakes," did she?

So, if I say

> "If the sun is green then the grass is green."

that does not make me a liar. The sun is not green (you did not clean up the room), but the grass turned out to be green anyhow (but your mom made pancakes anyhow).

# Answer
> 16 votes
It's a convention -- we could use a different one, but this one is convenient. Here's what Terence Tao says:

> This is discussed in Appendix A.2 of my book \[Analysis 1\]. The notion of implication used in mathematics is that of material implication, which in particular assigns a true value to any vacuous implication. One could of course use a different convention for the notion of implication, however material implication is very useful for the purpose of proving mathematical theorems, as it allows one to use implications such as “if A, then B” without having to first check whether A is true or not. Material implication also obeys a number of useful properties, such as specialisation: if for instance one knows for every x that P(x) implies Q(x), then one can specialise this to a specific value of $x$, say 3, and conclude that P(3) implies Q(3). Note though that by doing so a non-vacuous implication can become a vacuous implication. For instance, we know that $x \geq 5$ implies $x^2 \geq 25$ for any real number $x$; specialising this to the real number 3, we obtain the vacuous implication that $3 \geq 5$ implies $3^2 \geq 25$.
>
> The way I like to think of material implication is as follows: the assertion that A implies B is just saying that “B is at least as true as A”. In particular, if A is true, then B has to be true also; but if A is false, then the material implication allows B to be either true or false, and so the implication is true no matter what the truth value of B is.

# Answer
> 10 votes
"A implies B" means (short) "if A is true then B is true".

It means (a bit longer) "if A is true then I claim that B is true; if A is false then I don't make any claim about B whatsoever".

Now take "If the sun is green then the grass is green".

In the long form it is translated to "If the sun is green then I claim that the grass is green; if the sun is not green then I make no claim about the color of grass whatsoever". The sun is not green, so I make no claim about the color of grass whatsoever.

# Answer
> 6 votes
Let's take an example. Suppose that we want to express that $a$ is the only element of the set $S$ that satisfies property $P$. Then we can write $$ \forall x \in S \\;\\; P(x) \Rightarrow x = a $$ This states that any element of $x$ that satisfies $P$ must be equal to $a$. It doesn't claim anything about elements not satisfying $P$. If $b$ doesn't satisfy $P$ and is different from $a$ then $P(b)$ is false and $b = a$ is false, and so $P(b) \Rightarrow b = a$ is true, just as in your example.

# Answer
> 4 votes
It's important to note that many forms of logic have no concept of chronology or causality. If something is true, then it will--within its context--have been and continue to be true forever. Saying that X implies Y does not mean in any sense that X will in any way cause Y to be true. It merely means that X cannot be true without Y also being true, and Y cannot be false without X also being false.

To usefully describe causal relationships in the real world requires something beyond the constructs used in "timeless" logic. A concept like "For any action Y such that X would *cause* Y to be reasonable, Y shall be deemed reasonable" can be useful in a causal universe even if X might be false, but the implication operator completely blows up in such cases. If one were to say "X implies that Y shall be deemed reasonable" and it turned out that X was never true, that would imply that *all* actions shall be deemed reasonable.

I'm not sure what forms of logic include the constructs necessary to allow statements involving one-way causality, but recognizing that the logical definition of "implies" does not recognize the concepts of time and causality should make it easier to understand why they behave in counter-intuitive fashion.

# Answer
> 1 votes
While using Implication In English it not about the things or objects we consider.

Like in your given example which is blowing you mind is that If the $sun$ is $green$ and then $grass$ is $green$.

Sun is just is an object here, don't make any emotional attachments to it, that a sun can't be green.

You can just replace sun with a book or a letter $S $, green with $G$ and grass with $GG$. Now see the sentence If the S is G then GG is G.

{{S-\>G} $-\>$ {GG-\>G}}

This seems less confusing then while writing in English.

# Answer
> -1 votes
To put your head in the right place for my answer, I want to mention what I like to call the Flying Monkeys Theorem, or what Wikipedia likes to call the Principle of Explosion, which states:

$$ (p\wedge\neg p) \rightarrow q $$

Or, in English, this says "given a contradiction, monkeys might fly out of my butt (NSFW audio)", or alternately "from falsehood, anything follows". One way to think about this is that if $2+2=4$ *and* $2+2=5$ then $4=5$, which means that $0=1$, or it could mean that $16=25$, etc., and you can basically generate any equality you want. This is why there are so many tricks that result in $1=0$ or $1=-1$ by abusing a hidden division by zero, because you are not allowed to divide by zero so you can make anything you want true.

---

Once we're in this realm where we **know** $p$ is false, we're no longer in reality. We're in some alternate dimension where the Babel Fish is real, black is white and watch out for that Zebra crossing. So given that we're no longer in reality, of course the statement could be true. Specifically, **I can use my false thing that I'm assuming to prove anything I want.** So of course $F \rightarrow T$ and $F \rightarrow F$ are both true statements.

---
Tags: terminology, logic, first-order-logic, propositional-logic
---


# Question
Title: Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?
So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact.

Can we use some sort of techniques on regular expressions to make them more simpler?

For example what is the relation between concatenation and kleene star? If we have a concatenation with an union between two expressions that have kleene star can we draw a conclusion using some sort of property to distribute the concatenation somehow or do something else. I just started learning this subjects and I may not be very good at expressing what I think right now.

# Answer
Minimizing regular expressions is very hard, see for example a paper of Gramlich and Schnitger, who show that no $o(n)$ approximation algorithm exists unless P=PSPACE. Another type of answer to your question is the formal systems mentioned in my answer to your related question.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, formal-grammars, regular-expressions
---


# Question
Title: Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$
How can I prove that the language $L=\left\\{\langle M\rangle\mid L(M)=\left\\{\langle M\rangle\right\\}\right\\}$ is not decidable?

When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\\{\langle M\rangle\right\\}$ that $\langle M\rangle\not\in L(M)$.

Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.

Is there an easy reduction to a known undecidable language?

# Answer
> 4 votes
The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.

Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \\{ \langle M' \rangle \\}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.

---
Tags: turing-machines, reductions, rice-theorem
---


# Question
Title: "P may collapse" vs. Time hierarchy theorem
https://en.wikipedia.org/wiki/P\_versus\_NP\_problem states:

> If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level.

They further state that this may be unlikely, but at least it's a possibility. However, https://en.wikipedia.org/wiki/Time\_hierarchy\_theorem states:

> The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME($n^k$) for any fixed k. For example, there are problems solvable in $n^{5000}$ time but not $n^{4999}$ time.

Why don't the above two quotes contradict each other?

# Answer
> 5 votes
The time hierarchy theorem only says that P does not collapse to $DTIME(n^k)$, that is, it says that giving one deterministic Turing Machine more time than another deterministic Turing Machine gives it more power. There is an analogous theorem for nondeterministic Turing Machines, called the Nondeterministic Time Hierarchy Theorem, which implies that NP does not collapse to $NTIME(n^k)$ for any fixed $k$.

The P vs NP question, however, it about how deterministic Turing Machines relate to nondeterministic Turing Machines. Just for clarity, the sets are defined as follows:

$$P = DTIME(poly)= \bigcup\_{k\in \mathbb{N}} DTIME(n^k) \\ NP = NTIME(poly) = \bigcup\_{k\in \mathbb{N}} NTIME(n^k)$$

For example, if P=NP, then we may find out that for all $k:\ NTIME(n^k)\subseteq DTIME(n^{7k})$. (Note that even if this is true, P still does not collapse to $DTIME(n^k)$ for any fixed $k$.) The polynomial hierarchy, which you refer to, informally, is a way to obtain more classes from P and NP by going "up" to more difficult problems in much the same way that we went from P to NP. Asking whether it collapses to its second level is the same as asking the P vs NP question, but for the higher level. For example, asking whether the polynomial hierarchy collapses to its second level is to ask how $ATIME(poly, 2)$ relates to $ATIME(poly, 3)$, with $ATIME(t(n), a(n))$ the set of languages decidable by an alternating Turing Machine in $t(n)$ time and using $a(n)$ alternations, with $P=ATIME(poly, 0)$ and $NP=ATIME(poly, 1)$, where the Alternating Turing Machine is something interesting enough to read up on this Sunday afternoon ;)

# Answer
> 6 votes
The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.

---
Tags: complexity-theory, polynomial-time, p-vs-np
---


# Question
Title: How does literals in compiled languages differ from literals in interpreted languages?
A **literal** is a piece of data which gets its value at compile time.

Means: Becomes set at compile time and afterward the value is fixed incorporated into the machine code as a code consisting out of 0s and 1s.

**What are literals in interpreted languages like for example JavaScript?**

As far as I know the code within JavaScript functions aren't touched by the interpreter until it becomes executed.

**Can one say that literals exists in these languages?** regarding my definition of a literal (first paragraph).

# Answer
> 2 votes
> A literal is a piece of data which gets its value at compile time.

I don't think that's a good definition of literals. A literal is a source-code token that represents a fixed value of some type. For example, in almost all programming languages, `23` is a literal representing the integer twenty-three. These aren't pieces of data that get their value at compile-time: rather, they are representations of the values themselves. For example if, in Java, you write

```
static final int magic = 23;

```

then `magic` is a constant (a variable whose value cannot be changed) that is set at compile-time to have the value twenty-three, which is the meaning of the literal `23`.

This is no different between compiled and interpreted languages.

---
Tags: compilers, interpreters
---


# Question
Title: weight balanced binary tree vs height balanced binary tree
What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?

# Answer
The way to answer your question is to find the peer-reviewed papers that first described the trees (or that later chose to reference them) and read their explanations of why the authors felt the need to invent a new tree.

Generally speaking, weight-balanced trees have the property that restructuring operations on a node with $n$ descendants happen every $O(1/n)$ operations. This is good because sometimes these trees are used in an augmented way so that restructuring operations take $\omega(1)$ time. In some height-balanced trees, restructuring operations can happen every operation, while in others they happen every $2^{-O(\lg n)}$ operations, which is slightly weaker than $O(1/n)$.
> 3 votes

---
Tags: trees, binary-trees, balanced-search-trees
---


title: Context free grammar issue at pda

text:
# Question
Title: Context free grammar issue at pda
I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata.

The automaton accepts all strings over alphabet $\\{e,k,q,y\\}$ of the form $w\\,kyyk\\,w'$ such that $|w|=|w'|$.

There are the productions rules I get.

```
S -> QkyykK
Q -> qQ
Q -> yQ
Q -> eQ
Q -> kQ
Q -> epsilon

K -> Kq
K -> Ky
K -> Ke
K -> Kk
K -> epsilon

```

I don't understand how to have the same number on the left and on the right. Hope anyone can help me or explain me cause I am having so problems with that exercice. I use jflap for testing if it's accepted or rejected.

# Answer
> 1 votes
You enforce the property of having an equal number of characters to the left and the right by only having rules that add an equal number of characters.

At the moment, your approach is essentially, "Start with $kyyk$ and add stuff to the left and the right." In this case, "stuff" is the non-terminal symbols $K$ and $Q$, each of which can expand to any string in $\Sigma^\*$. Whenever you're expanding two non-terminals in a context-free language, they're expanded completely independently, so there's no way to control their interaction, e.g., to require that both strings have the same length. This means that the approach of generating the left-stuff and right-stuff from two non-terminal symbols can't work.

Instead, you need to take the opposite approach. Start with nothing and simultaneously expand the stuff on the left and right.

# Answer
> 1 votes
As David correctly noted, you work from the outside in, adding a single character to the left and the right sides. Here's a simpler example: suppose you want all strings over $\\{a,b\\}$ of the form $wabw'$ where $|w|=|w'|$. This grammar will do what you want: $$\begin{align} (1)\quad S&\rightarrow aSa\\ (2)\quad S&\rightarrow aSb\\ (3)\quad S&\rightarrow bSa\\ (4)\quad S&\rightarrow bSb\\ (5)\quad S&\rightarrow ab\\ \end{align}$$ Every one of the first four productions will generate strings of the form $xSy$ where $x$ and $y$ are single characters, and production (5) will eventually replace the variable $S$ with the "central" string $ab$. For example, to generate the string $bab\ ab\ aaa$ we could do this derivation: $$ S\stackrel{(3)}{\Longrightarrow}bSa\stackrel{(1)}{\Longrightarrow}baSaa\stackrel{(3)}{\Longrightarrow}babSaaa\stackrel{(5)}{\Longrightarrow}\underbrace{bab}\_wab\underbrace{aaa}\_{w'} $$ It's clear that in each of the steps in the derivation $w$ and $w'$ will always have the same length and can consist of any strings over the alphabet, which is exactly what you need. In your example, with a four-character alphabet, you'll need 17 productions: 16 for all possible combinations of the four characters on the left and right sides, plus one more to get the $kyyk$ in the middle.

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


# Question
Title: Classification of technologies used for communication in distributed systems
I am currently writing a State of Art about technologies used for distributed communication (like CORBA for example). I want to structure the document in way that I don't leave any subset of this technologies out of the research. My proposed solution is to structure the document by Communication Paradigms:

* Interprocess Communication
* Remote Invocation
* Indirect Communication

Am I missing a paradigm? Are there another classifications that could be usefull for structure the document? Also if you can recommend me a good source to read about this topic, I would really apreciate it.

# Answer
Finally I decided to classify the distributed system technologies by the communication paradigm that they implement. The categories of communication paradigms I considered are:

* Remote Procedure Call
* Berkeley Sockets
* Message Passing Interface
* Message Oriented Middleware
* Distributed Shared Memory
* Stream Oriented Communication
* Multicast Communication (based in peer-to-peer architecture)

I still have to do some research about some more modern implementations that can eventually use a paradigm not listed here.
> 1 votes

---
Tags: reference-request, distributed-systems, communication-protocols, research
---


title: What does a wedge in a graph look like?

text:
# Question
Title: What does a wedge in a graph look like?
I am reading Decompositions of Triangle-Dense Graphs by Gupta et al.

On page 2, in Definition 1 what is a wedge in a graph?

I know what triangle is but I don't know what wedge is and google isn't helping!

# Answer
> 6 votes
They say it in the paper.

> Let a wedge be a two-hop path in an undirected graph.

So it is a path with 2 edges, like 2/3 of a triangle.

# Answer
> 3 votes
Right before the definition the authors define a *wedge* to be a two-hop path in an undirected graph. After the definition, they note that every triangle of a graph contains 3 wedges. In other words, with a wedge they mean a path $P\_3$.

# Answer
> 0 votes
A nice and easy explanation of wedges is available the paper "Triadic Measures on Graphs: The Power of Wedge Sampling" SDM, 2013.

---
Tags: graphs, terminology
---


# Question
Title: Is a set of TM deciding specific length of language reducible?
For instance, if we know a language $L\_1 = \\{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n \\} $ is decidable, can we prove that $ L\_2 = \\{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n-1 \\}$ is also decidable? In other words, prove $L\_2$ reduces to $L\_1$.

# Answer
> 0 votes
Here is a similar example, to get you started. Let $L\_n$ consist of all encodings of Turing machines that accept some string of length $n$.

> Claim: $L\_{n-1}$ reduces to $L\_n$.
>
> Proof: Let $M$ be an input to $L\_{n-1}$. Construct a new machine $M'$ which on input $x$, if $x$ starts with a zero then $M'$ rejects, and if $x=1y$ then $M'$ simulates $M$ on $y$. Then $\langle M \rangle \in L\_{n-1}$ iff $\langle M' \rangle \in L\_n$ (exercise).

Your proof will be different, but the proof technique will be similar.

---
Tags: turing-machines, reductions
---


# Question
Title: How does the following truth table show Y's behaviour?
a b c Y
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 1 0
1 1 0 0

How would you put this into a logical expression that shows Y's behaviour?

# Answer
Giving an example of what **Eugene** has said, but letting you do your own homework. Let's look at another Truth Table:

$ \begin{array}{|c|c|c|c|} \hline a& b & c & \varphi \\ \hline 1 & 1& 1& 1\\ \hline 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 0 & 1\\ \hline 0 & 0 & 1 & 0 \\ \hline 0 & 0 & 0 & 1 \\ \hline \end{array} $

To put it on **DNF** just look at the rows which evaluate to **True**.

$ \begin{array}{|c|c|c|c|c|} \hline a& b & c & \varphi & \\ \hline 1 & 1& 1& 1 & a \wedge b \wedge c \\ \hline 1 & 1 & 0 & 1& a \wedge b \wedge \lnot c \\ \hline 1 & 0 & 0 & 1& a \wedge \lnot b \wedge \lnot c \\ \hline 0 & 1 & 0 & 1& \lnot a \wedge b \wedge \lnot c \\ \hline 0 & 0 & 0 & 1& \lnot a \wedge \lnot b \wedge \lnot c \\ \hline \end{array} $

So the **DNF** of $\varphi$ is : $$ (a \wedge b \wedge c) \vee (a \wedge b \wedge \lnot c) \vee (a \wedge \lnot b \wedge \lnot c) \vee (\lnot a \wedge b \wedge \lnot c) \vee (\lnot a \wedge \lnot b \wedge \lnot c) $$

To put it on **CNF** just look at the rows which evaluate to **False**. Now just negate those rows to get **True**.

$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline a& b & c & \varphi & & & \lnot \varphi & \\ \hline 1 & 0 & 1 & 0 & a \wedge \lnot b \wedge c & & 1 & \lnot a \vee b \vee \lnot c\\ \hline 0 & 1 & 1 & 0 & \lnot a \wedge b \wedge c & & 1 & a \vee \lnot b \vee \lnot c\\ \hline 0 & 0 & 1 & 0 & \lnot a \wedge \lnot b \wedge c & & 1 & a \vee b \vee \lnot c\\ \hline \end{array} $

So the **CNF** of $\varphi$ is:

$$ (\lnot a \vee b \vee \lnot c) \wedge (a \vee \lnot b \vee \lnot c) \wedge (a \vee b \vee \lnot c) $$
> 4 votes

# Answer
You can write either CNF or DNF from the truth table directly and then transform it to any form you like opening brackets and possibly using absorption rule.
> 1 votes

# Answer
# Define `Y` as:

```
|&A!B&C!A

```

If you can't understand it, then here is a more readable version:

```
Y = (((A) AND (NOT B)) OR ((C) AND (NOT A)))

```

# Explanation

If either:

* A = 1 and B = 0
* C = 1 and A = 0

Then Y = 1. Else, Y = 0.
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: Difference between ways to compare floating-point numbers
There seems to be many approaches to judge whether two floating-point numbers are identical. Here are some examples I've found:

1. `fabs(x - y) < n * FLT_EPSILON * fabs(x)` OR `fabs(x - y) < n * FLT_EPSILON * fabs(y)`
2. `fabs(x - y) < n * FLT_EPSILON * fabs(x + y)`
3. `fabs(x - y) < n * FLT_EPSILON * fabs(x + y) || fabs(x - y) < FLT_MIN)`
4. `fabs(x - y) < n * FLT_EPSILON * sqrt(x * x + y * y + FLT_EPSILON * FLT_EPSILON)`

I'm really confused about them. Suppose there is a best way to compare two floating-point numbers, which is the simplest as well as the most accurate, the other approaches shouldn't even exist. So these different ways must have there own pros and cons.

My question is: To do "real computations", which approach is the most **accurate** one?

---

Reference links:

http://accu.org/index.php/journals/1558 (1 and 4)

https://stackoverflow.com/a/10335601/5399734 (2 and 3)

# Answer
> 2 votes
You are rightfully confused, because these answers mix up incompatible concepts into a right mess.

If you want to know whether two floating point numbers are equal then you use the "==" operator, which will tell you absolutely correctly whether they are equal.

If you want to know whether they are identical, that's slightly more tricky: There are +0 and -0 which are equal but not identical, and there are NaNs (Not-a-Number) which are not equal, not even equal to themselves, but can be identical.

Now if you perform floating-point arithmetic, then it can happen that two calculations that should have given the same mathematical result do give different results due to rounding errors. It can also happen that two calculations that should have given different mathematical results do give the same result.

**There is no quick and easy rule**. You need to think about what your goal is, and how to achieve it. And every case is different.

PS. (4) is just awful. Totally, totally wrong. If you use double precision and one of x, y is greater than 10^160, then almost any two numbers will be considered "equal" by this code.

PS. (1-3) are equally awful, because they claim that 0 ≠ 0.

PS. (3) is awful - it completely destroys the idea of gradual underflow.

PS. As a rule, you should use double precision instead of single precision, unless you have a very good reason not to; a reason that you can explain and defend.

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


# Question
Title: How do you read this context-free language?
say you want to make a Pushdown Automaton to recognize this language.

What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I don't quite get why.

# Answer
> 0 votes
The language defined as $\\{a^ib^j\mid 2i=3j+1\\}$ is just the set of all strings of $i$ copies of $a$ followed by $j$ copies of $b$, **where** $2i=3j+1$. Trying various values of $i$ and $j$ and realizing that both $i$ and $j$ must be integers, we see that the admissible solutions are $$ (i,j)=(2, 1), (5, 3), (8, 5), (11, 7), \dotsc $$ For example, with $i=5, j=3$ we see that $2i=2(5) =10=3(3)+1=3j+1$. The corresponding strings are $$ aab,\quad a^5b^3,\quad a^8b^5,\quad a^{11}b^7 \dotsc $$ and so on.

With a bit of thought, we can make a PDA for this language by pushing two $a$ markers on the stack for each $a$ we read and then popping off three $a$s for each $b$ we see. If we wind up with a single $a$ on the stack after having read all the $b$s, we pop that off and go to the accept state.

---

It's worth noting that the PDA you picture does not accept the language described. That one accepts the language $\\{a^nb^{2n-1}\mid n\>0\\}$.

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


# Question
Title: Dynamic Programming - How to get the solution from the predecessor matrix
Whenever I'm coding a dynamic program , I usually struggle building the solution from the predecessor matrix . How should use the predecessor matrix to find the solution ?

Thanks,

# Answer
That depends a lot on the question, really. But basically, since you have the values of the all your "sub-problems", and you know your formula for the problem (Meaning, how the current problem is solved using the optimized solutions for the smaller problem), you can just check which cells (That are possible optimized solutions) in the matrix satisfy this formula.

Then, you can know that this cell is part of the solution.

Continue this way from top to bottom - and you'll get your whole solution (And not just the value, which is I guess was your problem).
> 3 votes

---
Tags: dynamic-programming
---


# Question
Title: Nim Games: Is it possible to reduce following using Grundy Number?
Following is the problem from a finished programming contest.

> Two players try to create a number, DesiredTotal, by adding numbers from 1 to N. The first to cross the number is the winner. The number to be added cannot be repeated. For example, if one player used 4 to increase the sum from 20 to 24, the neither player can use 4 again in the game.

Now I understand how the above problem could be solved using dynamic programming by exploring all the possible paths and memoizing the solution, but the game being impartial still qualifies to be a Nim game.

Am I correct that, it is a Nim game? If yes, could somebody help me to reduce into a Nim game?

Below is the source but it requires signing in.

Theory: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Source: https://leetcode.com/contest/leetcode-weekly-contest-10/problems/can-i-win/

# Answer
> 2 votes
Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the sum as well as the current set of allowed addends. You can compute the Grundy function, which gives the equivalence to Nim, using dynamic programming.

---
Tags: game-theory
---


# Question
Title: Number of different binary search trees storing n distinct keys?
How many different binary search trees are possible that store the values 1,2,...,n ?

So far I found a recursive formula for the number (by case distinction what's at the root):

$ T(n) = 2T(n-1) + \sum\_{i=2}^{n-1}T(i-1)T(n-i), n \> 1 $ and $ T(1) = 1 $

But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?

# Answer
The solution to your recurrence is $$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$ also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.
> 4 votes

# Answer
Any time you see something resembling a convolution, that suggests generating functions as a method. Convolutions are things that look like $\sum\_x f(x)f(\overline{x})$, where $\overline{x}$ denotes some kind of "complement" or "opposite" of $x$. Generating functions often turn convolutions into products.

Possible references are:
> 3 votes

---
Tags: binary-trees, recursion, search-trees
---


# Question
Title: Is it decidable whether a Turing machine will ever leave the start state on any input?
Is $L=\\{ M | M\text{ leaves the start state on every input}\\}$ decidable?

I have an intuition that the following language is undecidable, since the complement $L^C$ seems to not be recursively enumerable. Some TM might remain on the start state for $k$ steps, but then leave at $k+1$ steps, so we can't get a definitive answer whether it will ever leave the start state.

What known non-decidable TM can be reduced to A to show that a contradiction arises?

# Answer
> 0 votes
I would say decidable. Here is the idea.

Firstly, let your alphabet be $\Sigma$, including the empty symbol. I claim that unless you have in the transition function $(s\_0, x) \to (s\_i, \dots)$ for every $x \in \Sigma$ and $ i \neq 0$ your machine is not the desired one. Why this is true? Suppose there is such $x$ for which TM doesn't change the initial state. Fill the tape with all these $x$'s. Done.

Here I had the assumption that we can have any initial tape as we want. If you consider only finite non empty input the problem becomes much harder.

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


# Question
Title: Is any superset of an undecidable set is uncountable?
This statement really made me confused, Is any superset of an undecidable set is uncountable?

# Answer
> 3 votes
All sets of words over a finite alphabet are countable. Stated differently, no set of words over a finite alphabet is uncountable.

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


# Question
Title: Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$
I am working on finding the asymptotic estimate for $$ \sum\_{k=1}^{N} {\frac{1}{k^2 H\_k}}.$$ All I know is that ${\frac{1}{k^2 H\_k}}$ is convergent because $${\frac{1}{k^2 H\_k}}\<\frac{1}{k^2}$$ and $\frac{1}{k^2}$ is convergent.

Am I right to conclude that the asymptotic estimate for this is $O(\frac{1}{k^2})$?

# Answer
Since the infinite series $\sum\_{k=1}^\infty \frac{1}{k^2H\_k}$ converges, an asymptotic estimate to your sum is simply $\Theta(1)$.

You can obtain a better estimate by estimating the tail: $$ \sum\_{k=1}^n \frac{1}{k^2H\_k} = \sum\_{k=1}^\infty \frac{1}{k^2}{H\_k} - \sum\_{k=n+1}^\infty \frac{1}{k^2H\_k}. $$ We can estimate the tail by $$ \sum\_{k=n+1}^\infty \frac{1}{k^2H\_k} \leq \sum\_{k=n+1}^\infty \frac{1}{k(k+1)} = \frac{1}{n}, $$ and so $$ \sum\_{k=1}^n \frac{1}{k^2 H\_k} = C - O\left(\frac{1}{n}\right), $$ where $C = \sum\_{k=1}^\infty 1/k^2H\_k \approx 1.33275$.
> 3 votes

---
Tags: asymptotics
---


# Question
Title: center star alignment induces optimal alignments on pairs with the center string?
I'm trying to follow the center star algorithm error analysis - section 6.5.3. They claim that for the center string $S\_1$ the distance induced by the algorithm $d(1, j)$ is always equal the optimal alignment $D(S\_1, S\_j)$ since $\delta(-,-) = 0$.

I don't understand this argument. For each j, the algorithm aligns a totally different string $S'\_1$ with many surplus gaps from the previous iterations.

How come we arrive to the same exact cost? Can't it be that for the new string $S'\_1$ there's a very cheap alignment that would have costed lots of extra gaps if it was $S\_1$?

# Answer
> 0 votes
$S'\_1$ indeed can have many extra gaps over $S\_1$, but **it doesn't matter** and the distance $d(1,j)$ between the final strings in the MA: $S'\_1$ and $S'\_j$ would be exactly the same as $D(S\_1, S\_j)$.

Why? when we start the $j$ iteration, we do an optimal global alignment between $S'\_1$ and $S\_j$. At first, it looks as if $S'\_1$ might contain *disturbing* gaps, which will cause the distance to get *larger* than the distance to $S\_1$, and *helpful* gaps which will cause the distance to get *smaller* than the distance to $S\_1$. Let's show that both aren't really helpful or disturbing! suppose `S1 = abc`:

*Disturbing* gap - e.g. `S'1 = ab_c` and `Sj = abc`. as $\delta(-,-)=0$, whenever we encounter a disturbing gap at $S'\_1$ we can just add an extra space to $S\_j$ at no cost and get the same distance.

*Helpful* gap - e.g. `S'1 = ab_c` and `Sj = abxc`. It isn't really helpful, as if the global alignment would have wanted to add a gap to $S\_1$, it would just add it - it makes no difference that that gap was there before we started the alignment...

Gaps added after the $j$ iteration - if the center star algorithm will add gaps to $S'\_1$ in iteration $k \> j$, **it will always adjust strings from previous iterations with gaps at the same place**, including $S\_j$ - and again because $\delta(-,-)=0$ it doesn't make any difference.

To summarize - as there's no help or disturbance, the alignment distance would be **exactly** as the global alignment $D(S\_1, S\_j)$ would have wanted it, plus some extra aligned gaps which can not disturb our distance.

---
Tags: approximation, strings, bioinformatics
---


# Question
Title: If $A \le _m B$, then $A$ decidable $\not\Rightarrow B$ decidable
I'm currently reading up a bit on Turing decidability reductions as I'll take a more in-depth course about the topic next semester. While reading up on some older course material I asked myself the following question which leaves me a bit puzzled:

Let $A, B$ be languages, and $\le\_m$ be the mapping reduction for languages.

For mapping reductions a central statement is

> If $A \le \_m B$, then $B$ decidable $\implies A$ decidable

I'm now wondering about is whether the implication also works the other way around:

> If $A \le \_m B$, then $A$ decidable $\implies B$ decidable

I strongly suspect that this is not the case as $A \le \_m B$ does not even imply the existence of a mapping function from $B$ to $A$, however I'm struggling to find a good counterexample for this.

# Answer
Consider $A = \Sigma^\*$ and $B \subset\Gamma^\*$ undecidable. If you know any $b \in B$, the constant mapping $\Sigma^\* \to \Gamma^\*, w \mapsto b$ provides a counterexample.

To be a bit more specific: Let $\Gamma = \\{\texttt\<, \texttt\>, \texttt\[, \texttt\] \texttt+, \texttt-\\}$ be the set of symbols for Brainfuck without I/O. As BF is Turing complete, we know that the subset $B \subset \Gamma^\*$ of all terminating BF programs is undecidable (via the Halting problem). It turns out that $\texttt{+} \in B$.

Thus we have $A \leq\_m B$ for all languages $A \subseteq \Sigma^\*$ via the mapping $f\colon \Sigma^\* \to \Gamma^\*$ given by $f(w) = \texttt+$.
> 2 votes

# Answer
I'm going to answer this informally, in a way that gives the intuition. You should be aware of the formal definitions of the terms that I use, so you should be able to translate this into a formal argument.

$A\leq\_m B$ means that, if I could solve $B$, then I could use that to solve $A$ in a particular way.

* Suppose that we know that $A$ is hard to solve. Then $B$ cannot be easy to solve – if $B$ were easy, the reduction would give us an easy way of solving $A$, and we know that $A$ is hard.
* Suppose we know that $A$ is easy to solve. That doesn't tell us anything about $B$. $B$ could be easy, and give us another easy way of solving $A$, or it could be hard and give us a dumb way of solving $A$.
> 1 votes

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


title: Church-Rosser on an example

text:
# Question
Title: Church-Rosser on an example
In lambda calculus, starting from $KII$ we can get by a single $\beta$-reduction to either

$\lambda y.II$

or $KI$

Now, according to Church-Rosser, these should be reducing into a common normal form. But the first reduces to $I$ and the second to $\lambda y.\lambda z.z$.

Am I doing wrong $\beta$-reductions or the theorem holds only on some condition? I do not see a common reduct here.

# Answer
> 3 votes
Remember that $1)$ application is left associative and $2)$ application has higher precedence than abstraction. This is:

$1)$ $ A B C = (A B) C \neq A (B C)$
$2)$ $ \lambda x. A B = \lambda x. (A B) \neq (\lambda x. A) B$

So

$KII = (KI)I = ((\lambda x y. x) I) I = (\lambda y. I) I = I$

---
Tags: lambda-calculus
---


# Question
Title: Find amortized cost for insertion in binary arrays using accounting/potential methods?
Background:

> The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. However, there will be no relationship between the items in different arrays. The issue of which arrays are full and which are empty is based on the binary representation of the number of items we are storing. For example, if we had 11 items (where 11 = 1 + 2 + 8), then the arrays of size 1, 2, and 8 would be full and the rest empty.
>
> For inserts, we'll do them like mergesort. To insert the number 10, we first create an array of size 1 that just has this single number in it. We now look to see if $A\_0$ is empty. If so, we make this be $A\_0$. If not (like in the above example), we merge our array with $A\_0$ to create a new array (which in the above case would now be \[5, 10\]) and look to see if $A\_1$ is empty. If $A\_1$ is empty, we make this be $A\_1$. If not (like in the above example) we merge this with $A\_1$ to create a new array and check to see if $A\_2$ is empty, and so on.

Further clarification found here.

> To be clear about costs, let’s say that creating the initial array of size 1 costs 1, and merging two arrays of size $m$ costs $2m$ (so merging the sorted arrays can be done in linear time).

The claim is that the above data structure has amortized cost $O(\log n)$ per insertion.

1. How to show this using the accounting and potential methods for amortization?
2. What would potential function be?

Initial ideas: Right off the bat it seems that this problem bears a lot of resemblance to the typical binary counter problem. Imagine each array being empty or filled represented by a value of 0 (empty) or 1 (filled), and these values are updated accordingly with insertions. These counters would change when current arrays are completely filled and have to perform merges, which will create a larger filled array and as a consequence several smaller unfilled arrays, changing a lot of 1s (filled) to 0s (unfilled). In the binary counter example the expensive cost of incrementing is dealt with through the potential function which is the number of 1s in the binary counter. The cost for an insertion here is not just incrementing a counter, but paying for costly merges. I do think the idea of a counter perhaps can tie into this problem, but am unsure how it connects to potential method and $O(\log n)$ per insertion. Any thoughts?

Also, found this explanation but it doesn't fully make sense to me. Maybe someone would be willing to elaborate?

# Answer
Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n \< 2^{k+1}$. Thus only the arrays $A\_0,\ldots,A\_k$ are active. The cost of the $m$th operation can be broken down as follows:

1. Creating the initial array: 1.
2. If the number of elements (before adding the current one) is odd: 2.
3. If the number of elements is $3\bmod{4}$: 4.
4. And so on.

Observe now that:

* The number of odd numbers among $0,\ldots,n-1$ is $\lfloor n/2 \rfloor$.
* The number of elements $3\bmod{4}$ among $0,\ldots,n-1$ is $\lfloor n/4 \rfloor$.
* And so on.

We conclude that the total cost of the first $n$ operations is $$ \begin{align\*} &n + 2\lfloor n/2 \rfloor + 4\lfloor n/4 \rfloor + \cdots + 2^k \lfloor n/2^k \rfloor \\ \leq &n + 2(n/2) + 4(n/4) + \cdots + 2^k(n/2^k) \\ = &n + n + n + \cdots + n \\ = &(k+1) n \\ = &(\lfloor \log\_2 n \rfloor + 1)n. \end{align\*} $$ We conclude that the amortized cost is at most $\log\_2 n + 1 = O(\log n)$.
> 3 votes

---
Tags: arrays, time-complexity, amortized-analysis
---


title: Merging two binary search tress

text:
# Question
Title: Merging two binary search tress
You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$ nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys in tree B.

Propose an efficient algorithm for creating a single height-balanced binary search tree containing the key values of all the nodes in both the trees A and B.

# Answer
Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2): You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1 h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T2′ of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

```
v ← root(T1)
h′ ← h1
  whileh′ >h+1do
  if balance factor (v) = -1 then h′ ← h′ − 2
  else h′ ← h′ − 1
  v ← rightchild(v)

```

This takes O(h1) time. Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left subtree is the subtree rooted at v and whose right subtree is T2′. Note that this is a valid binary search tree, since all the keys in the subtree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T2′. The balance factor of the root of this new tree is h−h′, which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h′ +1, which is 1 bigger than v’s height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm. Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n)

you can find more answer in this question : Merging of height balanced trees

and this algorithm can help you for more details : A Fast Merging Algorithm MARK R. BROWN
> 1 votes

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