# Question
Title: Optimizing resource management game (similar to Farmville)
Given a fully deterministic single player resource management game with a pre-known finite number of turns and reasonably simple rules (eg, Farmville, if it were single player, deterministic, and ended after a certain number of turns), is it usually possible to write a computer program that can optimize the game in a reasonable amount of time? Details:

* I'm trying to create such a game (sort of a M.U.L.E. clone, but not really). Players would compete individually to get the highest score under a given set of starting conditions. The game must be simple enough to be fun, but complex enough that someone can't write a computer program to rapidly optimize it. The game is semi-tedious (in its current form), so I encourage API/automated use.
* Since the game is deterministic and finite, I realize that an optimization algorithm must exist. So my question really is: can someone always write an optimization algorithm that runs fast enough to be useful?
* I realize the answer depends on the actual game I write, so I'm looking for one of these answers (roughly):

+ Give up. If you design a resource management game easy enough for people to understand, someone could easily design an algorithm to win it.
    + There's hope. Depending on how you design the game, it may or may not be possible to write a reasonable algorithm to optimize it. However, you have to be very careful.
    + Go for it. In general, there are no algorithms that can optimize most resource management games. Barring extreme conditions, any resource management game you design could not reasonably be optimized by a computer.
* There are Farmville strategy guides online, but they focus on general strategy, not an explicit algorithm.
* I realize this is a specific case of P != NP, and that's it theoretically possible to create simple questions that cannot be solved easily (eg, factor a product of two large primes) or even at all (eg, the halting problem), but I'm wondering if resource management games fall, in general, into the NP category.
* For reference, the game will be a scaled down (and single player) version of:

https://github.com/barrycarter/bcapps/tree/master/YAMC

# Answer
> 2 votes
In general, you cannot hope for a polytime solution to all such games. For many such games, the problem of playing them optimally is NP-hard.

For instance, Minesweeper (on a $n\times n$ grid) is NP-hard, and thus does not have a polytime algorithm to solve it (unless $P=NP$, which most consider unlikely). The same is true for Sudoku (on a $n^2 \times n^2$ grid) and Tetris. Optimal play for chess, checkers, Go, and Scrabble (on a $n \times n$ grid) is either EXPTIME-complete or PSPACE-complete (depending upon whether you put a bound on the number of moves that a player can make), so they too are very unlikely to have any polytime algorithm to play them optimally (unless the polytime hierarchy collapses or something equally surprising).

In fact, I've seen some folks suggest that there's a strong connection here: the best games tend to be ones where finding the optimal solution is asymptotically hard. If finding the optimal solution was too easy, the argument goes, the game wouldn't be fun for humans. Obviously, this is not a rigorous argument and it is easy to come up with counterexamples, but I think there might be something to it.

There's lots more written on this sort of topic. For a entry point and overview, see, e.g., the following:

---
Tags: game-theory
---


# Question
Title: How to find the asymptotic runtime of these nested loops?
```
i=n;
while(i>0) {
  k=1;
  for(j=1;j<=n:j+=k)
    k++;
  i=i/2;
}

```

The while loop has the complexity of $\lg(n)$ the j value of inner loop runs 1,3,6,10,15... increase like 2,3,4,5,...

But how to find the overall complexity ?

# Answer
> 1 votes
$j$ satisfies the recurrence $j\_k = j\_{k-1}+k$. Note that another sequence, $s\_k = k^2$ satisfies $s\_k = s\_{k-1} + 2k-1$.

$$j\_k = \sum\_{i=1}^k i = \frac 1 2\sum\_{i=1}^k 2i = \frac 1 2(s\_k+k)$$

This should give you enough to find the largest $k$ such that $j\_k \< n$.

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


# Question
Title: Is $a^n b^n$ an artificial language or does it occur in the real world?
The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$.

Do such forms occur in the real world? Can you provide an example of a real-world case where there must be $n$ occurrences of something followed an equal number of occurrences of something else?

Let me give an example: if I run an on-line store, then for each purchase made to my store, there must be a corresponding delivery of the purchased item. That might be modeled as $n$ purchases followed by $n$ deliveries:

> purchase purchase purchase delivery delivery delivery

However, that is not a good data model since each delivery should legitimately be paired to a purchase:

> purchase delivery purchase delivery purchase delivery

So I am left wondering if there are *any* real-world examples where data would be (legitimately) modeled as a sequence of $n$ items of one type followed by $n$ items of another type. Can you provide a real-world example please?

Hendrik Jan provided this good example (see it in the comments below): *This weekend I visited my mother. Three flights up, and three flights down when I left.*

Neat example! Can you think of others?

A colleague just informed me of another example. In the KML specification it says that a \<Track\> element must contain N \<when\> elements followed by N \<gx:Coord\> elements:

https://developers.google.com/kml/documentation/kmlreference#gxtrack

Another excellent example. What are other examples?

Another colleague sent me an article about columnar databases. It is often more efficient to store data in columns rather than rows. For example, we may have a column of person's ages followed by a column of person's heights. Or, a list of N integers (ages) followed by a list of N decimals (heights). This enables efficient calculation of sums or averages. Here's the article:

http://www.postgresql.org/message-id/52C59858.9090500@garret.ru

**More examples please! I would like for us to create a nice collection of compelling examples.**

# Answer
The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.
> 12 votes

# Answer
The famous $a^nb^n$ example actually occurs very often: in a way, you can think of this language as a comparison of two natural numbers. For example, any piece of code that compares two inputs is essentially solving $a^nb^n$.

Comparison occurs naturally as a condition (e.g. in an "if" statement, or a loop-termination condition). Thus, it is indeed a real-life problem.

However, you can also argue to the converse - in "real-life", everything is finite, so this language doesn't really occur. Still, this is an argument against every infinite language.
> 1 votes

---
Tags: formal-languages, context-free, modelling
---


title: compiler interaction with OS

text:
# Question
Title: compiler interaction with OS
I want know if compiler interacts with operating system during compilation process.And if yes then which part of compiler interacts with which part of operating system

# Answer
> 2 votes
Compilation is only a process of converting your code to assembly language. To achieve this task there is no need to interact with OS kernel.

If you also mean linking, interaction with OS is again not a requirement. However, if certain optimizations, or naming conventions and versions are involved, linking might access operating system information. Still, again no code is executed in the kernel level.

---
Tags: operating-systems, compilers
---


# Question
Title: How to represent/implement the hypotheses class for a DAG learner
I am implementing a learner to learn a DAG model $G=\langle V,E\rangle$ where $V$ and $E$ represent both variables and dependencies respectively ( similar to Bayesian networks). Each variable $v\in V$ is associated with possible values (domain) $D\_v$ and a function $\theta\_v$.

I assume the learner knows the number of variables $n$ (i.e. vertices) and their possible values (domain). The goal is to find $E$ (dependencies) and $\theta\_v$ for every variable $v$. I also assume there is a target function $c$ exist (the realizable case).

The hypothesis class is defined as the set of consistent hypotheses i.e. $H=\\{h|\ h(x)=c(x)\\} \forall x\in S$ where $S$ is set of examples seen so far.

I am trying to find a way to represent my hypotheses class. Initially, before receiving any example, it contains:

1. all possible DAGs over $V$.
2. all different combinations of $E$ as long as its acyclic.
3. For every Graph $G$ generated from (1) and (2),all different function values over $G$.

Beside my naive representation, I do not know how to compute (1) precisely. To put my question in another way, how to represent the hypotheses class over Bayesian networks?

# Answer
> 1 votes
OK here is what I did:

I read about the most specific $ms$ and most general $mg$ hypotheses here. Intuitively, the hypotheses class is defined as these two hypotheses and anything in between. That is, for a hypothesis $h$ with DAG $G\_h$, in order for $h$ to be in the hypotheses class $H$, it must be the case $G\_{ms}\subseteq G\_h \subseteq G\_{mg}$.

For now, I used only $ms$ since my problem transformed to learning only one labelling $\\{+\\}$. Initially $G\_{ms}=\emptyset$. Every example $x$ consist of pair of vertices $(x\[a\],x\[b\])$. if $\zeta(x)=\\{+\\}$ then there is an edge from $x\[a\]$ to $x\[b\]$ in $G\_{ms}$ where $\zeta(x)$ is the labelling of $x$ according to the target function $h^\*$.

After seeing $i$ examples $G\_{ms}$ has $i$ edges. Any hypothesis $h$ with $G\_{ms}\subset G\_h$ is included in my hypotheses class $H$.

---
Tags: graphs, machine-learning
---


# Question
Title: A genetic algorithm modified for a specific problem
I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I found that optimal solutions are binary strings that contain only 01 or 011. For example, the optimal solution for $N=16$ is `0101011010101101`. So I think it would be a good idea to only search the solutions space where all solutions/chromosomes only contain 01 or 011. But clearly the standard GA cannot restrict the search in the subspace I desire. One mutation or one crossover will make the new solution go into the larger solution space.

My question is: is there a way to adapt the standard GA to restrict its solution space to one where the chromosomes contain only 01 or 011?

# Answer
Start with a population, where every candidate is "good", where "good" means they contain at least one occurrence of substrings "01" and "011".

For the mutation operator, flip a coin. If the result is heads, choose a random substring of length 2 and change it to "01". If the result is tails, choose a random substring of length 3 and change it to "011".

For the crossover operator, let $A$ and $B$ be two parents. Find say the first occurrence of substring "01" or "011" from $A$, that occurs starting from index $i$. Check if in $B$ there is an occurrence of "01" or "011" before $i$. If so, choose $i$ as your crossover point. If not, find the next occurrence from $A$, and repeat. This process will terminate at some point, because you start out with individuals containing "good" substrings, and your operators maintain an invariant that all individuals are "good".

Please note that this only really answers your question of "how do I modify my GA", and does *not* address whether this works performance-wise. However, this should give you ideas as to what kind of operators you can experiment with.
> 3 votes

# Answer
Here is one candidate way to impose the restriction you have in mind.

There is an isomorphism between strings in $(a|b)^\*$ and strings in $(01|011)^\*$: each $a$ corresponds to a $01$, and each $b$ corresponds to a $011$. For instance, the string $ab$ corresponds to $01011$, and $abb$ corresponds to $01011011$.

Now apply your genetic algorithm to the strings over $(a|b)^\*$. In other words, the chromosome is a string like $abb$, not a binary string like $01011011$. For instance, you'll apply mutation and cross-over to the $abb\cdots $ strings, not the $0110\cdots$ strings. Then, when you want to evaluate the fitness of a $abb\cdots$ string, you just convert it to the corresponding $0110\cdots$ string and evaluate its fitness.

This ensures that all new chromosomes generated by your genetic algorithm obey the restriction that they are composed solely of binary strings containing $01$ or $011$.
> 2 votes

# Answer
in GA you start with population then you try to evolve or generate other populations by the two operations: crossover and mutation. If you want to restrict the search space to strings containing only $01,011$, you can alter the operations accordingly. However, make sure your statement

> I found that optimal solutions are binary strings that contain only 01 or 011

is correct for all problem instances (or at least characterise the subclass where this is true).
> 1 votes

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: Why is deciding regularity of a context-free language undecidable?
As I have studied, deciding regularity of context-free languages is undecidable.

However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient condition. So the problem should be decidable.

Where is my mistake?

# Answer
> 11 votes
Myhill–Nerode does indeed provide a characterization of the regular languages but that isn't enough to show that the problem is decidable. "Decidable" means that there is an algorithm (more formally, a Turing machine) that terminates for every input and, of course, always gives the correct answer. So, in this case, you would need to give an algorithm that, given a language as input, determines whether the Myhill–Nerode relation has a finite number of equivalence classes. It turns out that this cannot be done for context-free languages; details in your favourite formal languages textbook.

If you want to decide whether a general language is regular, a further subtlety is that you have to be careful about what is the input to your algorithm. The input must be a finite string – otherwise, even just reading the input would be a non-terminating algorithm. In the case of context-free languages, you could use a grammar as a finite representation of an infinite language. For more general languages, you would need... well, something more general. Ultimately, though, if you want to deal with *all* languages, you're doomed. Over any finite alphabet, there are uncountably many languages but only countably many finite strings. That means you can't possibly describe all languages using finite strings.1 Therfore, trying to write an algorithm to determine whether arbitrary languages given as input are regular actually fails before it begins. It's not just that you can't write the algorithm: you can't even write the input!

Note that this doesn't mean that you, a human being, can't use Myhill–Nerode to determine whether languages are regular. It just means that you can't write down a set of precise instructions to tell *me* how to do that. At some point, any such set of instructions would have to say something like, "And then play about with it to see what works," or "From there, you have to figure it out on your own."

---

1. In particular, this means that some languages must be undecidable, since there are more languages than there are algorithms.

---
Tags: formal-languages, computability, regular-languages, undecidability
---


# Question
Title: Normal order sequencing vs applicative order sequencing
I'm trying to understand this lecture, section 2.7. Why would the normal order sequencing print out `"hello" "world"` and not `"world" "hello"`? I may be misinterpreting the order in which the arguments are applied.

It looks like the expression

$$ ((Seq (display "hello"))\\; (display "world")) $$

would evaluate to

$$ \lambda z.((display "world")\\; (display "hello")) $$

and that would, under normal order, would print out `"world" "hello"`.

My question is whether the assumption I'm making is correct. If not, could you show the correct derivation of the end-expression?

# Answer
> 7 votes
You're misreading the combinator. In these lecture notes, lambda abstraction binds tighter than application (the opposite convention is more common — it's apparent from the spacing but the author should state that explicitly). I'll use extra (redundant) parentheses in my answers to avoid any potential for ambiguity. The combinator is $$ \mathit{Seq} = \lambda x. \lambda y. ((\lambda z.y) \\: x)$$ So $$ \begin{align} & ((\mathit{Seq} \\; (\text{display "hello"})) \\; (\text{display "world"})) \\ &\qquad = (((\lambda x. \lambda y. ((\lambda z.y) \\; x)) \\; (\text{display "hello"})) \\; (\text{display "world"})) \\ &\qquad \to^2 ((\lambda z. (\text{display "world"})) \\; (\text{display "hello"})) \\ &\qquad \xrightarrow{\text{display "hello"}} (\text{display "world"}) \\ &\qquad \xrightarrow{\text{display "world"}} \mathord{?} \\ \end{align} $$ where $M \xrightarrow{\text{action}} N$ means that $M$ evaluates to $N$ performing the specified action.

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


# Question
Title: Weighted Set covering problem with a fixed number of colors
I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost.

I have a fixed number of colors, C = {1 , 2, ... , m}. Some of the sets mentioned above interfere with each other. I cannot assign same color to both those sets together.

I want to pick the sets and color them from my available color list in the following way:

\**Objective: Minimize the total cost of the selected sets

Constraints:

1. All elements of the universe are covered
2. No two sets that interfere with each other is assigned the same color\**

If the second constraint, i.e., coloring constraint, is taken out, the problem reduces to standard weighted set covering problem. I can solve that using a greedy manner. For example, greedy unweighted set covering will work in the following way: -- 1. pick the set with the highest number of elements at first, 2. Remove that set and the associated elements from the universe, 3. Repeat step 1 until all elements of the universe are covered.

But the coloring constraint in the presence of interference among sets and a fixed number of colors complicates the issue.

For example, let's assume,

U = {1, 2, 3, 4, 5}.

There are three sets, {1, 2, 3}; {2, 3, 4, 5} ; {4, 5}.

Assume {2, 3, 4, 5} interferes with both {1, 2, 3} and {4, 5}. {1, 2, 3} and {4, 5} do not interfere with each other. Assume that there is only one color in the system.

A standard greedy unweighted set coloring solution will pick {2, 3, 4, 5} at first and {1, 2, 3} in the second round. But that is an infeasible solution to my problem since they interfere with each other and I have only one color in my system. A feasible solution will be the selection of {1, 2, 3} and {4, 5}.

I wonder how I can minimize the total cost while meeting the color constraint. Any hint on the unweighted version of the problem (where all sets have equal cost) will be very helpful, too.

Thanks,

Nazmul

Additional information: The coloring of the sets and the interference can be understood by my application scenario.

I am looking at a wireless cell. I have a set of frequencies, possible base station locations and their associated users. Each set is associated with a station and it shows the set of users that the base station can serve.

"Interference" from one set to the other means that the users' signals of one set reaches the other set's base station. In a wireless setting, this interference is not symmetric. But assumption of symmetry is OK in the algorithm because if set A interferes with set B, A & B both should get different colors if they are selected.

The interference among sets is not transitive. Set A may interfere with set B (A's users may interfere with B's base station) and set B may interfere with set C (B's users may interfere with C' base station) but that does not mean that set A will interfere with set C.

The current example is showing that two sets interfere if they intersect. This is just a coincidence. I will have a pre-generated look up table that shows which set interferes with which set before the algorithm starts. This pre-generated table will be an input to the optimization problem

# Answer
## General advice

The question is confused about what you are looking for.

There is obviously no hope for a polynomial-time algorithm that finds the optimal solution to this optimization problem. This problem is at least as hard as weighted set covering (without coloring restrictions). Weighted set covering is NP-hard. Therefore, your problem is NP-hard. Therefore, any general polynomial-time algorithm that always outputs the optimal solution to your optimization problem would imply that $P=NP$ (which seems unlikely).

Obviously, if the question is confused about what you're looking for or if you are unable to communicate it in the language that computer scientists understand, then that reduces the likelihood that anyone will be able to answer your question in a way that helps you. We're not mind-readers.

Based on your comments, I suspect that what you *actually* want is an approximation algorithm for your problem, or a heuristic algorithm. So, here is my advice, based upon my inference of what I suspect you actually want (as opposed to what you said you want).

First, I suggest that you learn about approximation algorithms and heuristic algorithms. Learn the terminology, learn some basic results, learn some of the standard examples of approximation algorithms. This will help you communicate with others and be able to express your requirements clearly in a language that other computer scientists can understand. Also learn about standard strategies for dealing with NP-completeness (e.g., Dealing with intractability: NP-complete problems).

Second, I suggest that you take a closer look at the sort of problem instances typically arise in your application. If you want to maximize the chance you find an approximation algorithm or heuristic algorithm that is useful in your application scenario, you need to analyze the parameters and properties of the problem instances that arise in your application. What are typical values of $k,m,n$? That's the sort of question you should be asking (and communicating in the question).

Without that kind of information, I don't think anyone here can predict what the best approach to your particular problem might be. However, I'll suggest some candidate approaches that you could try out.

## SAT solvers

You can formulate (the decision problem version of) your problem as a SAT instance and then try solving it with an off-the-shelf SAT solver.

We'll solve the decision problem version: given $u$, we'll test whether there exists a solution of total cost at most $u$. Introduce boolean variables $x\_1,\dots,x\_k$. The intent is that $x\_i=1$ means that the $i$th set $S\_i$ is selected, and $x\_i=0$ means that it is not. Also introduce variables $c\_1,\dots,x\_k$, where $c\_i\in \\{1,\dots,m\\}$ represents the color assigned to the $i$th set (if it is selected). Note that each $c\_i$ can be represented as a number of boolean variables using standard techniques. Finally, introduce variables $y\_0,y\_1,\dots,y\_k$, where $y\_i$ is an integer that represents the total cost of all sets that were selected from out of the first $i$ sets. Each $y\_i$ can be represented as $\lceil \lg (u+1) \rceil + 1$ bits, using binary encoding.

Now we're going to add some constraints to capture the requirements for a solution to be valid. For each element $u \in U$, we'll add a constraint to require that element $u$ is covered by at least one of the selected sets:

$$\bigvee\_{u \in S\_i} x\_i.$$

(Here the logical OR is taken over all sets $S\_i$ that contain $u$; at least one of them must be selected.) Also, for each pair $i,j$ of sets that interfere, we'll add a constraint to require that they have been given different colors: namely, $c\_i \ne c\_j$. Finally, we'll add constraints to define the $y\_i$'s: $y\_0=0$, and for each $i=1,\dots,k$:

$$y\_i = y\_{i-1} + \begin{cases} \text{cost}(S\_i) &\text{if $x\_i=1$}\\ 0 &\text{otherwise} \end{cases}.$$

Finally, we'll add the constraint that the total cost is at most $u$: namely, $y\_k \le u$. To deal with overflow, it helps to add constraints that $y\_i \le u$ for all $i$ and to make sure you've allocated enough bits for each $y\_i$ so that you can encode all integers in the range $0,1,\dots,2u$.

Notice that all of these constraints can be encoded in SAT (i.e., as CNF clauses) in a straightforward way. Some SAT solver front-ends, such as STP, even provide support to make it easy to express these: they'll convert the integer constraints to CNF by bit-blasting.

Now that you've formed a CNF formula representing the assertion that there exists a solution of total cost $\le u$, you feed it to a SAT solver and see whether it can find a satisfying assignment. If it can, then you know the optimal solution costs at most $u$; if it can't, you know the optimal solution costs at least $u+1$. Now you can use binary search to find the optimal solution.

This is not an approximation algorithm: this algorithm finds the exact optimum. Of course, it is a heuristic. SAT is NP-complete, so there is no guarantee that this algorithm will run in polytime (and we can be pretty sure that on some problem instances, it won't). However, SAT solvers are pretty good in practice, and so this might work pretty well on problem instances that arise from practice.

This formulation is a straightforward combination of the formulation of weighted set cover as a SAT problem, and the formulation of graph coloring as a SAT problem (see e.g. here). If you are having trouble following this, study other reductions to SAT and other ways of encoding standard problems as SAT instances.

## Integer linear programming

Another approach would be to formulate this as an integer linear program, then feed it to an off-the-shelf ILP solver.

The approach is very similar to the formulation in SAT. You can use similar variables to that listed in my SAT formulation above.

Boolean variables can be encoded as integer variables that are restricted to be in the range $0 \le \cdot \le 1$. Boolean operations on boolean variables can be expressed using the techniques shown here: Express boolean logic operations in zero-one integer linear programming (ILP)

I recommend encoding the $c\_i$'s as a one-hot encoding, i.e., introduce boolean variables $c\_{i,j}$ where $c\_{i,j}=1$ means that the $i$th set (if selected) is assigned the color $j$. Then you can add the constraints

$$\sum\_j c\_{i,j} = 1 \text{ for each $i$}$$

and

$c\_{i,j}+c\_{i',j} \le 1$ for each pair of sets $i,i'$ that interfere and each color $j$.

There's no need for the variables $y\_0,\dots,y\_k$ or to limit yourself to the decision version of the problem. Instead, you can make the objective function be

$$\sum\_i \text{cost}(S\_i) x\_i,$$

which is a linear function of the variables (as required).

Now feed it to an ILP solver, and see what the best solution it can find is.

## Naive greedy algorithm

There's a straightforward extension of the greedy algorithm, that could be used for your problem. It will only sometimes find a solution, so it is incomplete; other times, it will fail to find any valid solution.

In particular, at each point in time, we will have a partial solution (some sets that can be colored with $\le m$ colors). We will incrementally select a set to add to the partial solution greedily. We can prioritize the sets as follows, to help us select the next set. The priority of $S\_i$ is the number of additional elements of $U$ that would be covered if we selected $S\_i$ (over and above the number of elements that have already been covered by our current partial solution), divided by the cost of $S\_i$. Given a partial solution, we find a coloring for the sets (using some heuristic for graph coloring that tries to color them with as few colors as possible), then for each $i$ we see whether adding $S\_i$ would increase the number of colors above $m$. If we can't find a way to color the current selection + $S\_i$, then we throw away $S\_i$. Out of the remaining unselected sets, we choose the set with the highest priority. We repeat until we can make no further progress.

If this process ends with a selection that covers all of $U$, then we have found a candidate solution. It may not be optimal (it probably won't be), but it is *a* solution. If it ends without covering all of $U$, then the algorithm failed.
> 2 votes

# Answer
Obviously, if the number of colors is fixed, there is not much hope for a polynomial algorithm. You'd have to answer the question, whether your dependency graph $G$ is colorable with $n$ colors, which is NP-hard in general.
> 1 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Non-deterministic Turing machine that halts on at least one branches of computation
I'm looking at my textbook here from Michael Sipser and he says that a **nondeterministic Turing machine is a decider if all its computation branches halt on all inputs.** I think I recall seeing somewhere what you'd call a nondeterministic Turing machine that halts on at least one branch for all inputs, but may loop on others. Is there a name for such a thing? I see later in this chapter the word **verifier**, but that doesn't seem to fit... I think that refers to an algorithm.

> A ***verifier*** for a language $A$ is an algorithm $V$, where $$A=\\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\\}.$$ We measure the time of a verifier only in terms of the length of $w$, so a ***polynomial time verifier*** runs in polynomial time in the length of $w$. A language $A$ is ***polynomially verifiable*** if it has a polynomial time verifier.

# Answer
> 2 votes
The idea is that a *deterministic* TM will always answer Yes/No in finite time (else the whole idea makes no sense). And to do that, the deterministic simulation of the NTM can't just go off into lala-land on some branches, i.e., every branch must end in yes/no at a finite depth. It *decides* (gives you a definite answer). If not all branches halt, it can *verify* (i.e., given a word in the language it is guaranteed to answer Yes; if not, perhaps it anwers No, perhaps it loops).

# Answer
> 3 votes
The strings accepted by a NTM `M` is the language of `M`, noted `L(M)`

Let us say that `M` for any input is not guaranteed to halt on all branches. Then `M` clearly cannot be a decider, and is thus only a recognizer. `M` recognizes the language of all strings, for which any branch of `M` ends in an accepting state.

Since `M` is a recognizer, it is only guaranteed to accept a string if the string is in `L(M)`. Given a string, that is not in `L(M)`, it may reject the string, or loop forever. Any NTM can be simulated by a DTM, but if NTM only recognizes a language `L`, its equivalent DTM will also only recognize `L`.

If the NTM halts on all branches for any input it is a decider, then the equivalent DTM will do the same and thus be a decider as well.

A verifier is not the thing you are looking for. In Sipsers book, Introduction to the Theory of Computation, the verifier is introduced when talking about complexity of algorithms and complexity classes, because any language `L` is in NP if and only if it has a polynomial time verifier.

A verifier for a language `L` will take as input a string `w` in `L` and a certificate `c` (think of the certificate as a solution to the problem `w`) and verify that the certificate is in fact a correct solution, which makes `w` lie in `L`.

**Example:**

For the language

```
L = { w | w is an integer for which the product of some of the digits equals 12000 }

```

You can make a verifier `V`, that takes a string `w` in `L`, a certificate `c`, and verifies that `w` is in fact in `L` using the certificate `c`. `c` could be a binary string indicating the integers in `w` for which the product of equals 12000.

For example, `V` must reject the input `1923423343, 0010111011`, because `2*4*2*3*4*3 = 576 != 12000`

For many problems, we only know an algorithm that can solve them running in exponential time of the input size. This is why verifiers are interesting, because it is often the case, that we given a solution quickly can determine if that solution is correct or wrong.

---
Tags: turing-machines, nondeterminism
---


title: Simple explanation of Simon's Problem

text:
# Question
Title: Simple explanation of Simon's Problem
I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).

Can someone just briefly explain it in simple language, like is it just XOR'ing two binary strings and trying to isolate each string? Also, if this problem is known to take exponential time to solve, why isn't it being used as a cryptographic primitive?

# Answer
> 7 votes
I think there are really three issues buried in your question.

1. What's Simon's Problem?
2. What's a plain english description of the function involved in Simon's Problem?
3. Why isn't this problem a cryptographic primitive?

I can't really speak to 3 as cryptography is not my area. I can take a crack at 1 and 2 for you though. The distinction between 1 and 2 is, I think, important.

Simon's problem is one of discovering the parameter to a function *given a black-box to that function* and some basic information about the function. So, an algorithm to solve this problem takes as its input a black-box to a function and gives a output a binary string. Our goal is to reduce the number of queries to that black box. I think people tend to miss this point and focus on the internals of the function itself.

All we know about the function $f$ is that our black-box can compute it for us in constant, $O(1)$, time, and that if $f(x) = f(y)$, then either $x=y$ or $x \oplus y = s$. We want to know the value of $s$. A brute force, classical computing solution might give you a better feel for the problem. Here it is:

1. Feed all $n$ bit binary strings to the black-box and save each input-output pair to a table.
2. If no two inputs produce the same output then it must be the case that the parameter $s$ is $n$ bit $0$. Otherwise, two inputs will produce the same output and $s$ is the result of XOR'ing those inputs together.

In the worst case, we have to query all $2^n$ inputs leading to $O(2^n)$ query complexity.

Querying the black-box is at the heart of Simon's problem. *We need not concern ourselves with how to construct the black-box, i.e. how to compute $f$, as that is not what the problem is about.* I don't believe that Simon's problem is practically useful beyond the fact that it helps establish some complexity results about Quantum Computers. It's main significance is that it was an inspiration for Peter Shor's factoring algorithm.

# Answer
> 3 votes
What the article means by

$$f : \\{0,1\\}^n \rightarrow \\{0,1\\}^n$$

is that the input and output of the function is a binary string of length $n$.

As for the problem itself, the idea is that we have such a function $f$ with the added property that there is a special string $s$ such that for any two binary strings of length $n$, if the function gives the same result when passed either of them, they are either (1) equal or (2) give $s$ when XOR'ed together. The actual problem is: given the function (as a black box), find what $s$ is.

I can't say for certain why this isn't used as a cryptographic primitive, but there's at least one potential reason that I can see: **we haven't taken into account the time it takes to actually *construct* such a function in the first place**. If making such a function is equally (or even *more*) difficult; then it's much easier to imagine why it wouldn't be used.

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


# Question
Title: Transform values of hash functions like MD5 into numbers
I have read about the hash function MD5. I found an online calculator which counts the value of MD5 for different data. But the MD5 function returns as result strings like `735b90b4568125ed6c3f678819b6e058`, so I can't apply any numerical operation to this value, e.g. `mod`.

How can I transform values like these into numbers?

# Answer
> 5 votes
The output `735b90b4568125ed6c3f678819b6e058` is just a hexadecimal representation of a 128-bit (in binary) number, which corresponds directly to an integer between $0$ and $2^{128}-1$. Therefore, you can think of MD5 as returning a numeric value. You should be able to make the conversion from hexadecimal string to integer trivially using any programming language (if not, Stack Overflow is the place to go to).

---
Tags: algorithms, hash
---


# Question
Title: If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument
I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is computed in $O(n^2)$.

This is what I have/tried.

Let $ \ f(x)$ be a OWF that can be computed in $k^c$. Then we can construct a OWF:

$$ f'(x'||\ x'') = f(x') || \ x'' $$ where: $$ |x'| = k \\ |x''| = k^c $$

Notice the size of the input for $f'$ is $n = k^c + k$.

Its intuitively "obvious" f' is a OWF since f is OWF (or you can go ahead and prove it by contradiction if you want to be pedantic). But how come it takes $O(n^2)$ to compute the OWF f'? Does this depend on the Turing Machine model being used to compute f'?

It seems to me you can just parse the input $x'||x''$ (separate it so that you can feed the appropriate thing to the original f) in O(n) and then compute $f(x')$ in $k^c = O(n)$ and then concatenate it to $x''$ and print f(x')|x'' (printing takes at most $O(n)$). It seems to me it takes $O(n)$ and that the bound $O(n^2)$ is unnecessarily un-tight (I know $cn + d = O(n) = O(n^2)$). Or maybe the parsing algorithm is "harder" than I expect it... even if you just append the lengths at the beginning just for parsing purposes , isn't the time to compute $f'$ just $O(n)$?

Does someone understands why my O(n) argument is wrong?

# Answer
When we talk about quadratic running time, we mean $O(n^2)$ running time where $n$ is the length of the input -- i.e., the running time is a constant times the square of the length of the input. Make sure you understand what the length of the input is here. By padding the input, we've made the input longer. Even though the overall running time doesn't change, the size of the input is larger, so relatively speaking, the running time is now a slower-growing function of the input size.

For instance, suppose $f$ can be computed in cubic time: in $O(k^3)$ time, where $n$ is the length of the input to $f$. Now consider the padded function $f'$, which has been padded out to the length $k^{1.5}$. What is the running time of $f'$? Its running time remains $O(k^3)$, but now the input is of size $k^{1.5}$. Re-expressing the running time of $f'$ as a function of its input size, we let $n=k^{1.5}$ be the length of the input to $f'$, and then notice that $k^3=n^2$, so the running time of $f'$ is $O(n^2)$: quadratic in the size of its input.

---

On your specific question: yes, the $O(n^2)$ seems unnecessarily loose. Your argument that the running time of $f'$ is $O(n)$ (linear in the length of its input) looks right to me. I don't know why they mentioned $O(n^2)$ as opposed to $O(n)$.
> 5 votes

---
Tags: asymptotics, cryptography, one-way-functions
---


# Question
Title: Computer Vision - Algorithm for reconstructing tilted image
Recently I've seen this very good apps

https://play.google.com/store/apps/details?id=com.kingjim.shotnote&hl=en https://itunes.apple.com/JP/app/id411332997?mt=8

this apps reconstruct the image from the camera based on the marker (this is what I think :) ) it also have a special paper that have marker. What I've still haven't got is what is the algorithm to do this? what computer vision theory used in this one? I understand artificial intellegence and basic computer vision, is there anyone have the ide how can this be done? at first I thought this based on stereo image but based on what I've studied before stereo vision need two camera. I hope my question is clear enough but if is there any information needed please ask in the comment :)

Thank you!

# Answer
It detects 4 markers lying on the corners of the note. One of the markers is unique to able to determine the orientation. Because the actual size and layout of the form is known, a perspective warp can be computed, bringing the scanned image to a canonical (fronto-parallel) form. Then, OCR is carried out in the region where date and time is expected. The rest of the content are taken as image and saved on the smartphone.

For OCR, character segmentation and classification might be your key words. For Marker Detection, generally black-white polygonal regions are detected and expected to be quad-formed. The rest of the blobs are filtered out and you end up with the markers.
> 4 votes

# Answer
Stereo Vision doesn't require two cameras, it only requires two views, so if there is a translation between two frames of from one camera you can apply Stereo Vision.

Having said that, the app you saw probably doesn't use any stereo information. Most apps of this kind just detect the four corners of the page (sometimes with help from the user) and warp them to a rectangle.
> 1 votes

---
Tags: algorithms, artificial-intelligence, computer-vision
---


# Question
Title: Rice Theorem - What is non-trivial property?
Every nontrivial property of the recursively enumerable languages is undecidable.

What exactly is nontrivial property?

# Answer
A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property.

To see why, note that such a property can be decided by a very simple Turing machine, which accepts/rejects every Turing machine representation.
> 6 votes

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


# Question
Title: Is safety-critical software a subset of real-time software?
I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

I tried thinking of several examples, but they always seem somehow related to some physical system (e.g. flight control, radiation therapy, nuclear power) and therefore have some implicit timing constraints/deadlines. Even somewhat contrived "safety-critical" systems such as high-frequency trading are still real-time.

Note: I am not interested in a very specific subset of the code which is timing independent, but on something more complete, consisting of a substantial part of a complete application.

# Answer
> 4 votes
The important thing is to understand that real-time software is a strict subset of "software with timing constraints".

If you want to be nitpicky about it, *all* software has timing constraints: if the algorithm is correct, but it's not gonna give you the correct answer until one billion years from now, then it's not very useful. So one can make a quite reasonable argument that all software has *some* sort of timing constraint. Even, say, a sorting routine has *some* timing requirements.

Does that mean we should say that all software is real-time software? No. That stretches the definition of real-time software to a point where it becomes useless. I would never call mergesort a real-time application (even though there *is* an upper bound on the running time of mergesort).

Instead, we should realize that not all timing requirements are created equal. Empirically, some timing requirements are very strict and are non-trivial to achieve, while others are straightforward to achieve. For instance, "the brakes must be applied within 30 ms of pressing the brake pedals" is non-trivial to achieve: if we've got some generic software running on a multiprocessor polling the brake pedal sensors, if we are not careful, we could easily end up failing to notice the brake pedal has been pressed for over 30 ms. For instance, maybe a garbage collector kicks in and runs for 50ms, preventing the application code from running for the duration; maybe several other processes are running and the sensor polling process doesn't get a chance to run for a stretch of 50ms; or any number of other possibilities. So that would be an example a situation where we need to apply special techniques to ensure that the timing requirement is met. Software like that is called real-time software.

In contrast, when we have software that technically has some timing requirements but where the timing requirements are relatively easy to achieve, we do not call it real-time software (in general). For instance, consider a web browser/web site: "when I click on a link to CNN, the CNN web page should start to show up within a few seconds, or a minute at most"; or, "when I open a web page in the browser, it should either load within a minute or so, or else the browser should show a visible indication that it was unable to load the page". Those are timing requirements that do not require special real-time techniques to meet. In particular, no one would call your web browser an example of real-time software. There might be some timing requirements, but no one would call your web browser a real-time system, and your web browser was not built using real-time implementation techniques.

With that understanding, it is straightforward to see that there is plenty of safety-critical software that is not real-time software. There are safety-critical systems that are not built using real-time techniques because, while they might have *some* sort of timing requirement, the timing requirement is easy enough to meet that there is no need for special real-time techniques or systems.

For instance, think of a medical X-ray machine. One requirement might be "when the doctor programs it to irradiate at X units of beam strength for Y minutes, the machine does it, and it does not generate more than X units or run for more than Y minutes". Another requirement might be "the machine beeps whenever it is emitting radiation". Both of these requirements can be achieved without real-time systems. Consequently, I would call this a safety-critical system but not a real-time system.

# Answer
> 11 votes
> I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

A good example of a safety critical program which does not itself have to meet real time constraints is a compiler.

If a compiler has code generation bugs, then even if the programmer wrote a safe program, the emitted machine code may still fail to meet some necessary guarantees. As a result, the standard practice at many development teams developing safety-critical software is to generate code with compiler optimizations turned off, and then to manually review the generated machine code.

The Compcert C compiler has a machine-checked formal proof showing that it never generates incorrect assembly programs for any input program. As a result, it is possible to (a) limit code review to the C source code, and (b) permit the compiler to do optimization passes, without compromising the safety of the overall system. (See for example *Towards Formally Verified Optimizing Compilation in Flight Control Software*...)

Obviously, if you are trusting the compiler to generate code for flight control software, it is safety-critical. Equally obviously, a compiler is not real time software.

# Answer
> 4 votes
No, not all safety-critical software is real-time. Suppose you have an industrial batch process that generates acidic waste, which must be neutralized by being mixed with an appropriate amount of alkali before being poured down the drain. It's important to use the right amount of alkali: if you use too little, your waste is still acidic; if you use too much, your waste is alkaline. Therefore, the computer program that tells you how much alkali to use is safety-critical.

However, it is not real-time. If, for some reason, the program takes unusually long to tell you how much alkali to use, you just have to wait unusually long before neutralizing your waste and disposing of it. As long as you don't run your process again before you've disposed of the last batch's waste, you will never have more waste than you can deal with.

---
Tags: programming-languages, software-engineering
---


# Question
Title: Can one reduce a problem of unknown complexity to a hard problem to show hardness?
In this paper (page 3 Theorem 1) the authors want to prove that their problem is NP-complete. Their method is as follows. Let their problem be known as $P$. They show that their problem can be written as a $0\text{-}1$ integer program. Then they claim that $0\text{-}1$ integer programs are NP-complete and therefore their problem $P$ is NP-complete.

I find this proof hard to believe. For the problem $P$ to be NP-hard I think one has to reduce the $0\text{-}1$ integer program into an instance of problem $P$ and not the other way around.

Please can someone explain if this proof in the paper is acceptable?

# Answer
You should not believe such a proof (still a claim might be true even if the proof is not). You can also see this by suddenly being able to "prove" silly things. The 2-SAT problem is a special case of the $k$-SAT problem, where each clause has exactly two literals. There are plenty of algorithms that solve 2-SAT in polynomial time, thus 2-SAT is in P. On the other hand, 3-SAT is already NP-complete.

Consider the following "theorem" and "proof".

> "**Theorem:**" 2-SAT is NP-complete. **"Proof:"** Given an instance of 2-SAT, duplicate a literal in every clause to produce an instance of 3-SAT. Because 3-SAT is NP-complete, we conclude that so is 2-SAT.

We of course know this is nonsense.
> 6 votes

# Answer
The proof is not correct. As you've indicated the reduction needs to go in the other direction, i.e. integer programming must be reduced to their problem, not the other way around.
> 6 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: How to determine the address of an element in a square matrix given the base address?
I was asked this question in examination. A square matrix $M$ of size $10 \times 10$ is stored in memory with each element requiring 4 bytes of storage. If the base address at $M\[0\]\[0\]$ is $1840$, determine the address at $M\[4\]\[8\]$ when the matrix $M$ is stored row majorwise. I seriously don't understand this question at all. What kind of problem is this? How to solve these kind of problems?

# Answer
> 1 votes
Is this a homework question? What is the point you exactly don't get? M\[0\]\[0\] is a memory location stored at some address like 0x5468792. M\[4\]\[8\] is another one like 0x5478954 (numbers are not correct). The question asks you to compute the address in a multi-dimensional array, given the first pointer.

---
Tags: data-structures, matrices, memory-access
---


# Question
Title: Differences between the Actor Model and Communicating Sequential Processes (CSP)
When we look at the Actor Model and Communicating Sequential Processes we see that they are both trying to do concurrency based on message passing, yet they are distinct.

(We see implementations of the CSP Model in go-lang's goroutines (and Clojure's core.async) and the Actor Model in Scala's Akka toolkit)

I'm trying to get a simple list of the differences between the Actor Model and CSP. So far I have:

Is this correct? Is there anything I'm missing?

**Assumptions**

* When I say 'actor model' - I mean the theoretical basis behind the implementation in Scala's Akka framework

# Answer
> 6 votes
Here is how I think Erlang works. I believe Akka is very similar.

Each process has a single mailbox. Messages are put into the receiver's mailbox by the sender, and fetched by the receiver using pattern matching. This matching process can change message ordering in the sense that the oldest message in a mailbox may not match, but a younger one does. In this case the younger one is consumed first. Other than that, message ordering is preserved.

With this in mind, the asynchronous $\pi$-calculus extended with input pattern matching input from buffer describes Erlang (and hence Akka) semantics accurately, although one needs to do a bit of work in the encoding, since the $\pi$-calculus doesn't have the restriction to single channels per process. However, one usually doesn't want an encoding, but rather a calculus that models the target system directly. Such a calculus exists, and it's called Featherweight Erlang. It is by Mostrous and Vasconcelos. Their paper focusses on typing, but you can ignore that and just look at the untyped calculus in Section 3.

---
Tags: concurrency, message-passing
---


# Question
Title: Counting elements that are greater than the median of medians
Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition.

Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. The algorithm is roughly:

> **Input**: an array of $n$ elements and $i$, the number of the order statistic to return from the elements.
>
> 1. Divide the $n$ elements into $\lfloor n/5 \rfloor$ groups of 5 elements each along with an optional group containing $n\mod{5}$ elements (resulting in $\lceil n/5 \rceil$ groups.)
> 2. Find the median of each of the groups by sorting.
> 3. Recurse, using the $\lceil n/5 \rceil$ medians as the array and $\lfloor\lceil n/5 \rceil/2\rfloor$ as the order statistic, resulting in the median-of-medians.
> 4. Partition the $n$ elements around the median-of-medians (using a quicksort-like $O(n)$ partitioning algorithm.
> 5. Letting $k-1$ be the number of elements less than the median-of-medians, if $i = k$, return the median-of-medians. Otherwise recurse: if $i \< k$ then recurse finding the $i$th order statistic of the $k-1$ elements less than the median-of-medians; if $i \> k$, then recurse finding the $i-k$th order statistic of the $n-k$ elements greater than the median-of-medians.
>
> **Output**: the $i$th order statistic of the $n$ numbers.

In the proof of the runtime, CLRS argue that the number of elements greater than the median-of-medians is at least:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) $$

The reasoning is that half of the medians are greater than the median-of-medians, and each of those medians' groups has at least three elements greater than the median-of-medians (the median itself plus the two elements greater than the median.) That would result in

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) $$

for the lower bound on the number of elements greater than the median-of-medians.

But we must account for two things: the group containing the median-of-medians (the median-of-medians is not greater than itself) and the group that contains the modulo leftovers. To account for the group containing the median-of-medians, we subtract 1, resulting in:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 1 $$

and I *think* that for the modulo leftovers group, we should subtract 4, because the least number of elements in the group is 1. So that would give:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5 $$

which can be transformed into

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) + 1 $$

Why does my analysis lead to a lower-bound 1 greater than that given in CLRS?

# Answer
In

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) $$

we are subtracting 2 in order to discard the group containing the median of medians and the group of leftovers. So, 2 is the number of groups we are discarding.

First of all, note that there may not be a group of leftover elements: if $n$ is an exact multiple of 5 there will be no leftover group. We are interested in bounding from below the number of elements greater than the median-of-medians in the worst case, so suppose that a leftover group exists. Therefore, it will contain at least an element and no more than 4 elements. If you want to reason in terms of elements to be discarded and not in terms of groups, then we must discard exactly 3 elements for the group containing the median of medians (including the median of the medians), and at most 2 element from the leftovers group (if this group contains 1 or 2 elements you do not discard any element; if this group contains 3 or 4 elements, then you discard respectively 1 or 2 elements which are greater than the group's median). So, you discard in the worst case (leftover group with 4 elements) 3 + 2 elements:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5 $$
> 3 votes

---
Tags: algorithm-analysis, combinatorics, discrete-mathematics
---


# Question
Title: Turing Machine 'marking' specific portion of encoding
Given a turing machine $T$ that receives an encoding of another turing machine and a word $\<M\>\<w\>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states?

For example, if I want to show that the language $L = \\{\<M\>\<w\>\\}$ such that when we run $w$ in $M$ we will visit at least two unique states different than the starting state.

Now for this, I suggested this algorithm, but I am not sure it is even compuatable:

> Given the encoding $\<M\>\<w\>$, we will run through the encoding and 'mark' all states that can be reached from the starting state of $M$, if two or more states have been marked after finishing, accept, else, reject.

I know that since this an encoding of a turing machine and a word, we indeed -can- run through the encoding. But can we really do the 'marking' operation? if so, how?

# Answer
A quick answer: if the tape alphabet is large enough ($\geq 18$ symbols), then $L = \\{\langle M,w\rangle \mid $ M on w visits at least two unique states different than the starting state $\\}$ is undecidable; indeed for every $M$ with $n$ states there is an equivalent $M'$ with only 2 states such that for all $x$ $M(x)$ halts if and only if $M'(x)$ halts. To prove that L is undecidable, you can use the following reduction from the halting problem: given $\langle M\rangle$ build the equivalent two states machine $M'$ (the starting state plus another one), and add an additional final and accepting third state that can be reached only if $M'$ halts when run on the empty tape. Clearly $\langle M',w\rangle \in L$ (i.e. visit the second *and the third accepting state*) if and only if $M$ halts ($w$ is irrelevant), so if $L$ is decidable you can solve the halting problem which is a contradiction.

Reducing the number of symbols, doesn't help too much, indeed you can encounter Turing machines that behaves like the Collatz function (e.g enter the third state only when the sequence reaches 1) ... and it is an open problem if for all $n$ the Collatz function reaches 1.

For a proof that you can build an Universal Turing machine (using 2-tag simulation) with only 2-states and 18 symbols see:

Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215–240, Nov. 1996.

Finally, as an exercise, you should be able to easily prove that the following language is undecidable:

$L' = \\{ \langle M,w,k \rangle \mid$ when run on w the Turing machine M visits at least $k$ different states $\\}$
> 2 votes

---
Tags: computability, undecidability
---


# Question
Title: Existence of NP problems with complexity intermediate between P and NP-hard
Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete.

I could never quite understand the proof of the above result. The proof I saw in a textbook was starting with the assumption that one can enumerate all P and NP-hard problems, and then proceeding with a construction of a function that didn't fit in either. However, this construction seemed a bit fishy to me; in particular, the assumption that one can start with enumerated set of problems in a particular class, the NP.

Could you refer me to a clear self-contained proof of the statement in the 1st paragraph? More generally, what would be a good reference for proofs of such results?

# Answer
> 4 votes
The result you're describing is called 'Ladner's Theorem.' The Wikipedia article on 'NP-Intermediate' is probably a good place to start - you can find references to Ladner's original paper there.

There's also an extensive list of such problems on the cstheory Stackexchange.

For a couple of proofs of Ladner's Theorem, check out this note adapted from Downy & Fortnow's paper 'Uniformly Hard Languages'.

---
Tags: complexity-theory, reference-request, np, p-vs-np
---


# Question
Title: Complexity analysis of while loop with two conditions
I am curious how to do a line by line analysis of this piece of code using the "Big O" notation.

```
i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}

```

How I should represent number of iterations for the loop? Is good if I will do some assumptions or I should write min(n, m)?

Small extension after @Patrick87's comment to show why I am not sure that min() is a general solution:

```
i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}
if ( i < n )
{
      while ( ( i < n ) )
      {
         //do something
         i++;
      }
}
else
{
      while ( ( j < m ) )
      {
         //do something
         j++;
      }
}

```

How right now we can connect a number of iterations of the first loop and second one if we don't know which condition broke the condition of the first loop?

# Answer
As Patrick87 pointed out. The first loop is $\min(m,n)$. As for your extended question, it's unclear if you want best, worst, or average case. We typically look at worst case. Either way, you seem to be focused on a single execution when *you really need consider all possible $i$ and $j$ values.* So, let's do that:

1. $m = n$.

In this case the additional conditional does no work, so the total run time is still $O(\min(m,n))$.

1. $m \< n$.

When this is true, then the first loop terminates due to $j$. The conditional will then carry out the first case $i \< n$ and terminate after $O(n-m)$ iterations. The total number of operations is then $O(n-m+m)= O(n)$ operations.

1. $m \> n$.

This case is equivalent to the second case but the result is $O(m)$.

Now observe that cases 1,2, & 3 are all equivalent to $O(\max(m,n))$. This is the running time for your code.

So back to your "how to" question. You need to do a good, thorough case analysis for multi-conditional loops just like you need to do with conditionals. Then analyze the running time of each case and, assuming your doing worst case analysis, take the largest running time.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis
---


title: How to mark things in the input?

text:
# Question
Title: How to mark things in the input?
> ### Sipser theorem 4.4\*
>
> $E\_{DFA} = \\{ \langle A \rangle \mid \text{A is a DFA and } L(A)=\emptyset\\}$ is decidable.

I could not quite understand the solution, I'll quote it:

> On input $\langle A \rangle$ where $A$ is a DFA:
>
> 1. Mark the start state of A
> 2. Repeat until no new states get marked:
> 3. Mark any state that has a transition coming into it from any state that is already marked.
> 4. If no accept state is marked, accept; otherwise, reject.

My question is, what does it mean to even 'mark' something in the encoding? how do we do this? The encoding is merely a word from $\\{A,c\\}$, how would you 'mark' states?

# Answer
It's just a colloquialism. It means, you keep a set of states that have been marked. Initially the set is empty. When you mark a state, you add it to that set.
> 1 votes

# Answer
Assume your inputs are encoded in some alphabet $\Sigma$. You can then extend the tape alphabet to $\Sigma \cup \hat\Sigma$ (and probably some control symbols) where $\hat\Sigma = \\{ \hat a \mid a \in \Sigma\\}$.

Now, when you want to mark a part of the input, you just exchange the symbol(s) by its (their) marked version(s).
> 0 votes

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


# Question
Title: What is the order of the Pancake graph in Given example & what are the properties of Pancake graph?
Pancake graph have least diameter & degree (log n/ log log n)

pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}.

pancake Graph with order-3 will be one single line with one hexagonal, labeled with permutation of node {123, 132, 213, 231, 312, 321}.

Similarly for order-4 graph will be with 4-hexagonal.

**This graph is in three dimension or four dimension? if this graph is in four dimension, then how graph will look like in three dimension?**

# Answer
> 0 votes
Based on the example I infer the following structure.

The pancake graph seems to be defined with flipping pancakes in mind. For order $n$ we take all $n!$ permutations of the numbers $1,\dots,n$ as vertices of the graph. The vertices represent orderings of the pancakes, with the topmost pancake listed first, and the other pancakes are listed from top to bottom. The edges represent flips. Take any first $k\>1$ numbers in a vertex, and reverse that prefix. An edges is added between those to vertices. Thus $i\_1, \dots, i\_k, i\_{k+1}, \dots, i\_n$ flips to $\overleftarrow{i\_k, \dots, i\_1}, i\_{k+1}, \dots, i\_n$.

With $n=3$ there are obviously $3! =6$ vertices. $123, 132, 213, 231, 312, 321$. Each node has degree 2 (i.e., has two neighbours) as I can flip topmost 2 pancakes or all 3 of them. From $123$ I thus have edges to $213$ and $321$. The other edges follow the same rule.

Your example figure has missing edges. All vertices should have three neighbours for $n=4$. So $1324$ should also be connected to $4231$ flipping all the pancakes.

The above diagram have dimension 4.

PS. The pancake graph is important in the context of "sorting by reversal", for instance giving bounds on the number of steps to sort any permutation into the identity permutation. This bound is of course the diameter of the pancake graph. The field has a famous paper by Papadimitrou and Gates (of Microsoft fame).

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


title: Case distinction in B-tree deletion

text:
# Question
Title: Case distinction in B-tree deletion
Here is how deletion in B-trees is described:

> 1. If the key k is in node x and x is a leaf, delete the key k from x.
> 2. If the key k is in node x and x is an internal node, do the following.
>
> a) If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
>
> b) If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
>
> c) Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.
> 3. If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) has only t-1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.

What is the actual difference between case 1 case 3? Both seem to be directing to a leaf node.

# Answer
In simple terms, "case 1" dictates what happens when we reach the appropriate leaf node.

"case 3" tells us what we do when we're still higher up in the tree.

---

Small example: suppose we have {x, y, z} in a tree like so:

```
  y
 / \
x   z

```

and we delete x. We start out at y and hit case 3, determining that "x" must be in the left subtree.

```
  y <-- we are here, and hit case 3
 / \
x   z

```

Thus, we recurse on the left subtree. We then reach x, and execute case 1.

```
                                  y
                                 / \
we are here, and hit case 1 --> x   z

```
> 1 votes

---
Tags: data-structures, search-trees
---


# Question
Title: iterating over subsets by switching one element at a time
How do I iterate over all the $k$-element subsets of $\\{1,2,\dots, n\\}$ by switching one element at a time?

```
123
134
234
124
145
245
345
135
235
125

```

This comes from Ch2 of Combinatorial Algorithms by Nienhuis and Wilf.

Equivalently I am asking for a Hamiltonian circuit on the Johnson graph of $k$ element subsets of a set of $n$ elements connected if their intersection has $k-1$ elements.

---

I am trying to understand how the equation $$A(n,k) = A(n-1,k), \overline{ A(n-1,k-1)}\otimes \\{n\\}$$ from Nienhuis-Wilf leads to a type of "gray code" for subsets. In fact, it is the gray code when you restruct to $k$-element sets.

Here, $A(n,k)$ is an ordering, looping over the $k$-element subsets of $\\{1,2,\dots, n\\}$. The notation $\overline{ A(n-1,k-1)}\otimes \\{n\\}$ means we should list the $k-1$-element substs of $\\{1,2,\dots, n-1\\}$ and append the element $n$ to each element of that list.

This equation can also be thought of a set theoretic version of the binomial coefficient identity

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Using this formation I came up a means of listing all the subsets in order.

Here `gc(n,k)` is returning an array of $k$-element arrays, enumerating the $k$-element subsets of $\\{1,2,\dots, n\\}$.

```
def gc(n,k):
    if(k==1):
        return [[i+1] for i in range(n)]
    elif(n == 0):
        return []
    else:
        L = [ x+ [n] for x in gc(n-1,k-1)]
        return gc(n-1,k)+ L[::-1]

```

How do I find the predecessor or successor of a given subset without generating all the subsets? I wrote some python code for this, which is different from what is in the textbook. It still doesn't return the correct answer.

```
def S(n,k,a):
    if k == 1:
        return [(a[0] + 1)%n]
    elif(a[-1] == n-1):
        return P(n-1,k-1, a[:-1]) + [n-1]
    else:
        return S(n-1,k,a)

def P(n,k,a):
    if k == 1:
        return [(a[0] - 1)%n]
    elif(a[-1] == n-1):
        return S(n-1,k-1, a[:-1]) + [n-1]
    else:
        return P(n-1,k,a)

```

This looks pretty close to the recursion in Nienhuis-Wilf but I would like to understand where I am going wrong in my implementation.

# Answer
Here is how to convert a number from $\binom{n}{k}$ to a subset of $\binom{\[n\]}{k}$, and vice versa. This is known as *inductive counting*. I'll use your formula $$ \binom{\[n\]}{k} = \binom{\[n-1\]}{k} + \binom{\[n-1\]}{k-1} \times \\{n\\}. $$

Given a code $x \in \[0,\binom{n}{k})$, the idea is that the first $\binom{n-1}{k}$ codes will be used to code the $\binom{\[n-1\]}{k}$ part, and the rest will be used to code a subset in $\binom{\[n-1\]}{k-1}$ which will be completed to the required subset by adding the element $n$. Here is the relevant quasi-python code:

```
decode(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode(n-1, k, code)
  elif:
    return decode(n-1, k-1, code - binom(n-1, k)) + [n-1]

```

Encoding is the reverse process, and mirrors it exactly:

```
  encode(n, k, S):
    if k == 0:
      return 0
    elif n-1 not in S:
      return encode(n-1, k, S)
    else:
      return encode(n-1, k-1, S[:-1]) + binom(n-1, k)

```

Using these subroutines, you can compute the successor and predecessor of a given subset. You could also do it directly, for example by "unrolling" the resulting code, but this is a programming question which you should be able to solve for yourself in a couple hours.

---

The preceding doesn't produce a Gray code at all. You can obtain a Gray code by *reversing* the second half in your fundamental formula (this is the meaning of the overline). The corresponding decoding function is

```
decode2(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode2(n-1, k, code)
  elif:
    return decode2(n-1, k-1, binom(n, k) - 1 - code) + [n-1]

```

I'll leave the encoding function as an exercise. The proof that this forms a Gray code is by induction. You prove a more general claim, stating what are the first and last sets in the ordering for any given $n,k$, and given that you prove by induction that the result is a Gray code. Details left to you.
> 1 votes

---
Tags: algorithms, graphs, finite-automata
---


title: Importance of the empty string

text:
# Question
Title: Importance of the empty string
In the sense of a string distinct from a null reference string, what is the importance of an empty string in CS (and specially in formal languages)?

Why do you need a separate concept, that of 'empty string', which even has it's own Greek letter (ε)?

Couldn't just an EOL character replace it?

# Answer
> 13 votes
There is a **mathematical meaning** for the empty string. Indeed the concatenation product of words is an associative operation. But this operation also has a **neutral element**, namely the empty word. For this reason, the empty word is also frequently denoted by $1$, which allows one to write, for each word $u$, $$ 1 \cdot u = u = u \cdot 1 $$

Of course, if the alphabet is $\\{0, 1\\}$, it is not a good idea to denote the empty word by $1$ and this is probably the reason why the notation $\varepsilon$ (or sometimes $\lambda$) was introduced. But as Yuval Filmus pointed out, the empty word is a word of length $0$, that is, it contains no letter.

It is certainly disturbing to denote the empty word by $1$ (or by a greek letter $\varepsilon$ or $\lambda$), but you have to take it as a conventional notation, in the same way you denote the empty set by $\emptyset$.

# Answer
> 9 votes
The empty string is like zero. It represents "nothing" but is a fundamental concept. As a very simple example, a word $a$ is a prefix of a word $b$ if $b = aw$ for some word $w$. If you don't allow the empty string, a word wouldn't be a prefix of itself.

The EOL character is a character in a specific character set. If we're interested in strings over $\\{0,1\\}$, we have no EOL. Additionally, EOL is a character, so a string consisting of EOL is not empty.

# Answer
> 6 votes
Using an end-of-line (EOL) character is equivalent in terms of expressive power – anything you can do with the empty word $\varepsilon$, you could redefine to do with EOL instead – but using it would be a monumental pain in the butt. The conventional definitions are:

> An *alphabet* is a finite set $\Sigma$ of symbols. A *string* $s$ over the alphabet $\Sigma$ is a finite sequence $s\_1\dots s\_\ell$, where each $s\_i\in\Sigma$. We write $|s|$ for the *length* of $s$, with $|s\_1\dots s\_\ell|=\ell$; the unique word of length zero is denoted $\varepsilon$. A *substring* of $s\_1\dots s\_\ell$ is any string $s\_i\dots s\_j$, where $1\leq i\leq j\leq \ell$. The *concatenation* of strings $s\_1\dots s\_\ell$ and $t\_1\dots t\_m$ is the string $s\_1\dots s\_\ell t\_1\dots t\_m$ of length $\ell+m$.

Compare this with:

> Let $\dashv$ be a distinguished *end of line* symbol. An *alphabet* is a finite set $\Sigma$ of symbols such that ${\dashv}\in\Sigma$. A *string* $s$ over the alphabet $\Sigma$ is a finite sequence $s\_1\dots s\_\ell$ where $s\_i\in\Sigma\setminus\\{{\dashv}\\}$ for $i\<\ell$ and $s\_\ell={\dashv}$. We write $|s|$ for the *length* of $s$, with $|s\_1\dots s\_\ell|=\ell-1$. A *substring* of $s\_1\dots s\_\ell$ is any string $s\_i\dots s\_j{\dashv}$, where $1\leq i\leq j\< \ell$. The *concatenation* of strings $s\_1\dots s\_\ell$ and $t\_1\dots t\_m$ is the string $s\_1\dots s\_{\ell-1} t\_1\dots t\_m$ of length $\ell+m-2$.

Note the extra fiddliness and the potential for off-by-one errors, especially in the definition of concatenation. Also, consider defining automata over these terminated strings. In addition to checking whether its input has whatever properties the language requires, any automaton must now check that the last character of the input is ${\dashv}$, which will (I think) add two states to every automaton.

The empty string $\varepsilon$ has the same role as zero does in the natural numbers. It's the identity for the most basic operation (concatenation for strings, addition for naturals). This is important if you want to build any kind of algebraic structure, such as groups or monoids, which gives access to a large area of potentially useful mathematical results. More straightforwardly, it makes a great base-case for inductions, since the hypothesis is often trivial for the empty string. Indeed, when you do induction on strings, you're implicitly using the following inductive definition of $\Sigma$-strings:

* $\varepsilon$ is a $\Sigma$-string;
* if $s$ is a $\Sigma$-string and $\sigma\in\Sigma$, then $s\sigma$ is a $\Sigma$-string.

That also becomes more fiddly with terminated strings:

* ${\dashv}$ is a $\Sigma$-string;
* if $s{\dashv}$ is a $\Sigma$-string and $\sigma\in\Sigma\setminus\\{{\dashv}\\}$, then $s\sigma{\dashv}$ is a $\Sigma$-string.

Of course, you could do it the other way round and say that if $s$ is a string, then so is $\sigma s$. At that point, there's little to choose between terminated and unterminated strings but your induction might be better suited to adding characters on the end than the beginning.

Terminated strings are fine for programming with but they're not well suited to mathematics. When you're programming, you need some way of knowing when the string $s\_1\dots s\_\ell$ ends; when you're doing mathematics, it's obvious that $s\_\ell$ is the last character from the way the string is written.

---

I've just noticed that you ask about the difference between a null reference and the empty string. A null reference is no string at all; the empty string is a string but it has no characters on it. If you like, it's the difference between having a blank piece of paper (empty string) and having no paper at all (null reference).

# Answer
> 5 votes
Short answer: the empty *set* (i.e. the set of strings which contains no strings) is like zero, but the empty *string* (i.e. the set of strings which contains one zero-length string) is like one.

One way to axiomatise formal languages is as an idempotent semiring. A semiring is a structure with two binary operations $+$ and $\cdot$, and two distinguished elements $0$ and $1$, and obeys the following axioms. First off, $+$ is a commutative monoid with identity $0$:

$$(A + B) + C = A + (B + C)$$ $$0 + A = A + 0 = A$$ $$A + B = B + A$$

Secondly, $\cdot$ is a monoid with identity $1$: $$(A\cdot B)\cdot C = A\cdot(B\cdot C)$$ $$1\cdot A = A\cdot 1 = A$$ Multiplication left and right distributes over addition: $$A\cdot (B + C) = (A\cdot B) + (A\cdot C)$$ $$(A + B)\cdot C = (A\cdot C) + (B\cdot C)$$ Multiplication by 0 annihilates: $$0\cdot A = A\cdot 0 = 0$$ and finally, addition is idempotent: $$A + A = A$$

"Addition" can be interpreted as set union and "multiplication" can be interpreted as string concatenation.

Oh, and the link goes very deep. The Kleene closure operator, which is intuitively defined as:

$$A^\* = 1 + A + A^2 + A^3 + \cdots$$

behaves like exponentiation. Think of the power series of $e^x$, plus the fact that addition is idempotent.

Terminal characters behave like variables. In particular, we can define evaluation at zero:

$$a(0) = 0$$ $$(AB)(0) = A(0) B(0)$$ $$(A+B)(0) = A(0) + B(0)$$ $$A^\*(0) = 1$$

Given a regular expression $E$, $E(0)$ is either $0$ or $1$. It is $1$ if the empty string is a member of $E$, and $0$ otherwise.

We can also define a derivative, called the Brzozowski derivative:

$$\frac{\partial a}{\partial a} = 1$$ $$\frac{\partial b}{\partial a} = 0$$ $$\frac{\partial (A+B)}{\partial a} = \frac{\partial A}{\partial a} + \frac{\partial B}{\partial a}$$ $$\frac{\partial AB}{\partial a} = A(0) \frac{\partial B}{\partial a} + \frac{\partial A}{\partial a} B$$ $$\frac{\partial A^\*}{\partial a} = \frac{\partial A}{\partial a} A^\*$$

The only odd rule here is the one for multiplication. It's almost like the familiar product rule; the difference is due to the fact that concatenation is non-commutative.

What the derivative intuitively means is that $\frac{\partial E}{\partial a}$ is the set of strings in $E$ which start with the symbol $a$, but with that $a$ removed. So $a \frac{\partial E}{\partial a}$ is the set of strings in $E$ which start with $a$.

Thinking about it for a moment, if ${a\ldots z}$ is the alphabet, then:

$$E = E(0) + a \frac{\partial E}{\partial a} + b \frac{\partial E}{\partial b} + \cdots + z \frac{\partial E}{\partial z}$$

This is Taylor's theorem, only for regular languages. Moreover, it is also a rule for creating DFAs directly from regular expressions! $E(0)$ is $1$ if and only if the initial state is a final state, and the other terms are the transitions.

One remarkable thing about this is that the familiar regular expression operators (plus some less familiar ones, such as set intersection and set difference) are *completely* determined by their derivatives, plus their evaluation at zero. This is what we'd expect from the fundamental theorem of calculus, but it's interesting to see it here too.

Incidentally, this theory scales up to context-free and recursive languages too, but you need a bit more machinery for that which I won't go into here.

# Answer
> 4 votes
# A fundamental question about mathematics

*This answer was reorganized after the OP gave more precisions as to the meaning and intent of his question. I also comment other answers here, as it is awkward to do so in the usual comment format. Commenting them also gives extra insight into the relevant issues.*

## In a nutshell

Your intuition is quite correct that the empty string plays a special role in the study of strings and formal languages, and that is the reason why it is often given a special name or notation. Strings over a given set of symbols form an algebraic structure called a monoid, with the concatenation operation which has a neutral element: the empty string. See the answer by J.-E. Pin.

You are also correct that there could be many other notations or representation for it. The choice of representation is dictated by convenience, perspicuity and simplification of discourse, reasoning and computation.

One such convenience, as you rightfully wonder, is having a uniform notation for all strings, including the empty string. This can be achieved in several ways, whether on paper or in the computer. Terminating strings with a special symbol supposed not to belong to the set of symbols included in the strings is one way of doing it. I guess this is what you suggest with EOL. This was done some 45 years ago by Denis Ritchie for the programming language C, except that he used the byte 0, also noted NUL or ^@, rather than EOL.

In text it can be done with surrounding quotes, or with a final turnstyle $\dashv$. Note however that while the $\dashv$ alone will denote the empty string, it terminates then all strings, which is not the case for the use of the letter ε. They do not play exactly the same syntactic role.

In principle, such a termination symbol as EOL, ^@ or $\dashv$ cannot be also a symbol belonging to a string, unless you add more complex representation mechanisms.

In the computer, the null reference string could be used to represent the empty string. Otherwise it is only a programming concept that has nothing to do with the abstract concept of string.

However your question was a bit confusing and not too well stated. Talking of a "*separate concept*" hints at semantic issues rather than syntactic reresentation. And you were mixing textual, printed representations, which use εbut not EOL, with computer representation which do the opposite.

## With many more details

This is a strange question. In its way, it also raises one or two fundamental issues about mathematics.

Understanding such issues is non obvious, as witnessed by the inadequacies of some answers given by obviously competent users, and the inadequacies of the question itself. This is what attracted me to this question.

These two issues are concerned with :

* proper understanding of the respective **roles and uses of syntax and semantics** in mathematics and programming;
* proper understanding of the effect of **"removing a concept from an existing theory"**.

The second issue, which has to do with semantics, has probably been addressed by logicians, and possibly by historians of science. But I do not recall seeing it formally addressed (or possibly I did not recognized it).

A confusion between syntax and semantics probably arose from the fact that the OP talks of a "*separate concept*" where he should rather talk of a "*separate notation*". Such a mistake is probably fair in his case as he is trying to understand issues. But it further confused some users who answered, clearly Yuval Filmus and myself, as we took the word "concept" for what it is supposed to mean.

## About Semantics

*I realize now that the next paragraph is not about the question you intended; but it is the question you wrote, and which is to be understood as semantics, and was by several people, while you meant syntax (to be addressed in the syntax part below).*

Let's start with your question "**Why do you need a separate concept, that of 'empty string'?**", which I understood as: *"could we use strings, in theory and in programming, without ever considering the empty string?"*, as apparently did Yuval Filmus.

**The fact is, we often do not need the empty string**, but it is generally more convenient to have it. Most of the theory could probably be developed without ever considering empty strings. After all, a lot of arithmetics was developed by the Greeks without considering zero as a number. Zero was introduced syntactically and semantically only a few centuries later in India. Extending the number system is not just introducing new concepts, but also a way of simplifying the understanding and use of old concepts. Introducing zero and the negative numbers made it easier to understand the properties of the natural positive numbers, and so on. Some properties of functions on the reals (such as convergence of series) are much easier to analyze and understand when you consider the extension to complex numbers.

So introducing new concepts and extensions in mathematics is often a good way of making theories simpler (and usually more powerful for expressing problems).

Introducing the empty string along with "natural strings" will simplify theories built on strings, and that is good enough a reason. Typically, as stated in other answers, having the empty string enables us to consider strings as representatives (models) of well known algebraic structures (monoids), and apply directly all known results about such structures. Indeed, as noted by J.-E. Pin, the empty string is directly related to the concatenation operation on strings (and I would add, in the same way that zero is related to the addition of integers).

We do not or may not need the empty string, but it is a lot more convenient to do mathematics with it than without it. And this is also true of programming (which is a form of mathematics aiming at producing constructive proofs).

**A matter of consistency**

However *I disagree with the answer of Yuval Filmus* regarding the effect of not allowing for the concept of an empty string, in the same way that the Greeks would not consider a number zero. Introducing zero as a new number would not have been acceptable if it had changed the known results of arithmetics. At best it would have been considered a different theory, with its own purpose.

Similarly, a theory of strings should give consistent results whether it allows for the empty string or not. But both approaches should use consistent definitions for that to be apparent and meaningful, and Yuval Filmus did not do that.

**When the empty string is allowed**, the *usual definition of prefix* is:

> A string u is a **prefix** of a string v iff there is a string w such that u.w=v

where the dot denotes the string concatenation. This allows for a string being a prefix of itself by taking w=ε (the empty string). Then you can define:

> A string u is a **proper prefix** of a string v iff it is a prefix of v and not equal to v.

However, **when the empty string is not allowed**, you have to state these definitions consistently, but differently. For example:

> A string u is a **proper prefix** of a string v iff there is a string w such that u.w=v

Note that w must have at least one symbol. Then you can define:

> A string u is a **prefix** of a string v iff u is a proper prefix of v or u=v.

With such consistent definitions, a word remains a prefix of itself, even when the empty string is not allowed in the theory.

So the point to be made is not that not allowing the empty string changes the properties of strings (at least not in such a trivial way) as asserted by Yuval Filmus. The point is much more that it makes the study of strings more complicated, in the same way that arithmetics is more complicated when you cannot talk of zero.

## About Syntax

The second issue is syntactic. How should strings be represented, on paper or in the computer. In particular, assuming we agree that it is useful to have the concept of an empty string, how should it be represented syntactically so that we can talk or write about it.

The question actually arises for all mathematical concepts: how should they be represented so that we can talk or write about them, and do so as conveniently as possible. Much of the evolution of mathematics is also related to improvement of syntax, of the representation of concepts. A trivial example is the awkwardness of doing arithmetics with the ancient Roman representation of integers.

A first answer regarding the empty string is that you may want that to be consistent with the representation of other strings. Typically, the representation of a string will include the sequence of symbols in the strings plus some additional notation, such as quotes : "*gattaca*" for example. It then becomes quite natural to represent the empty string as "".

If you rather represent the above example as *gattaca*$\dashv$, then the natural representation for the empty string is $\dashv$ (as noted implicitly by David Richerby).

So the question about the need to introduce a *separate notation* (rather than a *separate concept*, as actually written) has a negative answer. No, it is not needed. Uniform notation, uniform representation, is possible for all strings, including the empty string.

However, if you simply represent the string by the sequence of included symbols, such as *gattaca*, with no other characters, then the empty string would become invisible syntactically, which is rather inconvenient. Then it is necessary to introduce some specific notation, such as the Greek letter ε or some other name.

Similarly, when studying strings abstractedly, it is a bit awkward to use "" to represent the empty string, if only because it does not make for nice and clear sentences in oral speech, when scientists talk to each other, which is supposed to happen on occasion. Hence it is nicer to give it a name. Saying *empty string* might do, but is awkward in writing. Hence the habit of using a single letter symbol as is often done in mathematics to denote entities of specific relevance,

The suggestion to represent the empty word by EOL is essentially the same as representing it by $\dashv$. It is simply a representation of strings with a special terminating character. EOL is just a special character "somehow available in computers".

As noted above for Roman integer arithmetics, the choice of a representation should be dictated by convenience, expecially in an algorithmic environment. There are many way to represent strings in general, and the empty string in particular, in the computer. From a theoretical standpoint, it does not matter much which you choose. From a practical standpoint, it is essential to choose one that will make string operations and manipulation more efficient. This is a basic issue in any class on algorithms and data structures.

## On the confusion of syntax and semantics

The answer by David Richerby is interesting for its confusion of syntax and semantics.

He tries to introduce the syntactic use of EOL suggested in the question, which he replaces by the symbol $\dashv$, but he strangely mixes it with the definition of the semantic domain of strings, making what is supposed to be only a notation part of that semantic domain.

His second definition should actually have been the following:

> An *alphabet* is a finite set $\Sigma$ of symbols. A *string* $s$ over the alphabet $\Sigma$ is a finite sequence of $\ell$ symbols $s\_i$, where $0\le\ell$, $1\le i\le \ell$ and $s\_i\in\Sigma$ for all values of $i$. It is noted $s\_1\dots s\_\ell\dashv$ where $\dashv$ is a special character not denoting a symbol in $\Sigma$. We write $|s|$ for the *length* of $s$, defined by $|s\_1\dots s\_\ell\dashv|=\ell$. A *substring* of $s\_1\dots s\_\ell\dashv$ is any string $s\_i\dots s\_j\dashv$, where $1\leq i\leq j\leq \ell$. The *concatenation* of strings $s\_1\dots s\_\ell\dashv$ and $t\_1\dots t\_m\dashv$ is the string $s\_1\dots s\_\ell t\_1\dots t\_m\dashv$ of length $\ell+m$.
> Note that as a consequence, the unique string of length zero is denoted $\dashv$.

This definition is just a notational variant of the conventional definition given by David Richerby. It does not introduce any complexity or "*extra fiddliness*" and changes nothing to automata theory, for the simple reason that $\dashv$ is part of the notation, not a symbol in the strings. And it does give a uniform notation for all strings, including the empty one.

Yuval Filmus makes a similar error in his second remark, since EOL is intended as a syntactic notational device for representing strings, not as a symbol in strings, while $\\{0,1\\}$ concerns the list of symbols that can constitute strings, semantically.

## To summarize answers

J.-E. Pin's answer is quite correct, but it addresses only one part of the question, regarding the importance of the empty string. It does not address the possibility of a uniform notation.

The answers of Yuval Filmus and David Richerby confusing syntax and semantics, thus erroneously rejecting the suggestion of the OPś question to use EOL. Also Yuval Filmus'argument to assert the semantic importance of the empty string is very disputable. Though it deos make some sense, David Richerby's remark on the use of the null reference is also somewhat unwarranted: it could well be used to represent the empty string, provided the code is written accordingly.

The answer by Pseudonym is theoretical overkill regarding the importance of the empty string in formal language, but does not actually discuss the issues raised by the question.

As for my own answer, I can only hope it addresses adequately the issues and contains no error, but it is far far too long.

---
Tags: formal-languages, terminology
---


# Question
Title: Reduction between $\Sigma^*$ and $\emptyset$
Throughout the subject of reductions, I was wondering:

> If we take $L\_1 = \Sigma^\* $ and $L\_2 = \emptyset$, is $L\_1 \leq L\_2$? is $L\_2 \leq L\_1$?

What I mean is, Is there some sort of reduction between any of the two with the other one?

I tried this:

> Let us try $L\_2 \leq L\_1$, we need to show that such a reduction exists. Suppose f(x) is that reduction function in which $x \in L\_2$ iff $f(x) \in L\_1$.

But there aren't any $x$ in $\emptyset = L\_2$, does that show that such a reduction doesn't exist?

# Answer
> 3 votes
Let $f : \Sigma^\* \to \Sigma^\*$ any total function. Then, the statement $x \in L\_2$ is always false since $L\_2 = \emptyset$, and conversely $f(x) \in L\_1$ is always true since $L\_1 = \Sigma^\*$. So, clearly, the equivalence

$\qquad\displaystyle x \in L\_2 \iff f(x) \in L\_1$

is false for $f$ and *all* $x \in \Sigma^\*$ (it would have been sufficient to find one example-$x$); in fact,

$\qquad\displaystyle x \in L\_2 \iff f(x) \notin L\_1$

holds for all $x$. So $f$ is not a reduction function.

Since we picked $f$ arbitrarily, there can be no reduction from $L\_2$ to $L\_1$. A similar argument works for the other direction.

---
Tags: reductions
---