# Question
Title: How to come up with the runtime of algorithms?
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.

I've seen in many sites and books, the big-O notations like $O(n)$ which tell the time taken by an algorithm. I've read a few articles about it, but I'm still not able to understand how do you calculate it for a given algorithm.

# Answer
> 35 votes
This part of computer science is called analysis of algorithms. Many times people are satisfied when they are given a guarantee that an algorithm’s performance is not worse than a specified bound and they dont’t care about the exact performance.

This bound is conveniently denoted with the Landau-notation (or big-Oh notation) and in case of $\mathcal{O}(f(n))$ it is an upper bound. That is for inputs of size $n$ the algorithms complexity is guaranteed not to exceed (a constant times) $f(n)$. Most of the time it is clear from the context what the “unit” this bound is measured in is. Note that “runtime” measured in actual time units (seconds, minutes, etc.) is frowned upon as you can’t compare them meaningful across different computers. Typically a “costly” elementary operation is identified, like compares and exchanges in sorting algorithms, or pushs and pops if the algorithm includes a stack, or updates to a tree data structure used in the algorithm. This elementary operation is understood as to be the dominating one, that has the largest contribution to the algorithm’s complexity, or perhaps it is more expensive than another one in a particular setting (multiplications are considered to be more expensive then additions for example). It has to be selected so that the cost of other operations are (at most) proportional to the number of the elementary operations.

This upper bound is called the worst-case bound or the worst-case complexity of the algorithm. Because it has to hold for **all** inputs of the same size $n$ and the worst-case inputs incur the highest (worst) cost. The actual performance for a specific input of size $n$ may be a lot lower than this upper bound.

While it is possible to do an exact analysis it is usually much more involved to arrive at an exact result. Also, an exact analysis means accounting for all operations in the algorithm, and that requires a rather detailed implementation; while counting elementary operations can be done from a mere sketch of the algorithm most of the time. It is nice if such an analysis is possible but it is not always necessary. Because small inputs are not much of a problem, you want to learn what happens when the input size $n$ gets large. Knowing that the algorithm’s complexity is bounded by $5n^2+3n-2\log(n)$ is nice but *overkill* when looking at the performance asymptotically ($n\rightarrow \infty$), because the term $n^2$ dominates the others for large $n$. So proving an upper bound of $\mathcal{O}(n^2)$ suffices.

If you have two algorithms and you can guarantee that one performs like $\Theta(n^2)$ and the other like $\Theta(n)$ you can easily decide which one is “faster”, has a lower “cost”, uses less elementary operations, just by noting that a quadratic function grows faster than a linear function. In practice that means that the linear algorithm finishes earlier or that it can process larger inputs in the same time. But it might be that the constants hidden by $\Theta$ are such that for practical $n$ the $\Theta(n^2)$ algorithm is faster.

However if you have three algorithms all with a $\mathcal{O}(n^3)$ guarantee on their complexity you are hard pressed when you have to decide which algorithm to choose. Then more detailed bounds are needed, or perhaps even an exact analysis.

It may very well be that this analysis is hard to do and you can’t give a **tight** bound. Then there is a gap between the actual worst-case performance, perhaps $n^2$ and your bound of perhaps $\mathcal{O}(n^3)$. Then a clever idea, a more involved analysis is necessary to close the gap and provide an improved bound. This is just an improvement of the bound not to the algorithm. Typically you have to argue more carefully when you want to prove a tighter bound.

This all said, an analysis of an algorithm can be as simple as looking at the implementation and counting the nesting depth of the for loops to conclude that the operations in the innermost loop are executed not more than $\mathcal{O}(n^3)$ times when say three loops are nested.

For some types of algorithms the analysis follows always the same pattern, so there is a theorem like the master theorem, that tells you generically what the algorithms performance will be. Then you only have to apply the theorem to get the bound.

Perhaps you are faced with a recursive algorithm and you are able to describe the algorithms complexity by a recurrence relation. Then solving the recurrence gives the desired bound.

Typically you have to exploit some properties of the inputs. Sorting algorithms are deeply connected to permutations and knowing something about the number of inversions in a permutation helps a lot when analysing the performance.

There is no general approach on how to proceed in an analysis. As discussed above it depends on the algorithm, its inputs, its implementation, the elementary operation choosen, what mathematical tools you have at hands, the desired sharpness of the bound.

Some may prefer a smoothed-analysis or an average-case analysis over a treatment of the worst-case. Then different techniques are necessary.

# Answer
> 28 votes
Big O notation ($\mathcal{O}$) ignores all constant factors so that you're left with an upper bound on growth rate.

For a single line statement like assignment, where the running time is independent of the input size $n$, the time complexity would be $\mathcal{O}(1)$:

```
int index = 5;  *//constant time*
int item = list[index]; *//constant time*

```

For a loop like:

```
for i:=1 to n do
  x:=x+1;

```

The running time would be $\mathcal{O}(n)$, because the line $x=x+1$ will be executed $n$ times.

But for:

```
for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

```

It'd be $\mathcal{O}(n^2)$ because the statement will be executed $n$ times for every $i$.

For a while statement, it depends on the condition and the statement which will be executed in it.

```
i := 1;
while ( i < n )
  i = i * 2;

```

The running time is logarithmic, $\mathcal{O}(\log n)$ because of the multiplication by 2.

For instance:

```
Double test(int n){
  int sum=0;  -> 1 time
  int i;  -> 0 time
  for(i=0; i<=n;i++)  -> n+2 times
  {
    scanf("%d",&a);  -> n+1 times
    sum=sum+a;  -> n+1 times
  }
  return sum;  -> 1 time
}

```

---

Which is $3n+6$. Hence, $\mathcal{O}(n)$.

For more information, have a look at this Wikipedia atricle: time complexity

# Answer
> 13 votes
A statement like "Algorithm $A$ takes $\cal{O}(n)$ time." does not say much about the actual runtime of the algorithm on a given instance. You (usually) have to read it like this:

"For a fixed $n\_0 \in \mathbb{N}$ and for all $n \geq n\_0$ the runtime of $A$ on a worst-case instance of size $n$ is bounded from above by a function $f(n) = cn$ with $c \in \mathbb{R}$ fixed."

This is called "asymptotic runtime bounded by $\cal{O}(n)$", a much weaker statement.

* First of all, it does not tell you anything for "small" instances; it might even be the case that $n\_0$ is so large that you will only ever encounter instances you have no runtime bound for.
* $c$ can be arbitrarily large. Combined with the first item, asymptotically slower algorithms might outperform a faster one on all relevant instances.
* A bound given by $\cal{O}$ is not necessarily sharp. For instance, all polynomial algorithms have runtime in $\cal{O}(2^n)$; therefore, such a bound might not characterise the algorithm well at all.
* In most cases, only worst-case instances are considered. Often, this is not very representative for the real behaviour of the algorithm. Prominent examples include Quicksort and Simplex algorithm.

All of these items come up because sharper analysis is *hard* or even impossibly to perform without knowledge about the concrete machine an algorithm is run on. Aside from determining $c$ precisely, deriving $\Theta$-classes (both upper and lower bound), average case analysis, amortised analysis and smoothed analysis are popular techniques to better describe an algorithm's behaviour.

Note furthermore tha memory hierarchies are usually ignored even though they can heavily influence performance. See my answer here for a quick explanation of the different Landau symbols.

That said, analysing an algorithm is conceptually simple: Count all executed operations and sum up their (relative) runtimes. As this is often (too) hard, some tricks are employed; the desired quality of the resulting bounds inform which one to employ to which extent. Performing a *good* analysis (i.e. one that yields exactly the desired precision) is definitely an art.

* Consider only best- or worst-case instances (often implicitly), or take the average over all instances.
* Count only those kinds of operations that dominate runtime, i.e. that occur (asymptotically) most often. Form example, analyses of sorting algorithms often count only element comparisons, which is not always appropriate; determining which operation dominates takes experience. Note that restricting yourself like this will effectively prevent you from obtaining any amount of precision regarding runtime estimations.
* Apply general calculation rules. For instance, loops translate to sums and recursive algorithms to recurrence equations.
* Simplify your model, e.g. count all elementary operations with a unit cost and ignore pipelines, memory IO peculiarities and caches.

If you want to see exceptionally rigorous analyses, take a peek into Donald Knuth's "The Art of Computer Programming". For examples with a more common resolution try Cormen, Leiserson et al, "Introduction to Algorithms".

# Answer
> 10 votes
Let me give a graphical representation. Consider two functions $f(n)$ and $g(n)$ that looks something like below:

When you say a function $f(n)$ is bound by $\mathcal{O}(g(n))$ i.e. ($f(n)=\mathcal{O}(g(n))$) what you actually mean is there exists a constant $c \gt 0$ and $n\_0$ such that $f(n)\leq c\cdot g(n)$, $\forall n\geq n\_0$ like the figure below:

Likewise, when you say a function $f(n)$ is bound by $\Omega (g(n))$ i.e. ($f(n)=\Omega (g(n))$) what you actually mean is there exists a constant $c \gt 0$ and $n\_0$ such that $f(n) \geq c\cdot g(n)$, $\forall n\geq n\_0$ like the figure below:

In the same manner, when you say a function $f(n)$ is bound by $\Theta (g(n))$ i.e. ($f(n)=\Theta (g(n))$) what you actually mean is there exists a two constants $c\_1 \gt 0 $ and $c\_2 \gt 0$ for the SAME FUNCTION and $n\_0$ and $n\_1$ such that $c\_1\cdot g(n)\leq f(n) \leq c\_2\cdot g(n)$, $\forall n\geq n\_0,n\_1$ like the figure below:

NOTE: You can remember these notations as — $O$: when you write $O$ you always end up finishing at the top so the line is above, $\Omega$: When you write the notation, you always finish it at the bottom so the line is below the function and $\Theta$: the line is in the middle.

Now, having said this and you have a basic understanding of all asymptotic notations, look at the following figure from here. The following figure dices up the analysis of runtime of the merge sort algorithm:

# Answer
> 8 votes
$\cal{O}$, $\Theta$ and $\Omega$ all denote some sort of expression, with it's constant factors stripped off. The difference is that the O notation sets an upper bound on the algorithm's running time, the Omega notation sets a lower bound, and the Theta notation "sandwiches" the algorithm's running time.

To calculate the running time of an algorithm, you have to find out what dominates the running time. For example, if you've designed an algorithm which does binary search and quick sort once, it's running time is dominated by quick sort.

But you'll finally have to calculate the running time of an algorithm which doesn't (at least partially) consist of algorithms which you have seen before. In this case, you have to find the part that spends the most time. It usually means that you have to look at loops, nested loops and recursive calls.

There is much more to say on algorithm analysis and there are also other techniques, like amortized analysis. To find out more, I highly recommend you to read "Introduction to Algorithms", Third Edition, CLRS.

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


# Question
Title: Natural occurrences of monads that make use of the category-theoretical framework
Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, i.e. with uncountably infinite state sets and different notions of traces. To this end, he goes up through several layers of abstraction to finally end up with the notion of monads which he combines with measure theory to build the model he needs.

In the end, it took him 45 minutes to (roughly) build a framework to describe a concept he initially explained in 5 minutes. I appreciate the beauty of the approach (it *does* generalise nicely over different notions of traces) but it strikes me as an odd balance nevertheless.

I struggle to see what a monad really *is* and how so general a concept can be useful in applications (both in theory and practice). Is it really worth the effort, result-wise?

Therefore this question:

> Are there problems that are natural (in the sense of CS) on which the abstract notion of monads can be applied and helps (or is even instrumental) to derive desired results (at all or in a nicer way than without)?

# Answer
> 6 votes
Asking whether an occurrence of monad is *natural* is similar to asking whether a group (in the sense of group theory) is natural. Once you formalise something, in this case as an endofunctor, either it satisfies the axioms of being a monad or not. If it does satisfy the axioms, then one gets a lot of technical machinery for free.

Moggi's paper Notions of computation and monads pretty much seals the deal: monads are incredibly natural and useful for describing computational effects in a unified way. Wadler and others translated these notions to deal with computational effects in functional programming languages, by using the connection that a functor is a data type constructor. This adds the icing on the cake. FP monads allow a treatment of computational effects such as IO which would be extremely unnatural without them. Monads have inspired related useful notion such as arrows and idioms which are also very useful for structuring functional programs. See the Wadler link for references. FP monads are the same thing as category theory monads in the sense that for an FP monad to work the same equations need to hold --- the compiler relies on these. Generally, the presentation of the monad differs (different but equivalent operations and equations), but this is a superficial difference.

A vast amount of the work of Bart Jacobs, to take but one example, uses monads. A lot of work stems from coalgebra, which is a general theory of systems. One of Jacobs' (many) contributions to the area is the development of a generic notion of trace semantics for systems (described as coalgebras) based on monads. One could argue that the notion of trace semantics is natural: What is the semantics of a system? The list of actions that can be observed!

One way to understand monads is to first program in Haskell using monads. Then find one of the many good tutorials available (via google). Start from the programming angle, then move to the theoretical side, starting with some basic category theory.

---
Tags: applied-theory, category-theory
---


# Question
Title: Is an inﬁnite union of context-free languages always context-free?
Let $L\_1$, $L\_2$, $L\_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L\_1$, $L\_2$, $L\_3$, $\dots $; i.e., $L = L\_1 \cup L\_2 \cup L\_3 \cup \dots $.

Is it always the case that $L$ is a context-free language?

# Answer
> 21 votes
The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L\_l = \\{ l \\}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and thereby definitely not context-free).

The closure properties of context-free languages can be found on Wikipedia.

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Time spent on requirement and its effect on project success and development time
Is there any evidence suggesting that time spent on writing up, or thinking about the requirements will have any effect on the development time? Study done by Standish (1995) suggests that incomplete requirements partially (13.1%) contributed to the failure of the projects. Are there any studies done which show that time spent on requirement analysis will have any effect on development time of a project, or how successful the project will be.

# Answer
> 10 votes
See Code Complete, By Steve McConnell, Table 3-1. He compares the average cost of fixing defects based on when they're introduced and detected. Detection at construction time costs 5-10 times more than detection at requirements time, and 10-100 times more post-release.

The table is based on the following sources:

1. "Design and Code Inspections to Reduce Errors in ProgramnDevelopment" (Fagan 1976)
2. Software Defect Removal (Dunn 1984)
3. "Software Process Improvement at Hughes Aircraft" (Humphrey, Snyder, and WIllis 1991)

and several more

# Answer
> 10 votes
Yes, there are plenty of studies on this topic. Of course, the question is too general to answer for all kinds of software development projects, but there is evidence from several contexts that support the notion that properly doing requirements analysis will have a positive impact on the implementation stage. This evidence has been partially collected into "laws", and here are three examples:

**Glass' law:** *Requirement deficiencies are the prime source of project failures.*

This law is backed up by case study evidence from large software development projects. Glass found that in the failed cases, there were far too many requirements, they were unstable due to late changes, and they were ambiguous and incomplete.

This suggests that there is a relation between the quality of requirements and the project outcome.

**Boehm's first law:** *Errors are most frequent during the requirements and design activities and are the more expensive the later they are removed.*

This is also backed up by case study evidence and contributes to answering the question in the following way: doing the requirements properly will reduce the number of errors in the system, and correcting the errors before starting implementation is going to be less expensive than hunting them down when implementation has already started (or worse, when the system has already shipped).

**Boehm's second law:** *Prototyping (significantly) reduces requirement and design errors, especially for user interfaces.*

This is backed up by controlled experiments in a student context. One possible interpretations is that requirements and design phases do not need to be entirely documentation-driven and theoretical. Instead, performing prototyping as part of the requirement and design phases – which amounts to spending time on and thinking about the requirements – is going to affect project success and implementation time.

There is also plenty of other evidence that points in the same direction: spending time on preparing for implementation pays off in the form of less risk and less chance of schedule overrun due to surprises. Although the question was not about testing, proper preparation positively affects testing, too.

The references for these laws are:

Glass' law: Glass, R.L.: Software Runaways. Lessons Learned from Massive Software Project Failures. Upper Saddle River, NJ: Prentice Hall 1998

Boehm's first law: Boehm, B.W., McClean, R.K., Urfrig, D.B.: Some Experience with Automated Aids to the Design of Large-Scale Reliable Software. IEEE Trans on Software Engineering 1, 1 (1975), 125–133

Boehm's second law: Boehm, B.W., Gray, T.E., Seewaldt, T.: Prototyping Versus Specifying: A Multiproject Experiment. IEEE Trans on Software Engineering 10, 3 (1984), 290–302

Also, the following reference may be of interest: Endres, A. and Rombach, D. A Handbook of Software and Systems Engineering. Empirical Observations, Laws and Theories. The Fraunhofer IESE Series on Software Engineering. Addison Wesley, 2003.

---
Tags: software-engineering
---


# Question
Title: Implementing the GSAT algorithm - How to select which literal to flip?
The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or you reach the max\_tries/max\_flips limit and find no solution.

I'm implementing the following algorithm:

```
procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

```

I'm having trouble interpreting the following line:

```
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;

```

Isn't the maximum number of satisfied clauses what we're looking for? It seems to me that we're trying to use the solution or approximations to it to find the solution.

I've thought of some ways to do this but It'd be good to hear other points of view (The assumption is that once the variable is flipped once it is selected.):

* Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.
* Randomly select the variable that I will flip starting with the literals that are more common.
* Pick a random literal.

# Answer
> 12 votes
> Isn't the maximum number of satisfied clauses what we're looking for?

Yes, we're looking for an assignment that satisfies the maximum number of clauses (that is all of them, preferably). And to that end we ask ourselves "Which single variable will bring us closest to this goal when flipping it?" and then flip it.

> It seems to me that we're trying to use the solution or approximations to it to find the solution.

Using the solution would be if we asked "Which combination of multiple flips would give the best result?" or simply "Which assignment would be the best?". However that's not what we're doing, we're only looking one step ahead. Using an approximation of the solution seems like an accurate description. However there's nothing wrong with that. That's how greedy strategies work.

> Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.

Right.

---
Tags: algorithms, satisfiability, 3-sat
---


# Question
Title: Stability for couples in the Stable Matching Problem
In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's proposals.

From what I read, an unstable match occurs when $m$ and $f$ prefer each other to their current partners.

I am a little lost in the definition of Stable Matching for this case. I'm going over the slides here.

> Is a pair $(m, f)$ stable as long as the men are content even though the female's preferences have not been matched?

# Answer
Yes, it is stable. It doesn't need to assign the optimal choices for both sides. To break a marriage you need two willing parties, unhappiness of one side in a marriage doesn't make it unstable here.
> 8 votes

---
Tags: combinatorics
---


title: How to define quantum Turing machines?

text:
# Question
Title: How to define quantum Turing machines?
In quantum computation, what is the equivalent model of a Turing machine? It is quite clear to me how quantum **circuits** can be constructed out of quantum gates, but how can we define a quantum Turing machine (QTM) that can actually benefit from quantum effects, namely, perform on high-dimensional systems?

# Answer
(**note**: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model)

When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model the advantage of quantum mechanics.

Similarly to the classical model, QTM has:

1. $Q=\\{q\_0,q\_1,..\\}$ - a finite set of states. Let $q\_0$ be an initial state.
2. $\Sigma=\\{\sigma\_0,\sigma\_1,...\\}$, $\Gamma=\\{\gamma\_0,..\\}$ - set of input/working alphabet
3. an infinite tape and a single "head".

However, when defining the transition function, one should recall that any quantum computation must be *reversible*. Recall that a *configuration* of TM is the tuple $C=(q,T,i)$ denoting that the TM is at state $q\in Q$, the tape contains $T\in \Gamma^\*$ and the head points to the $i$th cell of the tape.

Since, at any given time, the tape consist only a finite amount of non-blank cells, we define the (quantum) state of the QTM as a unit vector in the Hilbert space $\mathcal{H}$ generated by the configuration space $Q\times\Sigma^\*\times \mathrm{Z}$. The specific configuration $C=(q,T,i)$ is represented as the state $$|C\rangle = |q\rangle |T\rangle |i\rangle.$$ (remark: Therefore, every cell in the tape isa $\Gamma$-dimensional Hilbert space.)

The QTM is initialized to the state $|\psi(0)\rangle = |q\_0\rangle |T\_0\rangle |1\rangle$, where $T\_0\in \Gamma^\*$ is concatenation of the input $x\in\Sigma^\*$ with many "blanks" as needed (there is a subtlety here to determine the maximal length, but I ignore it).

At each time step, the state of the QTM evolves according to some unitary $U$ $$|\psi(i+1)\rangle = U|\psi(i)\rangle$$

Note that the state at any time $n$ is given by $|\psi(n)\rangle = U^n|\psi(0)\rangle$. $U$ can be any unitary that "changes" the tape only where the head is located and moves the head one step to the right or left. That is, $\langle q',T',i'|U|q,T,i\rangle$ is zero unless $i'= i \pm 1$ and $T'$ differs from $T$ only at position $i$.

At the end of the computation (when the QTM reaches a state $q\_f$) the tape is being measured (using, say, the computational basis).

The interesting thing to notice, is that each "step" the QTM's state is a superposition of possible configurations, which gives the QTM the "quantum" advantage.

---

The answer is based on Masanao Ozawa, On the Halting Problem for Quantum Turing Machines. See also David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer.
> 32 votes

# Answer
As the notes indicate, the way to define a QTM is to define the transition function as a unitary transform of state and letter. So in each step, you imagine multiplying the (state,letter) vector by a transformation to get a new (state, letter). It's not particularly convenient, but it can be defined.
> 7 votes

---
Tags: quantum-computing, turing-machines, computation-models
---


# Question
Title: Problems Implementing Closures in Non-functional Settings
In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):

> In computer science, a closure (...) is a **function together with a referencing environment** for the non-local variables of that function. A closure allows a function to access variables outside its immediate lexical scope.

So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

In practice, the concept seems to be diverging, though, at least outside of functional programming. Different languages implement different semantics, there even seem to be wars of opinons on. Many programmers do not seem to know what closures are, viewing them as little more than anonymous functions.

Also, there seem to exist major hurdles when implementing closures. Most notable, Java 7 was supposed to include them but the feature was pushed back to a future release.

Why are closures so hard (to understand and) to realise? This is too broad and vague a question, so let me focus it more with these interconnected questions:

* Are there problems with expressing closures in common semantic formalisms (small-step, big-step, ...)?
* Are existing type systems not suited for closures and can not be extended easily?
* Is it problematic to bring closures in line with a traditional, stack-based procedure translation?

Note that the question relates mostly to procedural, object-oriented and scripting languages in general. As far as I know, functional languages do not have any problems.

# Answer
> 10 votes
May I direct you to the Funarg problem wikipedia page? At least this is how the compiler people used to reference the closure implementing problem.

> So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

While this definition makes sense, it does not help describe the problem of implementing first-class functions in a traditional runtime-stack based language. When it comes to implementation issues, first class functions can be roughly divided into two classes:

* Local variables in the functions are never used after the function returns.
* Local variables can be used after the function returns.

The first case (downwards funargs) is not that hard to implement and can be found on even the older procedural languages, like Algol, C and Pascal. C kind of skirts the issue, since it does not allow nested functions but Algol and Pascal do the necessary bookkeeping to allow inner functions to reference the stack variables of the outer function.

The second case (upwards funargs), on the other hand, requires activation records to be saved outside the stack, in the heap. This means that it is very easy to leak memory resources unless the language runtime includes a garbage collector. While almost everything is garbage collected today, requiring one is still a significant design decision and was even more so some time ago.

---

As for the particular example of Java, if I remember correctly, the main issue was not actually being able to implement closures, but how to introduce them to the language in a way that was not redundant with existing features (like anonymous inner classes) and that did not clash with existing features (like checked exceptions - a problem that is not trivia l to solve and that most people don't think of at first).

I can also think of other things that make first class functions less trivial to implement, such as deciding what to do with "magical" variables such as *this*, *self* or *super* and how to interact with existing control flow operators, such as *break* and *return* (do we want to allow for non-local returns or not?). But in the end, the recent popularity of first-class functions seems to indicate that languages that don't have them mostly do so for historical reasons or due to some significant design decision early on.

# Answer
> 5 votes
We can look at how closures are implemented in C#. The scale of the transformations the C# compiler performs makes it clear that their way of implementing closures is quite a lot of work. There may be easier ways to implement closures, but I'd think the C# compiler team would be aware of this.

Consider the following pseudo-C# (I cut out a bit of C# specific stuff):

```
int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

```

The compiler transforms this into something like this:

```
class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

```

(in reality, the variable f will still be created, where f is a 'delegate' (= function pointer), but this delegate is still associated with the theClosureObject object - I left this part out for clarity for those that aren't familiar with C#)

This transformation is quite massive and tricky: consider closures inside closures and the interplay of closures with the rest of the C# language features. I can imagine that the feature was pushed back for Java, as Java 7 already has quite a lot of new features.

# Answer
> 5 votes
To answer part of your question. The formalism described by Morrisett and Harper covers big- and small-step semantics of higher-order polymorphic languages containing closures. There are papers before these providing the kinds of semantics you are looking for. Look, for example, at the SECD machine. Adding mutable references or mutable locals into these semantics is straightforward. I don't see that there are any technical problems in providing such semantics.

---
Tags: programming-languages, semantics
---


# Question
Title: Why store self and parent links (. and ..) in a directory entry?
Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to in systems such as unix and Windows (for example, its access permissions are completely different and not tied to metadata stored in directories). This filesystem does not allow any kind of hard link or soft link, so every file has a unique name in a strict tree structure.

Is there any benefit to storing a link to the directory itself and to its parent in the on-disk data structure that represents a directory?

Most unix filesystems have `.` and `..` entries on disk. I wonder why they don't handle those at the VFS (generic filesystem driver) layer. Is this a historical artifact? Is there a good reason, and if so, which precisely, so I can determine whether it's relevant to my embedded system?

# Answer
You get fewer special cases. In many situations, VFS may handle ".." as it handles any other directory name.
> 2 votes

# Answer
Having links to the parent directory makes good sense to me. If you didn't have them, you would always need to work with a whole list of directories. So, for example, `/home/svick/Documents/` would have to be represented as `{ /, /home/, /home/svick/, /home/svick/Documents }`. If you didn't do that, you wouldn't be able to find the parent directory at all (or it would be very expensive). This is not only inefficient, but also dangerous. If you have two such lists that overlap, they could easily desynchronize if you moved some directory.

On the other hand, if you have a reference to the parent directory, it's more efficient and safer.

I don't see any reason to actually have a link to the current directory. If you have a structure that represents some directory and you want to access that directory, using `.` is always completely unnecessary. Because of that, I would expect that the `.` link doesn't actually exist in the filesystem structure and is only virtual.
> 2 votes

# Answer
The only reason I can imagine is the following scenario:

1. An original implementation of a file system existed with the same directory format but the notions of file paths and subdirectories was not considered at that time (See The PDP-7 Unix file system).
2. Then people thought that path resolution and subdirectories would be useful!
3. To keep some amount of backward compatibility with older implementations, it was decided that the `.` and `..` will be stored on the disk just like any other directory.

So maybe we're left with those useless artefacts, just for the sake of backward-compatibility with 40 years old software? Credible scenario?

---

Note: Also it was not completely stupid to add these entries to the directory listing, as you need to store the inode number of your true parent directory somewhere anyway (remember that hardlinks on directories was allowed at this time), and a reference to your own inode number might be a good sanity check.
> 2 votes

# Answer
I don't see a reason to implement `.` and `..` on either level rather than the other. However, if you target embedded systems any layer you can *save* may be dollars earned, so it might make sense to try and implement everything as low as possible.

As for the general need of `.` and `..`, how would you express relative paths without them? At least `..` is indispensable for paths that leave the current subtree. If you do not need such paths (maybe the tree is a primitive way to encode access privileges?) you do not need `..`.
> 1 votes

---
Tags: operating-systems, filesystems
---


# Question
Title: Influence of the dimension of cellular automata on complexity classes
Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?

Here is a bunch of more specific questions:

1. What kind of algorithms will have their time complexity changed, by how much?
2. What would be the basic idea for the encoding; how is a 3d grid efficiently (or not efficiently…) mapped to a 2d grid? (The challenge seems to achieve communication between two cells that where originally neighbors on the 3d grid, but are not neighbors anymore on the 2d grid).
3. In particular, I'm interested in the complexity drift for exponential complexity algorithms (which I guess remains exponential whatever the dimension, is it the case?)

Note: I'm not interested in low complexity classes for which the chosen I/O method has an influence on complexities. (Maybe the best is to assume that the I/O method is dimensionless: done locally on one specific cell during a variable amount of time steps.)

---

*Some context: I'm interested in parallel local graph rewriting, but those graphs are closer to 3d (or maybe ωd…) grids than to 2d grids, I'd like to know what to expect of a hardware implementation on a 2-dimentional silicon chip.*

# Answer
> 5 votes
I will explain pieces of this article: Simulating 3D Cellular Automata with 2D Cellular Automata.

Let's start by the encoding of the grid, a function $t:\mathbb Z^3 → \mathbb Z^2$. Intuitively $t$ can't preserves the distance because the number of cells at a distance less than $R$ from the origin won't be the same. You will need to embed these about $R^3$ cells into some the same number of cells but which will be somehow of the form $r^2$ but then you must have $r\>R$. These $r$ and $R$ are a bit like the radius of the notion of neighborhood you find in any cellular automaton.

So the transformation of the article will make things essentially bigger by a power of at least $3/2$. That if points are distant of $d$ in the first grid, they will be distant of at least $O(\sqrt d^3)$ in the second grid. Unfortunately the given embedding is only in $O(d^3)$.

However, and this is a very important remark, you don't obtain the same neighborhood than in the first automaton and that's why I previously said "a bit like". To quote the article:

> it is obvious that there will be cells that are very close in $\mathbb Z^3$ and such that \[their encoding will be\] arbitrarily far in $\mathbb Z^2$

That works for time, too: the execution time of one step in $\mathbb Z^3$ can be arbitrary long in $\mathbb Z^2$. Note that the encoding is more of a simulation: the 2D CA the author even simulates the computation of the function $t:\mathbb Z^3 → \mathbb Z^2$.

It is a safe bet to say that the complexity (in time) of any algorithm ran on a 3D CA will explode when ran on the encoding of this 3D CA into a 2D CA. The author says it cannot be bound by any function in his simulation. And I say the explosion is at least exponential in general, because of the propagation time of the information depends on the position.

The idea of running algorithms on cellular automata seems already a bit weird to me, but that's personal. However that's nothing compared to the idea of an implementation of a cellular automaton into a silicon chip, or is it just me?

---
Tags: complexity-theory, time-complexity, cellular-automata
---


title: Type-checking algorithms

text:
# Question
Title: Type-checking algorithms
I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques?

I am particularly interested in complex type-checking algorithms that were implemented in widely known strongly static typed languages such as, for example, C++, Java 5+, Scala or others. I.E, type-checking algorithms that are not very simple due to the very simple typing of the underlying language (like Java 1.4 and below).

I am not per se interested in a specific language X, Y or Z. I am interested in type-checking algorithms regardless of the language that they target. If you provide a answer like "language L that you never heard about which is strongly typed and the typing is complex has a type-checking algorithm that does A, B and C by checking X and Y using the algorithm Z", or "the strategy X and Y used for Scala and a variant Z of A used for C# are cool because of the R, S and T features that works in that way", then the answers are nice.

# Answer
Most research does not actually publish the type checking algorithms for full blown programming languages. You will find some formalisations of a large part of the type systems for full programming languages, such as the work done by Drossopoulou and Eisenbach for Java or Nipkov et al's work on C++. More often, though, you will only find the type systems for some core part of the language (Featherweight Java is one example) or for the core concepts of a language such as the local type inference approach of scala.

In conferences such as POPL and ICFP you will find many type checking algorithms for specific kinds of type systems, and novel approaches such as bidirectional and tridirectional type checking.

More generally, you probably need to know about the Damas-Milner algorithm, local type inference, bidirectional and tridirectional type checking, and expand from there, by following references in the papers and by using google scholar to find which papers cite these and build on the approaches described. Also, as suggested above, conferences such as POPL, ICPF, ESOP and even ECOOP and OOPSLA will have papers relevant to your quest.
> 14 votes

# Answer
A basic tool are Attribute Grammars. You will maybe not be able to do every wicked thing you can imagine with them, but they are a good starting point.

Essentially, you can walk over a program's abstract syntax tree top-down and/or bottom-up and pass information around. So, for instance, you could pass global scope type information (e.g. classes and their members) downwards and determine the type of expressions recursively, i.e. bottom-up, passing the resulting types upwards.

Find some explanation and examples in the slides here (Chapter 5).
> 2 votes

---
Tags: algorithms, programming-languages, reference-request, type-checking
---


# Question
Title: How is a JIT compiler different from an ordinary compiler?
There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or Python called JIT compilers, while C/C++ compilers are just called compilers?

# Answer
> 17 votes
JIT compilers compiles the code on the fly, right before their execution or even when they are already executing. This way, the VM where the code is running can check for patterns in the code execution to allow optimizations that would be possible only with run-time information. Further, if the VM decide that the compiled version is not good enough for whatever reason (e.g, too many cache misses, or code frequently throwing a particular exception), it may decide to recompile it in a different way, leading to a much smarter compilation.

On the other side, C and C++ compilers are traditionally not JIT. They compile in a single-shot only once on developer's machine and then an executable is produced.

# Answer
> 12 votes
JIT is short for just-in-time compiler, and name is misson: during runtime, it determines worthwhile code optimisations and applies them. It does not replace usual compilers but are part of interpreters. Note that languages like Java that use intermediate code have *both*: a normal compiler for source to intermediate code translation, and a JIT included in the interpreter for performance boosts.

Code optimisations can certainly be performed by "classical" compilers, but note the main difference: JIT compilers have access to **data** at runtime. This is a *huge* advantage; exploiting it properly may be hard, obviously.

Consider, for example, code like this:

```
m(a : String, b : String, k : Int) {
  val c : Int;
  switch (k) {
    case 0 : { c = 7; break; }
    ...
    case 17 : { c = complicatedMethod(k, a+b); break; }
  }

  return a.length + b.length - c + 2*k;
}

```

A normal compiler can not do too much about this. A JIT compiler, however, may detect that `m` is only ever called with `k==0` for some reason (stuff like that can happen as code changes over time); it can then create a smaller version of the code (and compile it to native code, although I consider this a minor point, conceptually):

```
m(a : String, b : String) {
  return a.length + b.length - 7;
}

```

At this point, it will probably even inline the method call as it is trivial now.

Apparently, the Sun dismissed most optimisations `javac` used to do in Java 6; I have been told that those optimisations made it hard for JIT to do much, and naively compiled code ran faster in the end. Go figure.

---
Tags: compilers
---


# Question
Title: Is it possible to solve the halting problem if you have a constrained or a predictable input?
The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?

For example, it seems likely that a language that does not allow loops for instance, would be very easy to tell if the program would halt or not.

The problem I'm trying to solve right now is that I'm trying to make a script checker that checks for the validity of the program. Can halting problem be solved if I know exactly what to expect from script writers, meaning very predictable inputs. If this cannot be solved exactly, what are some good approximation techniques to solve this?

# Answer
> 10 votes
The intuitive answer is that if you don't have unbounded loops and you don't have recursion and you don't have goto, your programs terminate. This isn't quite true, there are other ways to sneak non-termination in, but it's good enough for most practical cases. Of course the converse is wrong, there are languages with these constructs that do not allow non-terminating programs, but they use other kinds of restrictions such as sophisticated type systems.

### Recursion

A common restriction in scripting languages is to dynamically prevent recursion: if A calls B calls C calls … calls A, then the interpreter (or checker, in your case) gives up or signals an error, even if the recursion might actually terminate. Two concrete examples:

* The C preprocessor leaves a macro intact while it is expanding that macro. The most common use is to define a wrapper around a function:

```
#define f(x) (printf("calling f(%d)\n", (x)), f(x))
f(3);

```

This expands to

```
(printf("calling f(%d)\n", (3)), f(3))

```

Mutual recursion is handled as well. A consequence is that the C preprocessor always terminates, although it's possible to build macros with high run-time complexity.

```
#define f0(x) x(x)x(x)
#define f1(x) f0(f0(x))
#define f2(x) f1(f1(x))
#define f3(x) f2(f2(x))
f3(x)

```
* Unix shells expand aliases recursively, but only until they encounter an alias that's already being expanded. Again, the primary purpose is to define an alias for a similarly-named command.

```
alias ls='ls --color'
alias ll='ls -l'

```

An obvious generalization is to allow a recursion depth of up to $n$, with $n$ perhaps being configurable.

There are more general techniques to prove that recursive calls terminate, such as finding some positive integer that always decreases from one recursive call to the next, but these are considerably harder to detect. They are often hard to verify, let alone infer.

### Loops

Loops do terminate if you can bound the number of iterations. The most common criterion is that if you have a `for` loop (without tricks, i.e. one that really counts from $m$ to $n$), it performs a finite number of iterations. So if the body of the loop terminates, the loop itself terminates.

In particular, with for loops (plus reasonable language constructs such as conditionals), you can write all **primitive recursive functions**, and vice versa. You can recognize primitive recursive functions syntactically (if they are written in an unobfuscated way), because they use no while loop or goto or recursion or other trick. Primitive recursive functions are guaranteed to terminate, and most practical tasks don't go beyond primitive recursion.

# Answer
> 5 votes
See Terminator and AProVe. They tend to rely on heuristics, and I'm not sure if they clearly describe the class of programs for which they work. Still, they are regarded as state-of-the art, so they should be good starting points for you.

# Answer
> 4 votes
Not a formally rigid answer, but here it goes:

The problem in determining if it halts or loops forever. Looping on finite collections one element at a time or between an interval of numbers is ok. EDIT: Obviously, this will only work if the iterated collection or interval are prohibited to change (e.g., by immutability) when it is being iterated (or at least, prohibited to grow).

Recursion is probably not ok, unless if you set an artifical rule to make it finite, like allowing a maximum stack depth, or forcing that a non-negative parameter decreases in each iteration.

Arbitrary gotos are generally bad. Backwards-gotos are very likely to lead to loops that might be infinite.

Whiles and do-whiles statements are a problem, because they depend on a condition that is not guaranted to change or not during the execution. A possible (but probably very unsatisfatory) way to restrict that is to give a maximum number of iterations possible.

# Answer
> 4 votes
Yes, it can be possible. One common way of solving such problems is considering an extra (monotone) *uncomputable* parameter depending of the code as a part of input. The complexity of the problem having that parameter can be severely reduced.

We cannot compute the parameter, but if you know that the input instances you are dealing with have small parameter values, you can fix it to a small number and use the algorithm.

This and similar tricks are used in formal-methods to deal with undecidability of halting and similar problems. But if what you want to decide is complicated, the complexity of your algorithms is unlikely to be better than running the algorithm on those instances.

Regarding the other question, if you restrict the inputs enough, then the halting problem can be come easy. For example, if you know that the inputs are polynomial time algorithms, deciding the halting problem for them is trivial (since every polynomial time algorithm halts).

Problems that arise in formal-methods are typically undecidable, you may want to check the literature on how they deal with these problems in practice.

# Answer
> 2 votes
You need to provide a definition of your script language, and what do you mean by "expect" from the script writers.

If the language is allowing only linear assignments and linear conditionals, then this halting is decidable in polynomial time (more or less ${\cal O}(n^\omega)$) by Tiwari's paper in my comment.

There is a similar result for a class of polynomial program by Aaron R. Bradley, Zohar Manna and Henny B. Sipma. But AFAIK (I might be wrong here) the runtime is doubly exponential (essentially the time required to compute a Groebner basis).

---
Tags: computability, undecidability, software-engineering, formal-methods
---


# Question
Title: Why are the total functions not enumerable?
We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.

In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is *not* enumerable. That would mean that we can not devise a programming language that allows us to write all total functions but no others---which would be nice to have!

So how is it that we (apparently) have to accept the potential for non-termination if we want decent computational power?

# Answer
Because of diagonalization. If $(f\_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f\_e$ was total, then $g(i) = f\_i(i)+ 1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

Suppose we think of a universal computable function $h(e,i)$, where "universal" means $h$ is a computable binary function and that for every total computable unary function $f(n)$ there is some $e$ such that $f(i) = h(e,i)$ for all $i$. Then there must also be some $e$ such that $g(n) = h(e,n)$ is not a total function, because of the previous paragraph. Otherwise $h$ would give a computable enumeration of total computable unary functions that includes all the total computable unary functions.

Thus the requirement that every function is a system of functions is total is incompatible with the existence of a universal function in that system. For some weak systems, such as the primitive recursive functions, every function is total but there are not universal functions. Stronger systems that have universal functions, such as Turing computability, simply must have partial functions in order to allow the universal function to exist.
> 25 votes

# Answer
Just to be clear, we need to distinguish mathematical functions (I will call them *functions* and there is often uncountably many of them so they are not at all enumerable) and functions you can write: I will call them *programs* or also *computable functions*.

A subset $S$ of a countable set $E$ is called computable if there is a program that, given an element $x$ of $E$ responds "yes" if $x∈S$ and "no" if $x\not∈S$. (And he always has to respond something) A set is called recursively enumerable if the program is authorized not to respond instead of saying "no". (it's equivalent to require that the program has to print all elements of $S$ in any order)

The set of all programs that are total on a **finite set** is **enumerable** because you can write an interpreter that just run the program on all the elements of the finite set and return "yes" if they all terminates. (But can't see if any of them does not)

Your professor said that the set of all programs that are total on a **infinite set** is **not enumerable** because you can't just run your program on an infinite number of elements.

But this does not mean this is bad:

1. For example the set if all programs that are **provably** total is **enumerable** because you can enumerate all the proofs and mechanically check if they prove your program is total.
2. Even an enumerable set would not be practical, because you may have to wait forever without being sure if the procedure would terminate one day. I don't see how to use a programs that enumerate all total functions...

There are some programming languages where everything you write is guaranteed to terminate just with static typing! There are even some that guarantees you polynomial bound. They are mostly academic for now, writing in those will probably make you feel the constraints more that writing in Python, but there are a lot of researchers working on this.

So to answer your question: in a sense, yes. Potential non-termination is necessary to be Turing-complete (highest computational power for now). But I don't find this directly relevant to the fact that total functions are enumerable or not. You can still write all total programs!
> 10 votes

---
Tags: computability, semi-decidability, enumeration
---


title: Decidability of prefix language

text:
# Question
Title: Decidability of prefix language
At the midterm there was a variant of the following question:

> For a decidable $L$ define $$\text{Pref}(L) = \\{ x \mid \exists y \text{ s.t. } xy \in L\\}$$ Show that $\text{Pref}(L)$ is not necessarily decidable.

But if I choose $L=\Sigma^\*$ then I think $\text{Pref}(L)$ is also $\Sigma^\*$, thus decidable. Also $L=\emptyset$ gives the same result. And since $L$ must be decidable I cannot pick the halting problem or such..

1. How can I find $L$ such the $\text{Pref}(L)$ is not decidable?
2. Which conditions on $L$ will make $\text{Pref}(L)$ decidable, and which will make it undecidable?

# Answer
> 9 votes
Note that using an existential quantifier in front of a decidable language we can obtain any r.e. language, i.e. every r.e. language is expressible as

$$ \\{ x\in \Sigma^\* \mid \exists y \in \Sigma^\* \ \langle x,y \rangle \in V \\} $$

where $V$ is a decidable language. These include undecidable r.e. languages like $$A\_{TM} = \\{ \langle e, x\rangle\ \mid \text{$e$ encodes a Turing machine which accepts $x$} \\}$$.

The only difference here is that here we have to separate $x$ and $y$ ourselves. The standard trick is to use a new symbol to separate the two parts (assume that the separator belongs to $y$). Therefore any r.e. language including undecidable ones can be expressed in this format.

For the second question, there is no general algorithmic way to check if the prefixes of a given decidable language is undecidable. This follows from Rice's theorem.

# Answer
> 3 votes
Meta-knowledge: you want to find a non-decidable language which nonetheless has some computational property. An arbitrary non-decidable language is probably not going to lead you very far. But a semi-decidable one…

---

Stronger hint: what's a semi-decidable language? It means we can enumerate the words: it's some set of words $u$ such that there exists an integer $n$ such that

$$u = f(n)$$

Stare at this equation for a bit, with decidability and prefixes in mind.

---

Intuitively speaking, suppose you have some $x$ and you'd like to test whether it's in $\mathrm{Pref}(L)$. You're not going to do better in general than check $x a$, $x b$, $x a a$, etc. where $a,b,\cdots$ are the letters of the alphabet. This is a partial recursive function that tests membership in $\mathrm{Pref}(L)$. Of course, we knew that $\mathrm{Pref}(L)$ was r.e. already; what we need to show is that sometimes there's no alternative method. Let's take some set $S \subset \mathbb{N}$ which is r.e. and not recursive, and let $f$ be an enumeration of $S$ ($S = {f(x) \mid x\in\mathbb{N}}$).

Assume the alphabet contains three symbols $0$, $1$ and $:$ (if you only have two symbols $\\{\aleph,\beth\\}$, encode $0$ as $\aleph\aleph$, $1$ as $\aleph\beth$ and $:$ as $\beth$). If $n\in\mathbb{N}$, let $\bar n$ be $n$ written in base 2 using the symbols $0$ and $1$ with no leading $0$.

Let $L = \\{\bar y\mathord:\bar x \mid y = f(x)\\}$. In plain English, we're taking the elements of $S$ and tacking on their enumeration index. $L$ is clearly decidable (check that there is a single $:$, that the two digit sequences contain no leading $0$, and that the first digit sequence spells the image by $f$ of the number that the second one spells). Yet deciding whether some $\bar y$ is a prefix of $L$ is tantamount to deciding whether $y$ is in $S$, which you can't do without knowing $x$ since $S$ is not recursive by assumption. Formally, $\mathrm{Pref}(L)$ is not decidable, because $\mathrm{Pref}(L) \cap \\{0,1\\}^\*\mathord: = S\mathord:$ is not decidable.

---
Tags: computability, undecidability
---


# Question
Title: Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?

Anyway, here's the question:

> Show that the language $L = \\{xy \mid |x| = |y|, x\neq y\\}$ is context free.

# Answer
**Claim**: $L$ is context-free.

**Proof Idea**: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary.

**Proof**: For sake of simplicity, assume a binary alphabet $\Sigma = \\{a,b\\}$. The proof readily extends to other sizes. Consider the grammar $G$:

$\qquad\begin{align} S &\to AB \mid BA \\ A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\ B &\to b \mid aBa \mid aBb \mid bBa \mid bBb \end{align}$

It is quite clear that it generates

$\qquad \mathcal{L}(G) = \\{ \underbrace{w\_1}\_k x \underbrace{w\_2v\_1}\_{k+l}y\underbrace{v\_2}\_l \mid |w\_1|=|w\_2|=k, |v\_1|=|v\_2|=l, x\neq y \\} \subseteq \Sigma^\*;$

the suspicious may perform a nested induction over $k$ and $l$ with case distinction over pairs $(x,y)$.

The length of a word in $\mathcal{L}(G)$ is $2(k+l+1)$. The letters $x$ and $y$ occur on positions $k+1$ and $2k+l+2$, respectively. When we split the word in half, i.e. after $(k+l+1)$ letters, then the first half contains the letter $x$ on position $k+1$ and the second half has the letter $y$ on position $k+1$.

Therefore, $x$ and $y$ have the same position (in their respective half), which implies $\mathcal{L}(G) = L$ because $G$ imposes no other restrictions on its language.

---

The interested reader may enjoy two follow-up problems:

**Exercise 1**: Come up with a PDA for $L$!

**Exercise 2**: What about $\\{xyz \mid |x|=|y|=|z|, x\neq y \lor y \neq z \lor x \neq z\\}$?
> 46 votes

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


title: Are all system calls blocking?

text:
# Question
Title: Are all system calls blocking?
I was reading an article that describes the switch between user-space and kernel-space that happens upon a system call. The article says

> An application expects the completion of the system call before resuming user-mode execution.

Now, until now I was assuming that some system calls are `blocking`, whereas others are `non-blocking`. With the comment above, I am now confused. Does this mean that all system calls are blocking or did I misunderstand a concept?

# Answer
> 16 votes
You seem to be overloading the term 'blocking'.

Any context switch you make to the kernel, you have to wait for it to switch back to the usermode before your application can continue. This is not what is usually called 'blocking'.

In the current kernel design, blocking calls are calls where the kernel returns only when the request is complete (or error happens). These calls usually take longer amounts of time and usually lead your process to be scheduled out. For instance, many IO calls are blocking.

There are system call which provides asynchronous IO and they are non-blocking. Note that there is still a context switch that happens here, only the application has to take care of the asynchronous nature of the call.

The paper seems to aim to do away with this context switch back and forth (exception-less system calls) and try to make all the calls asynchronous.

---
Tags: operating-systems, os-kernel
---


# Question
Title: Decision problem such that any algorithm admits an exponentially faster algorithm
In Hromkovič's Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117):

> There is a (decidable) decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills
> $\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}\_{A'}(n) = \log\_2 \mathrm{Time}\_A(n)$

$\mathrm{Time}\_A(n)$ is the worst-case runtime of $A$ on inputs of size $n$ and $\forall^\infty$ means "for all but finitely many".

A proof is not given and we have no idea how to go about this; it is quite counter-intuitive, actually. How can the theorem be proven?

# Answer
> 13 votes
It seems to be a simple case of Blum's Speedup Theorem:

> Given a Blum complexity measure $(\varphi, \Phi)$ and a total computable function $f$ with two parameters, then there exists a total computable predicate $g$ (a Boolean valued computable function) so that for every program $i$ for $g$, there exists a program $j$ for $g$ so that for almost all $x$ $$f(x,\Phi\_j(x)) \leq \Phi\_i(x)$$

Just let the the complexity measure be the time complexity measure (i.e. $\Phi\_e(x)$ is the time complexity of the Turing machine with code $e$) and let $f(x,y) = 2^y$.

---
Tags: complexity-theory
---


# Question
Title: Which instruction yields atomicity in this expression that makes the result 2?
I am reading about atomicity and came across the following scenario

```
int x = y = z = 0;

Thread 1        Thread 2
---------       --------
x = y + z       y = 1
                z = 2

```

Which gives the following sets of output

$$\begin{array}{ccc}1&2&3\\ T1 : x = y + z&T2 : y = 1&T2 : y = 1\\T2 : y = 1&T2 : z = 2&T1 : x = y + z\\T2 : z = 2&T1 : x = y + z&T2 : z = 2\end{array}$$

Translating the $x=y+z$ expression to machine code gives

```
load r1; y
load r2; z
add r3; r1; r2
store r3;

```

However according to some notes I read going down the path of

```
T1 : load r1, y
T2 : y = 1
     z = 2
T1 : load r2, z
     add r3, r1, r
     store r3, x

```

I cannot seem to understand how the author came to result that $x=2$.

To me, based on the previous machine instructions the result should be 3, which I guess leads me to realize I am supposed to hit *eureka* (or a simple misread) and realize where the atomicity occurs. Could you explain the atomicity in this fairly simple statement that leads to the correct result?

# Answer
The point you are missing is that in thread $y$ is loaded into $r1$ and that any subsequent changes to $y$ will not affect the value stored in $r1$. Thus, the value in $r1$ is $0$ even after statement $y=1$. From this it is easy to see that the result is $x=2$.
> 7 votes

---
Tags: operating-systems, programming-languages, concurrency
---


# Question
Title: How is the loop invariant obtained in this square root bound finding algorithm?
*Originally on math.SE but unanswered there.*

Consider the following algorithm.

```
u := 0
v := n+1;
while ( (u + 1) is not equal to v) do
   x :=  (u + v) / 2;
   if ( x * x <= n)
     u := x;
   else
     v := x;
   end_if
end_while

```

where u, v, and n are integers and the division operation is integer division.

* Explain what is computed by the algorithm.
* Using your answer to part I as the post-condition for the algorithm, establish a loop invariant and show that the algorithm terminates and is correct.

In class, the post-condition was found to be $0 \leq u^2 \leq n \< (u + 1)^2$ and the Invariant is $0 \leq u^2 \leq n \< v^2, u + 1 \leq v$. I don't really understand on how the post-condition and invariants were obtained. I figure the post condition was $u + 1 = v$... which is clearly not the case. So I am wondering on how the post-condition and invariant was obtained. I'm also wondering on how the pre-condition can be obtained by using the post-condition.

# Answer
Gilles is right that the general technique is to go fishing for interesting observations.

In this case, you may observe that the program is an instance of binary search, because it has the following shape:

```
while i + 1 != k
  j := strictly_between(i, k)
  if f(j) <= X then i := j
  if f(j) > X then k := j

```

Then you just plug in your particular `f`, `X`, ... into the general invariant for binary search. Dijkstra has a nice discussion of binary search.
> 9 votes

# Answer
$u+1=v$ is indeed a post-condition of the while loop (why do you think it's “clearly” not the case?). This is always the case with a while loop that doesn't contain a `break`: when the loop exits, it can only be because the loop condition (here, $u+1 \neq v$) is false. It's not the only thing that will be true when the loop exits here (this algorithm actually computes something interesting, as you saw in your class, so $u = \text{\[this interesting thing\]}$ and $v = \text{\[this interesting thing\]}$ are also post-conditions), but it is the most obvious.

Now, to find other interesting properties, there's no general recipe. In fact, there is some formal sense in which there is no general recipe to find loop invariants. The best you can do is apply some techniques that only work in some cases, or generally go fishing for interesting observations (which works better and better as you get more experienced).

If you run the loop for a few iterations with some value of $n$, you'll see that at each iteration:

* either $u$ jumps up to $(u+v)/2$;
* or $v$ jumps down to $(u+v)/2$.

In particular, $u$ starts less than $v$, and will never overtake it. Furthermore, $u$ starts positive and increases, while $v$ starts at $n+1$ and decreases. So $0 \le u \le v \le n+1$ is an invariant throughout this program.

One thing that's not so obvious is whether $u$ can ever be equal to $v$. That's important: if $u$ and $v$ ever become equal, we'll have $x = u = v$ and the loop will keep going forever. So you need to prove that $u$ and $v$ never become equal in order to prove that the algorithm is correct (i.e. does not loop forever). Once this need has been identified, it is easy to prove (I'm leaving this as an exercise) that $u \< v$ is a loop invariant (keep in mind that $u$ and $v$ are integers, so this is equivalent to $u+1 \le v$).

Since $v = u+1$ at the end of the program, the post-condition you were given can also be written $u^2 \le n \< v^2$ (the part $0 \le u^2$ is trivial). The reason we want a post-condition like this, involving $n$, is that we want to tie the result of the program with the input $n$. Why this precise condition? We're looking for something that's as precise as possible, and we look at where $n$ appears inside the loop:

* we have $u \le x \le v$;
* when $x^2 \le n$, we pick the next $u$ to be $x$, so that $u^2 \le n$ (and $v$ doesn't change);
* when $x^2 \> n$, we pick the next $v$ to be $x$, so that $n \< v^2$ (and $u$ doesn't change).

This dichotomy hints that maybe $u^2 \le n \< v^2$ all the time. In other words, we suspect that it's a loop invariant. Verifying this is left as an exercise to the reader (remember to check that the property is true initially).

And now that we've done all this, we see that $u^2 \le n$ and $(u+1)^2 \> n$: $u$ is the square root of $n$ rounded down to the nearest integer.
> 7 votes

---
Tags: algorithms, loop-invariants, correctness-proof
---


# Question
Title: Do you get DFS if you change the queue to a stack in a BFS implementation?
Here is the standard pseudocode for breadth first search:

```
{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

```

Here `push` and `pop` are assumed to be queue operations. But what if they are stack operations? Does the resulting algorithm visit vertices in depth-first order?

---

If you voted for the comment "this is trivial", I'd ask you to explain why it is trivial. I find the problem quite tricky.

# Answer
No, this is not the same as a DFS.

Consider the graph

If you push the nodes in right to left order, the algorithm gives you a traversal:

$A, B , E, C , D$

while a DFS would expect it to be

$A,B,E,D,C$

The problem occurs because you mark it as seen at the time of pushing, rather than at the time of visiting. As pointed out in the comments, if you mark at the time of visiting, your space requirements might go up to $\Theta(V+E)$ rather than $\mathcal{O}(V)$.

I agree, the problem is not trivial.
> 27 votes

---
Tags: algorithms, graphs
---


title: Universality of the Toffoli gate

text:
# Question
Title: Universality of the Toffoli gate
Regarding the quantum Toffoli gate:

1. is it *classicaly* universal, and if so, why?
2. is it *quantumly* universal, and why?

# Answer
> 16 votes
Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$).

To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\epsilon$ and target unitary $U$ there is some way to apply a finite number of your quantum gates to get a unitary $U'$ such that $||U - U'|| \< \epsilon$.

Toffoli by itself is clearly not universal under this definition since it always takes basis states to basis states, and thus, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.

# Answer
> 10 votes
From the wikipedia article that you cited:

> The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Which means in simple terms that any boolean function may be constructed only with Toffoli gates.

Boolean functions are typically constructed from OR, AND and NOT gates, which may be combined to form any boolean function. It is widely know that the same is possible only with NOR gates or only with NAND gates.

The Toffoli gate may be summarized as:

$\rm{Toffoli}(a, b, c) = \begin{cases} (a, b, ¬c) & \mbox{when }a=b=1 \\ (a, b, c) & \mbox{otherwise.}\end{cases}$

Since the first and the second outputs are always equal to the first and second inputs, we may disconsider them. So we have:

$\rm{Toffoli}'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases}$

With that, it is possible to define the NAND gate as:

$\operatorname{NAND}(a, b) = \rm{Toffoli}'(a, b, 1)$

Since the NAND gate is universal and the NAND gate may be defined as a Toffoli gate, then the Toffoli gate is universal.

There is another way to prove that Toffoli is universal, by direct constructing the AND and NOT gates:

$\operatorname{NOT}(x) = \rm{Toffoli}'(1, 1, x)$

$\operatorname{AND}(a, b) = \rm{Toffoli}'(a, b, 0)$

Then, we may construct the OR gate using De Morgan's laws:

$\operatorname{OR}(a, b) = \operatorname{NOT}(\operatorname{AND}(\operatorname{NOT}(a), \operatorname{NOT}(b)) = \rm{Toffoli}'(1, 1, \rm{Toffoli}'(\rm{Toffoli}'(1, 1, a), \rm{Toffoli}'(1, 1, b), 0))$

---

EDIT, since the question was edited and its scope changed:

First, I don't understand quantical computing, so if there is something wrong, please add a comment. I did a little research to try to make this answer complete and ended with this:

The Toffoli gate is reversible (but the Toffoli' used above is not). This means that any computation did with it can be undone. This is:

$(a, b, c) = \rm{Toffoli}(\rm{Toffoli}(a, b, c))$

Which means that for any triple (a, b, c) if the Toffoli is applied twice, the original input is get as the output.

Reversibility is important because quantum gates must be reversible, so the (classical) Toffoli gate may be used as a quantum gate due to this.

As demonstrated here, the Deutsch gate is defined in a similar way that the Toffoli gate is, but instead of a classical gate, it is a quantical one:

$\operatorname{Deutsch}(a, b, c) = |a,b,c\rangle \mapsto \begin{cases} i \cos(\theta) |a,b,c\rangle + \sin(\theta) |a,b,1-c\rangle & \mbox{for }a=b=1 \\ |a,b,c\rangle & \mbox{otherwise.}\end{cases}$

In this way, the Toffoli gate is a particular case of the Deutsch gate where:

$\rm{Toffoli}(a, b, c) = \operatorname{Deutsch}(\frac{\pi}{2})(a, b, c)$

The Toffoli gate does classical computation, it lacks a phase-shift operation, this would mean that the Toffoli gate may be used only for 90 degrees ($\frac{\pi}{2}$) phase-shifts (and by combining multiple gates, to get multiples of 90 degrees). But this also means that it can't be used to create state sobrepositions because this would require phase-shifts on angles that are not multiple than 90 degrees, hence the Toffoli gate is not a universal quantum gate.

A universal quantum Tgate set may be obtained, if we combine the Toffoli gate whit the Hadamard gate. This is exactly what the Deutsch gate does.

Interesting references can be found here, here and here. A possible valuable reference, showing the foundations of the Deutsch transform should be here, however the link is password-protected.

---
Tags: quantum-computing, circuits, turing-completeness
---


# Question
Title: What is the height of an empty BST when using it in context for balancing?
Suppose the datatype for a BST is defined as follows (in SML)

```
datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

```

So there are two cases one in which the BST is `Empty` or it can have a (key,value) as well as two children.

Now, for the case of an AVL where the condition is

> In an AVL tree, the heights of the two child subtrees of any node differ by at most one
> <sub>\- AVL tree Wikipedia</sub>

I want to able to create a height function for use to check whether the tree is balanced. My current setup is as follows

```
fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

```

I tried to separate the Tree into three conditions

1. A empty Tree
2. A Tree with a root node
3. A populated tree

The reason for this is that there does not seem to be a canonical source on what the value is for the height of an `Empty` Tree as opposed to one in which only has a root. For the purposes of my balance function it did the job, but I rather try to understand why there isn't a canonical answer for the height of an `Empty` Tree.

There is a canonical answer, in a matter of speaking on Wikipedia but while initially doing research on this on Stack Overflow I arrived at many comments stating this to be wrong/incorrect/unconventional

> Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.)

I grabbed the question from which my uncertainty appeared

What is the definition for the height of a tree?

> I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.
>
> The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.

# Answer
> 5 votes
The **height** of a rooted tree is defined as the **length of the longest simple leaf-to-root path**

In the case of a 2 node tree, then clearly this length is 1.

In the case of a 1 node tree (a tree with just the root) then the length has to be 0. (There are 0 edges on the path from the leaf to the root.)

In the case of a 0 node tree, well -1 doesn't make sense. It is a **distance** and must have a value $\geq 0$, but neither does it make sense to try and measure the length of `null`.

-1 is sometimes chosen because of its consistency with this recurrence relation for the height of nodes: (which is basically the same as what you posted above)

```
height(null) = -1
height((v, left, right)) = max(height(left), height(right)) + 1

```

but we could just as easily define:

```
height((v, null, null)) = 0
height(null) = 0
height((v, left, right)) = max(height(left), height(right)) + 1

```

# Answer
> 6 votes
Any constant works as the height of `Empty`, because only the *difference* of heights is important for balancing. So, why not choose 0?

---
Tags: algorithms, data-structures, terminology
---


# Question
Title: Distinguishing between uppercase and lowercase letters in the "move-to-front" method
Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode `Matt_ate_the_mat` starting with an empty list.

Using the author's solution methodology of not taking into account `M` versus `m` one arrives at

$C(1)C^∗(M)\\ C(2)C^∗(a)\\ C(3)C^∗(t)\\ C(1)\\ C(4)C^∗(\\\_)\\ C(3)\\ C(3)\\ C(5)C^∗(e)\\ C(4)\\ C(3)\\ C(6)C^∗(h)\\ C(4)\\ C(4)\\ C(6)\\ C(6)\\ C(6)$

Seeing that move-to-front works best with items that are repeated this works to one advantage as long as the difference between `M` and `m` in the original message is not important, correct?

Though would it not change the last encodings if taking into account `m` to $C(7)C^\*(m)$ or was this done for the sake of brevity within the exam?

# Answer
> 5 votes
Though for us, human beings, `m` and `M` are the same, for a computer these are two distinct symbols that have no relation whatsoever.

The answer actually depends on the application:

* If your application is not case-sensitive, this separation does not matter, and the encoding is correct.
* If the application is case-sensitive there *must* be a distinction between lower case and upper case.

It seems to me that the encoding is more efficient as the number of symbols is smaller, thus maybe it is better to encode upper and lower case as an additional bit rather than having the list to contain 26x2 symbols, but this depends on the distribution of the text you are encoding.

---
Tags: combinatorics, data-compression
---


title: Not all Red-Black trees are balanced?

text:
# Question
Title: Not all Red-Black trees are balanced?
Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.

Of course, when we talk about red-black trees\*(see definition at the end) being balanced, we actually mean that they are *height* balanced and in that sense, they are balanced.

Suppose we try to formalize the above intuition as follows:

> **Definition:** A Binary Tree is called $\mu$-balanced, with $0 \le \mu \leq \frac{1}{2}$, if for every node $N$, the inequality
>
> $$ \mu \le \frac{|N\_L| + 1}{|N| + 1} \le 1 - \mu$$
>
> holds and for every $\mu' \gt \mu$, there is some node for which the above statement fails. $|N\_L|$ is the number of nodes in the left sub-tree of $N$ and $|N|$ is the number of nodes under the tree with $N$ as root (including the root).

I believe, these are called *weight-balanced* trees in some of the literature on this topic.

One can show that if a binary tree with $n$ nodes is $\mu$-balanced (for a constant $\mu \gt 0$), then the height of the tree is $\mathcal{O}(\log n)$, thus maintaining the nice search properties.

So the question is:

> Is there some $\mu \gt 0$ such that every big enough red-black tree is $\mu$-balanced?

---

The definition of Red-Black trees we use (from Introduction to Algorithms by Cormen et al):

A binary search tree, where each node is coloured either red or black and

* The root is black
* All NULL nodes are black
* If a node is red, then both its children are black.
* For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Note: we don't count the NULL nodes in the definition of $\mu$-balanced above. (Though I believe it does not matter if we do).

# Answer
**Claim**: Red-black trees can be arbitrarily un-$\mu$-balanced.

**Proof Idea**: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path.

**Proof**: Define a sequence $T\_k$ of red-black trees so that $T\_k$ has $k$ black nodes on every path from the root to any (virtual) leaf. Define $T\_k = B(L\_k, R\_k)$ with

* $R\_k$ the complete tree of height $2k - 1$ with the first, third, ... level colored red, the others black, and
* $L\_k$ the complete tree of height $k-1$ with all nodes colored black.

Clearly, all $T\_k$ are red-black trees.

For example, these are $T\_1$, $T\_2$ and $T\_3$, respectively:

---

\[source\]

---

\[source\]

---

\[source\]

---

Now let us verify the visual impression of the right side being *huge* compared to the left. I will not count virtual leaves; they do not impact the result.

The left subtree of $T\_k$ is complete and always has height $k-1$ and therefore contains $2^k - 1$ nodes. The right subtree, on the other hand, is complete and has height $2k - 1$ and thusly contains $2^{2k}-1$ nodes. Now the $\mu$-balance value for the root is

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

which proves that there is no $\mu \> 0$ as requested.
> 32 votes

# Answer
**No.** Consider a red-black tree with the following special structure.

* The left subtree is a complete binary tree with depth $d$, in which every node is black.
* The right subtree is a complete binary tree with depth $2d$, in which every node at odd depth is red, and every node at even depth is black.

It's straightforward to check that this is a valid red-black tree. But the number of nodes in the right subtree ($2^{2d+1}-1$) is roughly the *square* of the number of nodes in the left subtree ($2^{d+1}-1$).
> 15 votes

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


# Question
Title: Is this language defined using twin primes regular?
Let

$\qquad L = \\{a^n \mid \exists\_{p \geq n}\ p\\,,\ p+2 \text{ are prime}\\}.$

Is $L$ regular?

This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.

# Answer
> 17 votes
If the twin prime conjecture is true, then $L = a^{\*}$, which is regular. If the twin prime conjecture is not true, then there are finitely many twin primes; indeed, there is a largest pair of twin primes $\\{p, p + 2\\}$. In this case, $L = \\{a^{n} | n \< p + 1\\}$, a finite language. In either case, you get a regular language, so I think it's safe to conclude that $L$ is a regular language... we just won't know which one it is until the twin prime conjecture is resolved.

# Answer
> 11 votes
Yes, this language is regular. The twin prime conjecture need not be resolved in order to see this:

Suppose the twin prime conjecture is true, that is, for any $n$, we can find a prime $p \geq n$ such that $p+2$ is prime. Then in particular, $L = \\{ a^n | n \in N \\}$, as the condition is always true. This last language is expressible by $a^\*$ and hence regular.

Suppose the twin prime conjecture is false. Then there exists some $N$ such that there exists some prime $p$ such that $p+2$ is prime, and for every $n \> N$, there exists no $p$ such that $p+2$ is prime. In this case, $L = \\{ a^n | n \leq N \\}$, which is a finite language, and therefore regular.

By case distinction, we conclude that $L$ is regular.

# Answer
> 9 votes
It is regular in either case.

* If there are infinitely many twin primes, then $L=\\{a^n:n\geq 0\\}=L(a^\*)$.
* If there are finitely many twin primes, then $L$ is finite, therefore regular.

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


# Question
Title: Languages accepted by modified versions of finite automata
A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide some transition for all elements of the input alphabet; in other words, the transition function $\delta : Q \times \Sigma \rightarrow Q$ should be a (total) function.

Imagine what we will call a doubly deterministic finite automaton (DDFA). It is defined similarly to a DFA, with two exceptions: first, instead of the transition leading from one state to one other state for every possible input symbol, it must lead to two distinct states; second, in order to accept a string, all potential paths must satisfy either one or the other of the following conditions:

1. All potential paths through the DDFA lead to an accepting state (we will call this a type-1 DDFA).
2. All potential paths through the DDFA lead to the same accepting state (we will call this a type-2 DDFA).

Now for my question:

> What languages do type-1 and type-2 DDFAs accept? Specifically, is it the case that $L(DFA) \subsetneq L(DDFA)$, $L(DDFA) = L(DFA)$, or $L(DDFA) \subsetneq L(DFA)$? In the case that $L(DDFA) \neq L(DFA)$, is there an easy description of $L(DDFA)$?

Proofs (or at least moderately fleshed-out sketches) are appreciated, if they aren't too complicated.

# Answer
This combined with Alex's answer give the complete picture.

$L(DDFA)\subseteq L(DFA)$ can be proven by adapting the usual powerset construction with a modified final state condition. In the power set construction, states are sets of states from the original automaton. Usually after performing the powerset construction, a state is final if one of the states in the set is final in the original automaton.

* In type-1 DDFA, final states in the constructed automaton are the sets where all elements are final in the original automaton.
* In type-2 DDFA, final states are the singleton sets of the final states from the original automaton.

In both cases, the resulting automata are DFAs.

Now type-2DDFA's can express only the languages $\\{\epsilon\\}$ and $\emptyset$, depending on whether the starting state is accepting or not. This is because the two transitions from a state need to go to distinct states, but acceptance is only possible if they end up on the same state.
> 9 votes

# Answer
To start off the analysis, I can say that $L(DFA) \subseteq L(DDFA)$ for type-1.

You can do this by duplicating a DFA and adding edges to duplicated states. If a state $s\_1$ has a transition to $s\_2$ on $x$, you make a transition from $s\_1$ to $s\_2'$ on $x$ as well. In addition, $s\_1'$ has a transition to $s\_2$ and $s\_2'$ on $x$. Obviously, this means we will nearly always be in states $s\_i$ and $s\_i'$ at the same time (or possibly only $s\_i$, initially), and hence we will recognize the same language.

Update: we also have $L(DFA) \neq L(DDFA)$ for type-2, as there does not exist a type-2 DDFA that recognizes the language $\\{ a \\}$. If you try to make such a DDFA, you have a start state $s$, and then you have to have two outgoing edges to states $s\_1$ and $s\_2$ on an $a$, but these states must be distinct, and hence the two accepting paths end in different accepting states.

Together with Dave Clarke's answer, that gives you the complete analysis.
> 7 votes

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


# Question
Title: Equivalence of Kolmogorov-Complexity definitions
There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K\_1$ and $K\_2$ are kolmogorov complexity functions (defined via different languages or models), then there exists a constant $c$ such that for every string $x$, $|K\_1(x) - K\_2(x)| \< c$. I believe this is because for every Kolmogorov complexity function $K$ and for every $x$ it holds that $K(x) \le |x| +c$, for some constant $c$.

I'm interested in the following definitions for $K$, based on Turing-machines

1. **number of states**: Define $K\_1(x)$ to be the minimal number $q$ such that a TM with $q$ states outputs $x$ on the empty string.
2. **Length of Program**: Define $K\_2(x)$ to be the shortest "program" that outputs $x$. Namely, fix a way to encode TMs into binary strings; for a machine $M$ denote its (binary) encoding as $\langle M \rangle$. $K\_2(x) = \min |\langle M \rangle|$ where the minimum is over all $M$'s that output $x$ on empty input.

Are $K\_1$ and $K\_2$ equivalent? What is the relation between them, and which one grasps better the concept of Kolmogorov complexity, if they are not equivalent.

What especially bugs me is the rate $K\_2$ increase with $x$, which seems not to be super-linear (or at least linear with constant $C\>1$ such that $K\_2 \< C|x|$, rather than $|x|+c$). Consider the most simple TM that outputs $x$ - the one that just encodes $x$ as part of its states and transitions function. it is immediate to see that $K\_1(x) \le |x|+1$. However the encoding of the same machine is much larger, and the trivial bound I get is $K\_2(x) \le |x|\log |x|$.

# Answer
> 6 votes
I apologize in advance for that I give way too many details, but I'm about to contradict people.

### About $K(x)≤K'(x)+c$

The fact that $K\_1(x)≤K\_2(x)+c$ usually comes from an **interpreter** of the description language #2 into the description language #1 and **not** from a translation from programs of #2 into programs of #1.

For example $K\_\mathtt{C}(x)≤K\_\mathtt{Python}(x)+c\_\mathtt{py2c}$ and you get this inequality as simply as this:

```
void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

```

Then your constant $c\_\mathtt{py2c}$ will be something like $528+490240688$ where $528$ is the number of bits for this code and $490240688$ bits is the size the official Python interpreter written in C. Of course you only need to interpret what is possible in your description language for Python so you can do better than 69 MB :-)

What is important is that you can write your Python program **linearly** in your C code. For example, a language where you need to put "BANANA" between every character is not a very good description program and the property is then false. (But if the description language authorizes you to write data in a separate file or in a block, this problem disappear)

### Why your $K\_1(x)=q$ is flawed

The problem with your definition of $K\_1$ is that you may need more than $q$ bits to describe a Turing machine with $q$ states because you need to encode transitions.

So no $K\_1$ and $K\_2$ are probably not equivalent, but that's mainly $K\_1$'s fault. I think that we can prove that for all $a\>0$ there is a $c\_a$ such that $K\_1(x)≤a|x|+c\_a$. Of course any $a\<1$ is enough to disprove the fact that $K\_1$ is not a valid function, since it would mean that we can encode more all $2^n$ possible strings of length $n$ into $an+c\_a$ bits.

But the size is an incredibly tight bound when building Turing machines. The idea is that in a block of $b$ states there are $b^{2b}$ ways to find transitions for each state and that's better than the usual $2^b$ ways you can fill $b$ bits. Then you can store in each block $\log\_2 b$ bits of information. (not $2\log\_2 b$ because you have to go in and out the block one way or another)

So yeah... With blocks of size $2^{1/a}$ you could probably prove $K\_1(x)≤a|x|+c\_a$. But I already written way too much about why the number of states is not a valid Kolmogorov complexity function. If you want me to elaborate, I will.

### Now about $K\_2$

The naive descriptive language corresponds roughly to $K\_2(x)=q\cdot 2 \cdot (\log\_2 q + 2)$ (i.e. $\log\_2q$ for each next state and details about write and termination).

As you seem to be, I'm convinced that a better/cheater way would be to authorize to encode "data" into Turing machine, maybe by adding a binary tag in the description language that says whether if a state is a *data state* (that just writes a bit and go to the next state) or if it does something else. That way you could store one bit of your $x$ in one bit of your descriptive language.

However if you keep the same $K\_2$ you could use the same technique I used in the previous part to save a few bits, but I seem to be stuck at $K\_2(x)≤a|x|\log|x|+c$ (for any $a\>0$) .. maybe less than $\log|x|$, even, but obtaining $O(|x|)$ seems hard. (And I expect it should be $|x|$, not even $O(|x|)$.)

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: Is a function looking for subsequences of digits of $\pi$ computable?
How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable:

$$f(n) = \begin{cases} 1 & \text{if \\(\bar n\\) occurs in the decimal representation of \\(\pi\\)} \\ 0 & \text{otherwise} \\ \end{cases}$$

where $\bar n$ is the decimal representation of $n$ with no leading zeroes.

If the decimal expansion of $\pi$ contains all finite digit sequences (let's call this a universal number (in base 10)), then $f$ is the constant $1$. But this is an open mathematical question. If $\pi$ is not universal, does this mean that $f$ is uncomputable?

# Answer
> 3 votes
Note that $f$ can be the constant $1$ even if $\pi$ is not a normal number. (In French we say if $f$ is constant that $\pi$ is a *nombre univers*. I don't know the corresponding term in English)

For what it's worth: *it could be*, in the following way:

Proving $f$ is computable would not necessarily imply the resolution of the open question whether $f$ is constant or not. For example you can build $g$ that is computable but such that the constantness of $g$ is equivalent to Goldbach's conjecture.

Of course that does not even begin to answer your question, but it's likely open to me.

---
Tags: computability, real-numbers
---