title: Fastest static associative map

text:
# Question
Title: Fastest static associative map
Let's say that I wanted to build a key to value associative map where the only requirement was that lookup times were fast.

Once built, the associative map would not allow inserts, deletes, or modifications, so is a static data structure.

What would the best algorithm be for making and using such a thing?

I'm interested to know if there is a provable "best solution", or if it's provably NP-Hard or similar.

Here are some ideas of my own:

**Minimally Perfect Hash**

My best idea would be to use minimal perfect hashing. I would find a hashing algorithm that hashes the $N$ known inputs to $\[0,N)$, that resulting value being able to be looked up in an array.

I would want to find the computationally cheapest (average time) hashing algorithm for my data set.

However, finding a minimally perfect hash function is a challenging problem already without wanting the computationally cheapest one.

**Feature Based Indexing**

Another thought I have would be to look at my input and find bits which are differing between items. For instance, file paths may have a lot of the same characters in them, especially if they are absolute paths to the same deep folder.

I could find where the bits are that matter and make a tree of objects out of them.

The challenge here I think is that I would ideally want a balanced tree, and it might be hard to test all the permutations of bits that actually matter, to make the tree as balanced as possible.

I think Ideally, my hope is that the entire tree could go away, and I could instead take the bits that mattered and make some equation like "xor bit 2 against bit 3 and add bit 5" to come up with an index into an array.

# Answer
> 6 votes
Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $\[0,N)$ using only those features. This is effectively a way of building a perfect hash, where the hash function is expressed as a decision tree applied to the feature vector constructed from the input.

Building the smallest decision tree is NP-hard in general, but there are heuristic algorithms that do a reasonable job. You might look at the ID3 algorithm, for instance; in many settings it does a pretty good job of building a small (though not necessarily minimal) decision tree. You can compare that to other ways of building perfect hash functions and see which is computationally more efficient for your particular data set. Probably the only way to know is to try it out; I'm not sure there is any theory that will give you a definitive answer, as the answer probably depends on characteristics of your dataset that will be hard to model in a theoretical setting.

# Answer
> 2 votes
A practical answer to this question is that the fastest lookup is the simplest. Make a flat array of the data items you want to look up, and make sure all your keys are pre-processed (before run time, possibly at compile time) from their key value into the array index that they correspond to.

Furthermore, doing this, if the data is truly static, and has duplicate values in it, you can make multiple keys point at the same value to deduplicate the data.

This is the fastest pragmatic solution, but doesn't answer the question about what sort of data structures might be helpful, for the cases where you can't preprocess the data and keys in this way.

More info on this and similar techniques, including performance timings and source code, is available here: http://blog.demofox.org/2016/10/03/is-code-faster-than-data-examining-hash-tables/

---
Tags: data-structures, dictionaries
---


# Question
Title: How does lack of deadlock relate to computability in process calculi?
I'm interested in knowing things about the computability of concurrent programs. If you had a Turing complete language that also let you branch off new programs but had no means of communication between them there would be programs that you couldn't write. Namely those that required communication between concurrently running programs. At the other extreme it seems like the $\pi$-calculus can pretty well compute any program and has the power to implement almost any synchronization primitive I've ever heard of. But it also has deadlock much like Turing complete programs have infinite loops. So there seem to be degrees of power in synchronization/communication primitives although all I have figured out are extremes. This however seems analogous to programs without any kind of iteration or recursion and full Turing complete programs. One in-between would be mutexs that have levels to them at the type level. Every mutex could have levels to them at the type level. Every mutex could only be acquired if a higher mutex level had already been acquired by that thread. This would prevent deadlock but it would probably restrict some kinds of communication from occurring because the type system couldn't encode all well orderings on the mutexs (this is a bet, I have no proof). This feels analogous to something like primitive recursion or some other limited form of repeating computation (in fact, it's the kinda same problem of finding a well-ordering on objects in a program)

It's also easy to prove that a sufficiently strong language with a way to cause deadlock would not have decidable deadlock. Just replace infinite loops for dead lock in the standard proof of the halting problem. So yet again deadlock seems to have the kinds of properties that infinite looping has. On the other hand there is no way (that I know of, please tell me if this is possible) to detect infinite loops at run time *but* you can detect deadlock at run time. So dead lock also seems like an easier problem in a way as well.

Say I define a notion of total-program equality that goes something like "two languages are equal IFF every total program that can be written in one can be written in the other" where "total program" here is a function from naturals to naturals. More clearly stated if the set of total computable functions two languages can compute are the same then I'll call them "total-program equal". Every Turing complete language is total program equal and another neat fact is that have language that is total-program equal to a Turing complete language is not a total language! Assume that such a language existed, then an interpreter for it would be a total program that could be interpreted by a Turing complete language. Thus the supposed language could interpret itself. But such a total language (namely one which definitely has composition and paring and such) can't interpret itself so we have a contradiction. This is to say, there is no way to define a language that isn't going to contain non-total members.

I'd like to define something similar but for deadlock and the pi-calculus. Deadlock is tricky however. Separating deadlock from livelock is tricky to work with. Moreover I don't have a notion of the semantics of elements of a concurrent language. Certainly $\mathbb{N} \to \mathbb{N}$ doesn't really capture this because the programs were interested in keep outputting data on various channels as new data comes in. So there are some things that need to be formalized but basically I want a notion of "deadlock-free equivalent" languages. That is two languages are deadlock-free equivalent if the set of programs that they can define that never dead lock is the same set. Then I'd like to ask "is there a dead-lock free language that is deadlock-free equivalent to the pi-calculus?".

I don't really expect this exact question to have been answered but I was wondering if anyone has done work in this vain that I could look at? What are good models of process calculi like how $\mathbb{N} \to \mathbb{N}$ models computation. How do you formalize the difference between deadlock lock and livelock? Does being deadlock free cause such a language to not be able to interpret itself? Is there some other reason a dead lock free language as good as the pi-calculus can't exist? Answers to these questions here would be fantastic but I mainly just want to be pointed in the right direction to read further.

In a nutshell, lack of infinite loops means that you can't compute some programs even though they don't have infinite loops in them. Is the same true for deadlock? That is, will any language that never deadlocks have some programs that it can't compute?

# Answer
I think you are asking about expressivity of concurrent programming languages. This is a deep and not well-understood field. For example you say that "the $\pi$-calculus \[...\] has the power to implement almost any synchronization primitive I've ever heard of". It is well known that the $\pi$-calculus cannot implement broadcasting (see e.g. here). The $\pi$-calculus can also not implement $n$-ary synchronisation (think Petri nets) for all $n \> 2$, and $\pi$ can also not implement Ambient-calculus. Moreover, full mixed choice cannot be implemented by the asynchrnous $\pi$-calcululs, this is an old result by Palamidessi. There are more such results.

What I have not said here is what it means precisely for one calculus to implement another (or being unable to do so). There is no general agreement. For more on this, I suggest to consult the following.

* D. Gorla, Towards a Unified Approach to Encodability and Separation Results for Process Calculi.
* D. Gorla, Comparing Communication Primitives via their Relative Expressive Power.
> 5 votes

---
Tags: computability, reference-request, concurrency, deadlocks, process-algebras
---


# Question
Title: k-nearest neighbors (Euclidean distance): How to process multiple attributes?
Given this sample:

$$\begin{array}{|c|c|c|} \hline X1 & X2 (Kg/m^2) & \text{Class} \\ \hline 8 & 4 & A \\ \hline 4 & 5 & B \\ \hline 4 & 6 & B \\ \hline 7 & 7 & A \\ \hline 5 & 6 & B \\ \hline 6 & 5 & A \\ \hline \end{array}$$ we then calculate each of ***Euclidean distance*** values to the row:

with `P = (7, 4)`

$$\begin{array}{|c|c|c|} \hline X1 & X2 (Kg/m^2) & \text{Square distance to query point P} \\ \hline 8 & 4 & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline 4 & 5 & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline 4 & 6 & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline 7 & 7 & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline 5 & 6 & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline 6 & 5 & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline \end{array}$$

But what if each class has more than one attribute , for example: $$\begin{array}{|c|c|c|c|} \hline X1 & X2 (Kg/m^2) & \color{red}{X3} & \text{Square distance to query point P} \\ \hline 8 & 4 & \color{red}{2} & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline 4 & 5 & \color{red}{5} & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline 4 & 6 & \color{red}{1} & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline 7 & 7 & \color{red}{4} & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline 5 & 6 & \color{red}{6} & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline 6 & 5 & \color{red}{2} & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline \end{array}$$

How to calculate the Euclidean distance in this case?

# Answer
> 3 votes
Straight from definition:

$\sqrt{(q\_1-p\_1)^2 + (q\_2-p\_2)^2 + \cdots + (q\_n-p\_n)^2}$

In your particular case $n = 3$, so the query should also be 3D (e.g. {7, 4, 3}.

$\sqrt{(q\_1-p\_1)^2 + (q\_2-p\_2)^2 + (q\_3-p\_3)^2}$

So plugging in the third dimension: $$\begin{array}{|c|c|c|l|} \hline X1 & X2 (Kg/m^2) & X3 & \text{Square distance to query point {7, 4, 3}} \\ \hline 8 & 4 & 2 & (8 - 7)^2 + (4 - 4)^2 + (2 - 3)^2= 2 \\ \hline 4 & 5 & 5 & (4 - 7)^2 + (5 - 4)^2 + (5 - 3)^2= 14 \\ \hline 4 & 6 & 1 & (4 - 7)^2 + (6 - 4)^2 + (1 - 3)^2= 17 \\ \hline 7 & 7 & 4 & (7 - 7)^2 + (7 - 4)^2 + (4 - 3)^2= 10 \\ \hline 5 & 6 & 6 & (5 - 7)^2 + (6 - 4)^2 + (6 - 3)^2= 17 \\ \hline 6 & 5 & 2 & (6 - 7)^2 + (5 - 4)^2 + (2 - 3)^2= 3 \\ \hline \end{array}$$

---
Tags: machine-learning, nearest-neighbour
---


# Question
Title: Why are some programming languages Turing complete but lack some abilities of other languages?
I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that calls 'printf' with the exact same arguments that it got, and instead has to call an alternate version that take a variadic object. This is very problematic since I want to be able to make an object that hold an anonymous hook.

So, I thought that this was weird since Forth, JavaScript, and perhaps a plethora of other languages can do this very easily without having to resort to assembly language/machine code. Since other languages can do this so easily, does that mean that the class of problems that each programming language can solve actually varies by language, even though these languages are all Turing complete?

# Answer
> 71 votes
Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it.

This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features commonly found in modern languages.

Turing completeness tells nothing about having types, built in arrays/integers/dictionaries, input/output capabilities, network access, multithreading, dynamic allocation, ...

Just because Java does not have feature X (say, macros, higher-rank types, or dependent types), it does not suddenly stop being Turing complete.

Turing completeness and language expressiveness are two different notions.

# Answer
> 49 votes
Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

This does not, however, say how convenient it is to do so. Some features that are easy in some languages may be very difficult in others, due to design choices. Turing completeness just says that you *can* do the computation. As an extreme example, it may be difficult to hook varadic functions in C++, but it is possible to write a JavaScript interpreter in C++ which can hook variadic functions.

Language design is a pretty interesting art. One of the major steps one has to undertake is identifying which behaviors you want to form the backbone of your language. These behaviors are things that are easy to do in your language because they're built into the ground floor. We make design decisions about which features to include in every language.

As to your particular example, when C was developed, it was designed to operate very close to the way the assembly languages of the day operated. Variadic functions simply pushed arguments onto the stack, with very little typesafety. The implementation of these variadic functions was left to the compiler, to ensure maximum portability. Accordingly, very few assumptions were made about the capabilities of the hardware. By the time JavaScript came along, the scene had changed. It already operates in a virtual machine as an interpreted language, so the balance shifts towards convenience. Permitting hooking of variadic functions becomes reasonable. Even in the case of JavaScript that is Just In Time Compiled, our compilers are willing to store far more extra information about the arguments than the C compilers of yore were willing to store.

# Answer
> 26 votes
Think of programming languages as different land vehicles: bicycles, cars, hovercars, trains.

Turing Completeness says "this vehicle can go anywhere any other vehicle can go." That is, you can compute all the same functions. Input to output, start to end.

But, that statement says *nothing* about how you get there. It might be on rails, it might be on roads, it might be in the air. In the same way, Turing Completeness says nothing about *how* you compute a function. You might use recursion, or iteration, or some weird cellular automata. You might use types or not, you might use dynamic or static techniques. But, if all you consider is functions (or sets/formal languages) you can compute, as long as you are Turing Complete, these features give you the same power.

# Answer
> 17 votes
What you are essentially asking about is the difference between the *computational power* and what is commonly called the *expressive power* (or just *expressiveness*) of a language (or system of computation).

# Computational Power

The *computational power* refers to what kinds of problems the language can compute. The most well-known class of computational power is that which is equivalent to a Universal Turing Machine. There are a lot of other systems of computation, such as Random Access Machines, λ-calculus, SK combinator calculus, µ-recursive functions, `WHILE` programs, and many others. And as it turns out, all of these can simulate each other, which means that they all have the same computational power.

This gives rise to the *Church-Turing Thesis* (named after Alonzo Church who created the λ-calculus and Alan Turing who created the Universal Turing Machine). The Church-Turing-Thesis is a hypothesis on computability with two aspects:

1. all computing systems capable of general computation are equally powerful, and
2. a human being following an algorithm can compute exactly the functions that a Turing Machine (and thus any of the other systems) can compute.

The second is more important in the field of philosophy of mind than computer science, though.

However, there are two things the Church-Turing-Thesis *doesn't* say, that are very relevant to your question:

1. how *efficient* the various simulations are and
2. how *convenient* the encoding of a problem is.

A simple example for (1): on a Random Access Machine, copying an array takes time proportional to the length of the array. On a Turing Machine, however, it takes time proportional to the *square* of the length of the array, because the Turing Machine does not have random memory access, it can only move across the tape one cell at a time. Therefore, it needs to move across the **n** elements of the array **n** times to copy them. So, different models of computation may have different performance characteristics, even in the asymptotic case, where we try to abstract away from implementation details.

Examples for (2) abound: both λ-calculus and Python are Turing-complete. But would you rather write a program in Python or in λ-calculus?

There is also a third wrinkle I have skirted around until now: all of those original systems were designed by logicians, philosophers, or mathematicians, not by computer scientists … simply because computers and thus computer science didn't exist. These all go back to the early 1930s, even before Konrad Zuse's very first experiments (which weren't programmable and/or Turing-complete anyway). They only talk about "computable functions on the natural numbers".

Now, as it turns out, there's a *lot* you can express as functions on natural numbers – after all, our modern computers even get by with a lot less than that (basically 3-4 functions on the numbers 0 and 1, and that's it), but, for example, what function does an operating system compute?

This notion of I/O, side-effects, interacting with the environment, is not captured by the idea of "functions over natural numbers". And yet, it is kind of important, since, as Simon Peyton Jones once put it "All a pure function with no side-effects does, is make your CPU hot", to which an audience member replied "actually, that *is* a side-effect, too!"

Edwin Brady, the designer of Idris, (only half) jokingly uses (I don't know whether he invented it) the term "Tetris-complete" to express this difference between "can compute any computable function on natural numbers" and "can be used to write non-trivial programs that interact with the environment". Even more ironically, he demonstrates this by having an implementation of a Space Invaders clone in Idris, but he says that he is confident that Tetris reduces to Space Invaders.

Another thing to point out is that not only is Turing-equivalence not necessarily *enough* to talk about actually writing "useful" programs, it may OTOH also not even be *necesssary*. E.g. SQL has only become Turing-equivalent with ANSI SQL:1999, but it was still useful before that. In fact, some might argue that making it Turing-equivalent hasn't added to its usefulness at all. There are many Domain-Specific Languages that aren't Turing-equivalent. Data Description Language typically aren't (and shouldn't be). Total Languages obviously can't be Turing-equivalent, yet you can still write event loops, web servers, or operating systems in them. There are also languages which are Turing-equivalent but where this is actually considered to be a mistake.

So, all in all, Turing-equivalence is not terribly interesting, unless you want to statically analyze programs.

# Expressiveness

Assuming that our computation system is computationally powerful enough to even solve our problem at all, what we have to do next, is to express our algorithm for solving that problem in some sort of formal notation for that system. In other words: we need to write a program in some computer language. That's where the notion of *expressiveness* comes in.

It refers to, essentially, how "easy" or "enjoyable" it is to write our program in our particular programming language. As you can see, the notion is quite vague, subjective, and more psychological than technical.

However, there are attempts at more precise definitions. The most famous one (and the most rigorous one I know of) is by Matthias Felleisen in his paper *On the Expressive Power of Programming Languages* (the first two pages contain a gentle introduction, the rest of the paper is more meaty).

The main intuition is this: when translating a program from language to another language, some of the changes you need to make are locally contained (such as e.g. turning `FOR` loops into `WHILE` loops or loops into conditional `GOTO`s), and some require a change to the global structure of the program.

When you can replace one feature of one language with a different feature of a different language by only local transformations, then these features are said to have no effect on the expressive power. This is called *syntactic sugar*.

On the other hand, if it requires a change of the global structure of the program, then the language you are translating to is said to be unable to express the feature. And the language you are translating from is said to be *more expressive* (with respect to this feature).

Note that this gives an objectively measurable definition of expressiveness. Note also that the notion is context-dependent on the feature, and it is comparative. So, if every program in language **A** can be translated to language **B** with only local changes, and there is at least one program in language **B** which can *not* be translated to **A** with only local changes, then language **B** is strictly more expressive than language **A**. However, the more likely scenario is that many programs in both languages can be translated back and forth, but there are some programs in both languages that cannot be translated to the other. This means that neither language is strictly more expressive than the other, they just have different features that allow different programs to be expressed in different ways.

This gives a formal definition of what it means to be "more expressive", but it still doesn't capture the psychological notions behind the phenomenon. For example, syntactic sugar, according to this model, does not increase the expressive power of a language, because it can be translated using only local changes. However, we know from experience that having `FOR`, `WHILE`, and `IF` available, even if they are just syntactic sugar for conditional `GOTO` makes expressing our intent *easier*.

The fact is, different languages have different features that make expressing different ways of thinking about a problem easier or harder. And some people might find one way of expressing their intent easier and others a different way.

An example I found in the Ruby tag on StackOverflow: many users who follow the Ruby tag claim that loops are easier to understand than recursion and recursion is only for advanced functional programmers and loops are more intuitive for newcomers, but I have seen multiple cases of complete newcomers who intuitively write code like this:

```
def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

```

Which usually leads to several people commenting that "this doesn't work" and "they are doing it wrong" and the "correct way" is this:

```
def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

```

So, clearly, there are some people for whom tail recursion is a more natural way to express the concept of "looping" than loop constructs.

# Summary

The fact that two languages are Turing-equivalent says one and exactly one thing: that they can compute the same set of functions on natural numbers as a Turing Machine can. That's it.

It doesn't say anything about how fast they compute those functions. It doesn't say anything about the ease of expressing those functions. And it doesn't say anything about what else they can do besides computing functions on natural numbers (e.g. linking to C libraries, reading input from the user, write output to the screen).

> does that mean that the class of problems that each programming language can solve acctually varies by language, even though these languages are all turing complete?

Yes.

1. There are problems that aren't covered by the term "Turing-complete" (which only concerns itself with computing functions on natural numbers) such as printing to the screen. Two languages can be Turing-complete but one can allow printing to the screen and the other not.
2. Even if both languages can solve the same problems, that doesn't say anything about how complex the encoding is, and how easy it is to express this encoding. E.g. C can solve every problem Haskell can, simply by writing a Haskell interpreter in C … but you have to write the Haskell interpreter first in order to solve a problem this way!

# Answer
> 7 votes
All Turing complete programming languages can implement the same set of algorithms. So, if you see that some algorithm is very difficult to be implemented in a particular language, it does not mean it is impossible.

Remember that a language consists of syntax and semantics. Sometimes, the set of words belonging to some language is not minimum to be considered Turing complete, there are *features* that make things easier (that’s why they are called *features*). If you take out those features, the language is still Turing complete.

Some of these might be of interest:

# Answer
> 5 votes
All Turing-complete languages can compute the same things.

If you try to implement a modern language, you'll notice that most of its features do not *add* any computational capabilities. Many of those features can be lowered to simpler ones that already exist in the same language.

Here are some examples:

* If you don't have enums, you can use integers.
* If you don't have buffers that know their size, you can create a type that contains a size and a buffer that doesn't know its size.
* If you don't have bounds checking of buffers, you can just check the index every time you use them.
* If you don't have variadic functions, you can create a function that takes a buffer that knows its size and read from that buffer the same information that you'd get from formal arguments.
* If you don't have operators, you can use functions.
* If you don't have types that can inherit each other, you can create types that contain each other and access them through an extra level of indirection, with subtyping being simply a transformation of the handle-to-the-entire-type to a handle-to-the-contained-type.
* If you don't have delegates but you have function pointers, you can create a type that contains the referent object and a function pointer.
* If you don't have delegates but you have interfaces, you can declare an interface that contains a single method with the signature you want.
* If you don't have generic types, you can use non-generic types that only assume the upper or lower bounds you are interested in (and maybe perform appropriate casts at the usage spots, to keep the compiler happy).
* If you don't have a linear/affine type system, you can just avoid using any variable more than once.
* ...and so on.

Mainstream language design focuses on features that make it *easier* and *more convenient* for us to compute things faster, recognize our mistakes earlier, program against unknown components, make parallelism safer, and so on.

The purely computational stuff were nailed down a long time ago.

# Answer
> 4 votes
The existing answers rightly point out that Turing completeness is not a good way to compare languages. Indeed, almost all languages are Turing complete. ("If everyone is special, then no one is special," as The Incredibles used to say.)

However, it *is* possible to compare the expressiveness of languages with mathematical precision. Take a look Felleisen's On the Expressive Power of Programming Languages. Roughly, the idea is to ask the following question: Can I convert any program in language A into a program in language B by making only *local* changes? In other words, Felleisen gives a mathematically precise form to your intuition.

# Answer
> 3 votes
On top of everyone else's answers, here's another analogy.

To wash clothes, you need three things: some reservoir which holds water, a detergent of some kind, and an agitation mechanism. This could be realised in many ways. The water reservoir is anything which holds enough water (e.g. a tub, a lake, a river). The agitation mechanism could be a mechanical device, a washboard, or even a rock against which the clothes are beaten. And detergents come in various forms, too.

So what's the difference between a modern computerised washing machine, and a rock next to a river?

It boils down to three things: efficiency, safety, and convenience. Some methods of washing use less energy, pollute the environment less, use less water, and so on. Some methods of washing require less repetitive manual activities (which result in injuries) or being outside in inclement weather. And some methods of washing don't require a human to babysit the process.

Turing-complete programming languages are general purpose, so they are put to more than one task. Nonetheless, for a given task, some programming languages are more efficient, more convenient, and safer (in the sense that less can go wrong when the program is actually used) than others.

# Answer
> 2 votes
Others have provided plenty of good answers, but they don't explicitly mention one caveat that once confused me a lot: Turing completeness doesn't imply that a language can express arbitrary computable functions from its inputs to its outputs. It is weaker: there must be *some* way of representing the domain and range of the set of computable functions as inputs and outputs such that each of these functions maps to a program that takes a representation of its inputs to the corresponding outputs.

Take, for instance, a language that expresses Turing machines. Each program in the language is a Turing machine.

Now consider the sublanguage of all Turing machines that read and write only the characters a, b, and blank. It is Turing complete, but it cannot express any programs that, for instance, produce c on all inputs, because it can't write any cs. It can only express all computable functions on inputs and outputs encoded as strings of as and bs.

So it isn't true that all Turing-complete languages can compute the same things, not even when we limit these things to be the computable functions from their potential inputs to their potential outputs. The language may require inputs and outputs to be encoded in certain ways.

---
Tags: computability, programming-languages, turing-completeness
---


# Question
Title: Why the need for TSP solvers when there are SAT solvers?
Concorde TSP is a solver for TSP. SAT solvers are solvers for boolean satisfiability. TSP and SAT are NP-complete.

Hence, why spent the time to develop Concorde TSP when there is an abundance of SAT solvers in the market back then?

# Answer
> 13 votes
**TL;DR**: polynomial reduction *increases* the size of a problem; using a specific solver allows you to *exploit* the structure of a problem.

When you reduce one NP-complete problem to another one, the size of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of $\Theta(n^3)$ (I don't remember about the constant that arises in a straight-forward TSP-\>SAT reduction). If you use the Cook-Levin theorem, then the growth might be even bigger because a Turing machine might have really huge (polynomyal) overhead. NP-completeness is mostly a theoretical idea. So is a polynomial-time reduction. Many theoretical papers only state that *there is* a reduction, saying nothing about *how practical* it is.

Let's informally assume that TSP is *as hard* as SAT. It means that it takes similar computational resources to solve TSP on $n$ nodes and SAT with $n$ clauses if you use state-of-the-art solvers for each problem. Now it is easy to see that writing a separate solver is more practical than reducing the problem to SAT and using some existing SAT solver. It is all about polynomial overhead.

There is one more thing to notice: exact problems are usually simpler than broad ones. When you reduce TSP to SAT, the SAT solver knows nothing about the underlying structure of the formula. And special solvers for TSP, of course, deal with the fact that the input is a graph, the problem is to find a shortest Hamiltonian path, so on.

Although for some problems reduction to SAT can be reasonable, mostly if the problem is not well-studied (and no cool solvers exist) and when reduction doesn't increase the problem size a lot. SAT solvers are still very strong for many practical purposes.

---
Tags: np-complete, satisfiability, p-vs-np, traveling-salesman, sat-solvers
---


# Question
Title: Proving the Language is not regular for $(a^n)^n$
I am trying to solve a pumping Lemma Problem where $L= \\{(a^n)^n ; n\ge 0\\}$ I am having a lot of trouble with the pumping lemma and understanding using it with different languages. Here is what I have so far and would appreciate any input on it.

Assume for contradiction that $L$ is a regular language. Since $L$ is infinite we can apply the pumping Lemma. Let $p$ be the critical length for $L$.

Let $w = (a^p)^p$ and length of $|w|\>=p$. From the pumping lemma we can write $w = (a^p)^p = xyz$. With $|xy| \le p$ and $|y| \ge 1$. Thus $y = a^k, 1\le k\le p$. So for $xy^iz \in L$ we can take $xy^0z = xz = (a^{p-k})^p$ which should be contained in $L$ but since it is not we have a contradiction thus the language is not regular.

Any help or recommendations is appreciated, thank you.

# Answer
> 6 votes
You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\\{a^{n^2}\mid n\ge 0\\}$ isn't regular.

Assume $L$ is regular. Since $L$ is infinite, there's an integer $p$ for which the PL applies, so choose $s=a^{p^2}$ and write $s=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Hence, $y=a^k$ with $1\le k\le p$. Then the PL implies that $xz\in L$. Thus we know that $|xz| =p^2-k$, \[You goofed here.\] and since $k\le p$, we have $$ |xz| =p^2-k\ge p^2-p \>p^2-2p+1=(p-1)^2 $$ and so $(p-1)^2\< |xz|\<p^2$ and so $xz\notin L$, since $xz$ lies strictly between two adjacent (lengthwise) elements in $L$ and so can't be in $L$, a contradiction.

\[The only way this could fail is if $-p\le -2p+1$ and that only holds when $p\le 1$ which we know must be true, since $p$ is the number of states of a FA that accepts $L$ and clearly a one-state FA won't recognize $L$.\]

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: How exactly is this equation for insertion sort time complexity solved so that it shows it is linear?
# Background

I am currently taking an Algorithm and Analysis course and doing some extra studying on my own from the text book. This is not a homework question or exercise even. I am just trying to understand completely how the authors are doing the combining of terms in the time/cost equation for Insertion-Sort.

I understand what is being shown up until we get to the actual equation. I understand that each line, barring the comment which is considered to not have a cost, has a constant cost `c`.

This is how they have broken down the time/cost for the algorithm in psuedo-code:

1. `for j = 2 to A.length`
2. `key = A[j]`
3. `//Insert A[j] into the sorted`
4. `sequence A[1..j - 1]`
5. `i = j - 1`
6. `while i > 0 and A[i] > key`
7. `A[i + 1] = A[i]`
8. `i = i - 1`
9. `A[i + 1] = key`

Here's the cost/time for each line according to textbook:

1. $c\_1n$
2. $c\_2(n-1)$
3. 0
4. 0
5. $c\_4(n - 1)$
6. $c\_5 =\sum\nolimits\_{j}^{n} 2t$
7. $c\_6=\sum\nolimits\_{j}^{n} 2{t - 1}$
8. $c\_7=\sum\nolimits\_{j}^{n} =2{t - 1}$
9. $c\_8(n - 1)$

The best case run time of the algorithm is then given by:

> $$ T(n) = \ c\_1(n) + c\_2(n - 1) + c\_4(n - 1) + c\_5(n - 1) + c\_8(n - 1) $$

This is where I get confused. Somehow they combine all of these terms to simplify the equation but it's done in one step so I can not follow/reproduce it on my own. This is what they come up with:

> $$ = (c\_1 + c\_2 + c\_4 + c\_5 + c\_8)n - (c\_2 + c\_4 + c\_5 + c\_8) $$

According to the author it can be expressed as $an + b$ and thus a linear function of $n$. As mentioned above, I don't know how they simplified the equation nor how it can be expressed as $an + b$. I do understand that it is in linear equation form. How do I make the leap or bridge the gap per say?

# Answer
> 0 votes
The time complexity of the insertion sort is O(n2) in the worst case(array in decreasing order) and O(n) in the best case(array in non decreasing order). These bounds result from the variance in the number of iterations of the inner while loop or in other words the while loop dominates the running time of the algorithm. Considering the number of iterations while loop makes in different cases can be summarized as follows :

c5 = ∑nj 2t

**In the best case** : where while loop finds the condition A\[i\] \> key as true in the first iteration itself the t evaluates to 1 and thus the summation evaluates to O(n) . Therefore you see a constant term multiplied by n in the best case expression for T(n). Also there are no shifts required therefore the terms for line number 7 and 8 become zero and you don't see the constant terms c6 and c7 in the final expression for T(n) in the best case. (c6=∑nj2(t−1) , substituting t = 1 makes the summation 0.)

**In the Worst case** : the while loop has to make n-1 iterations in the worst case iterations to find a value A\[i\] \> key . The value of t becomes n-1 and the summation evaluates to O(n2).

**The question about T(an+b)** : 'a' is nothing but a constant a \>= c1+c2+c4+c5+c8

I suspect it is not the algebraic simplification which you are confused about and i have made my point clear.

# Answer
> 2 votes
So you question is how to go from:

```
T(n)= c1(n)+c2(n−1)+c4(n−1)+c5(n−1)+c8(n−1)

```

to

```
T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)

```

Step 1 (Expand the statement):

```
T(n)= c1(n)+c2(n)−c2+c4(n)−c4+c5(n)−c5+c8(n)−c8

```

Step 2 (Group similar elements):

```
T(n)= c1(n)+c2(n)+c4(n)+c5(n)+c8(n)−c2-c4-c5-c8

```

Step 3 (Find the factors):

```
T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)

```

# Answer
> 1 votes
You might be confusing $c\_1(n)$ to a function application: the function $c\_1$ applied to $n$. However, here it just means the constant $c\_1$ multiplied by the variable $n$. Given this, the simplification in the formula for $T(n)$ is simple algebra. Rendering the resulting expression in the form $an+b$ is also simple algebra.

---
Tags: algorithm-analysis
---


# Question
Title: Joining tables with minimum number of joins
I am working on a generalized problem where I am given only schema definition of multiple tables that i have.

Now i have to retrieve certain columns by joining multiple tables such that number of joins are minimized.(i will consider where condition in sql clause later)

Example: Suppose i have 3 tables and here is the list of columns that they have.

**Table 1:(1,2,3,4,5), Table 2:(5,6,7), Table 3:(5,6,7,8)**

Now suppose I have a query in which i want all the columns 1,2,3,4,5,6,7,8.

Now i can join either table 1,table 2 and table 3 OR table 1 and table 3.I would get the required information in both the cases but joining table 1 and table 3 would require only 1 join rather than 2 join in other case.

What i was trying was a greedy algorithm in which first i would consider table that has maximum number of required columns then eliminate the common columns between the query and table(from both query and table) and then consider updated required columns and update tables and so on.But i guess it would be slow.

So is there a generalized algorithm or if anyone can give me any hint in this direction?

# Answer
> 1 votes
I believe that your problem is NP-complete.

Showing that it's in NP is easy. To show that it's NP-hard, take any instance of the set cover problem. Add a new unique element to the universe, and add it to each set. Interpreting each set as a table, a solution to the minimum join problem is a solution to the original set cover problem.

---
Tags: algorithms, efficiency, database-theory, relational-algebra
---


# Question
Title: Backward data-flow: post-order or RPO on reverse CFG?
When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which makes sense.

Other resources (such as the "Engineering a Compiler" book) suggest to use reverse post-order (RPO) on the reversed CFG instead.

... and PO(graph) != RPO(rev(graph)) in some cases involving cycles.

My question is: which resource is right? Post-order makes sense, so why not just use that and save the CFG inversion? Why would I use RPO on reversed CFG instead?

# Answer
It is mostly due to the speed of convergence. To clarify, RPO visits as many predecessors possible before visiting a node so in case of forward data flow problems (like Dominator computation) this would help to converge faster. You can find more details in Engineering a compiler book (which you already know!)
> 1 votes

---
Tags: compilers, graph-traversal, data-flow-analysis
---


# Question
Title: Can other models of computation equivalent to Turing machines also recognize the same languages?
There are other models of computation equivalent to Turing machines in terms of computability.

Turing machines also recognize recursively enumerable languages.

My questions are

* Do other models of computation equivalent to Turing machines also recognize the same languages?
* Are computability and language recognization unrelated to each other, so that other models of computation equivalent to Turing machines don't recognize or accept any language?

Thanks.

# Answer
> 2 votes
Two models of computation are equivalent iff they can compute exactly the same set of functions. So the answer to your question is yes, they can recognize the same languages. The definition of "accept" has to be altered a bit to fit the new model, of course, since for example in the lambda calculus you have no states that you could mark as accepting.

# Answer
> 1 votes
> Do other models of computation equivalent to Turing machines also recognize the same languages?

Yes. That's the definition of "equivalent to Turing machines"! In particular, to be equivalent to Turing machines, a model has to have something equivalent to not halting.

> Are computability and language recognization unrelated to each other

Recognizing a language is computing membership of a set of strings; computing a yes/no function is recognizing the language "the set of strings that make the function true".

---
Tags: formal-languages, computability, automata, computation-models
---


# Question
Title: Why does the following Backus-Naur form reflect the following syntax diagram?
The definition of the variable

\< number\>::=\< digit \> | \< digit \>\< number \>

where \< digit \> is defined as

\< digit \> ::= 1|2|3|4|5

Apparently reflects the following syntax diagram

Please explain why this is the case. I am particularly confused with the clause after the vertical OR line (i.e. \< digit \>\< number \>) and whether it has something to do with the fact that number can consist of many digits.

# Answer
> 2 votes
`< number>::=< digit > | < digit >< number >` means that a number is either just a digit, or a digit followed by a number. So 1 is a number (just a single digit), and 12 is also a number (a single digit, followed by a number that consists of just the single digit '2'). Similarly 123 is a number that consists of a single digit '1' and a number (that itself consists of a single digit '2' followed by a number (that consists of the single digit '3')).

---
Tags: syntax
---


title: how type checking fails?

text:
# Question
Title: how type checking fails?
I was doing a type checking example in system f sub on paper to understand how it works.

according to Pierce's book Types and Programming Languages, numbers and their types are following in system f sub. (see chapter 26.3, page 399)

```
   1)top is universal type,
   2)capital letters are type variables, small letters are term variables

    church number 1
    sone = λA<:top.λB<:A.λC<:A.λx:(A-->B).λy:C.x y
    stwo = λA<:top.λB<:A.λC<:A.λx:(A-->B).λy:C.x (x y)

    type for church number 0
    SZero = ∀A<:top.∀B<:A.∀C<:A.(A-->B)-->C-->C

    type for numbers except 0
    SPos = ∀A<:top.∀B<:A.∀C<:A.(A-->B)-->C-->B
    SNat = ∀A<:top.∀B<:A.∀C<:A.(A-->B)-->C-->A

```

for the type checking

```
   Γ |-  stwo :  SZero

```

should fail.

book said "SPos is inhabited by all the elements of SNat except SZero".
Also I saw there is a input test test files, it shows above example should fail.

Therefore, I assume

```
 Γ |-  sone :  SZero

```

should fail too.

I want to see how it is going to fail and did pen-paper type checking as following (see type checking rules in the same book, previous page)

```
  1)for convenience, I wrote from top to down fashion
  2)variables are given distinct

   Γ |-  (λA<:top.λB<:A.λC<:A.λx:(A-->B).λy:C.x y)
       : (∀A1<:top.∀B1<:A1.∀C1<:A1.(A1-->B1)-->C1-->C1)
   ---------------------------------------------(T-TABS) =>assume A=A1,top=top
                                                             ,and renamed A1 to A
  A<:top |- (λB<:A.λC<:A.λx:(A-->B).λy:C.x y)
           :(∀B1<:A.∀C1<:A.(A-->B1)-->C1-->C1)
  ----------------------------------------------(T-TABS) =>assume B=B1, rename B1 to B

A<:top,B<:A |- (λC<:A.λx:(A-->B).λy:C.x y)
              :(∀C1<:A.(A-->B)-->C1-->C1)
 ---------------------------------------------------(T-TABS) =>assume C=C1, rename C1 to C
 A<:top,B<:A,C<:A |- (λx:(A-->B).λy:C.x y)
                   : (A-->B)-->C-->C
 -----------------------------------------------------T_ABS =>have A-->B=A-->B,   get A=A,B=B,remove them

 A<:top,B<:A,C<:A,x:A-->B |- (λy:C.x y) : C-->C
 ------------------------------------------------T-ABS ==>have  C=C
 A<:top,B<:A,C<:A,x:A-->B,y:C | ( x y ) : C
 ----------------------------------------------- T-APP  introduce type variable T1
 A<:top,B<:A,C<:A,x:A-->B,y:C | x : T1-->C  A:top,B<:A,C<:A,x:A-->B,y:C | y:T1
 ----------------------------------------  ----------------------------------
   have X:T1-->C                                   have y:T1
        X:A-->B                                         y:C
    so, T1=/=A, B=/=C                                   T1=/=C

```

so fails I assume.

I thought the type checking

```
  Γ |-  sone :  SPos

```

should be successful, but it ..

```
 1) type is different a bit here

   Γ |-  (λA<:top.λB<:A.λC<:A.λx:(A-->B).λy:C.x y)
       : (∀A1<:top.∀B1<:A1.∀C1<:A1.(A1-->B1)-->C1-->B1)

        intermediate steps are all same
         .................
               .....
  A<:top,B<:A,C<:A,x:A-->B |- (λy:C.x y) : C-->B
 ------------------------------------------------T-ABS ==>have  C=C
 A<:top,B<:A,C<:A,x:A-->B,y:C | ( x y ) : B
 ----------------------------------------------- T-APP  introduce type variable T1
 A<:top,B<:A,C<:A,x:A-->B,y:C | x : T1-->B  A:top,B<:A,C<:A,x:A-->B,y:C | y:T1
 ----------------------------------------  ----------------------------------
   have X:T1-->B                                   have y:T1
        X:A-->B                                         y:C
    so, T1=/=A, B=B                                   T1=/=C

```

See, these two type checking ended up pretty same, I did not understand why the first type checking should fail, while second one should be successful.

How to do type checking in system F sub? If you know, please correct me, thank you.

# Answer
I finally figured it out. The key is using sub-typing rules.

```
         ctx[]|- t:S     ctx[]|S<:T
         ---------------------------t-sub
               ctx[]|-t:T

```

By applying this rule after T-APP rules, you can eliminate all "A==B" equations by using

```
       eq(A,A) -> .
       eq(A-->B,A-->B) -> eq(A,A),eq(B,B).
         ........

```

One can easily observe how to write these rules to eliminate "eq"s. If there is one or some "eq"s left, such as "eq(A,B)", means a contradiction, so type checking fails.

If you can eliminate all "eq"s, means type checking successful.

One important point about "t-sub" rule is that it is not suitable for implementation, because it is not syntax directed. That rule is applicable for any statement with the form of

```
       ctx[]|t:T

```

therefore, algorithmic version is proved to has the same power in the book "Types and Programming Languages".

:)
> 2 votes

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


title: A question about type rule

text:
# Question
Title: A question about type rule
I realized that almost no one explained how to selected the type variable T1

```
 Γ ⊢ e1 : T1 -> T  ,  Γ ⊢ e2 : T1
 -------------------------------- T-APP
 Γ ⊢ e1 e2 : T

```

when doing type checking (from bottom to top).

So, the question is how T1 is introduced? Is there any condition about T1?

# Answer
> -1 votes
"T1" is obtained from typing context by doing derivation on the right branch of application rule. I worked on some type checking examples and concluded that.

# Answer
> 4 votes
`T1` is a schematic variable. Every consistent substitution of `T1` with a type produces an instance of the rule. In a simple enough system, the inference rules can be used directly as the blueprint for a type-checking algorithm. In languages with richer type systems, type-checking algorithms become more complex or even undecidable (which is not a desirable features). Let me give an example where I type-check the program using a simple derivation.

Let's say I have the following program I wish to type-check:

```
(lambda x: nat. x = 0)(4)

```

First, we can deduce that `4 : nat` by using the usual typing rules for natural numbers, which I will not reproduce here. Then we type-check the lambda abstraction with following derivation (I apologize for the sloppy latex):

$$ \underline{x : nat ⊢ x: nat \quad x: nat ⊢ 0 : nat} $$ $$ \underline{x : nat ⊢ x = 0 : bool}$$ $$ \underline{\lambda x: nat. \ x = 0 : nat \to bool} $$

Finally, using the application rules:

$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool \quad 4 : nat} $$ $$ (\lambda x: nat. \ x = 0)(4) : bool $$

Note that type-checking is much simpler when we're working in a type system without subtyping, in that ever expression is monomorphic. The typing rules are *syntax-directed*. That is, the structure of the program dictates the type of every expression.

# Answer
> 2 votes
It depends on what the expression `e2` (and `e1`) is and what other type rules are in the type system.

Basically, the `Γ ⊢ e2 : T1` part of the type rule says:

> If there is a rule in the type system, which assigns the type `T1` to the expression `e2` in the environment `Γ`

If you can also find a rule that assigns the type `T1 -> T` to `e1`, then you can use the type assignment from the conclusion.

---
Tags: programming-languages, type-theory
---


# Question
Title: Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?
I am reading section 6.4 on Heapsort algorithm in CLRS, page 160.

```
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i to A.length downto 2
3   exchange A[i] with A[i]
4   A.heap-size = A.heap-size-1
5   MAX-HEAPIFY(A,1)

```

Why is the running time, according to the book is $\Theta (n\lg{n})$ rather than $\Theta (n^2\lg{n})$ ? `BUILD-MAX-HEAP(A)` takes $\Theta(n)$, `MAX-HEAPIFY(A,1)` takes $\Theta(\lg{n})$ and repeated $n-1$ times (line 3).

# Answer
Let us count operations line by line. You construct the heap in linear time. Then, you execute the loop and perform a logarithmic time operation $n-1$ times. Other operations take constant time. Hence, your running time is

$\qquad \begin{align} & n + (n-1) \log n + O(1) \\ &= n + n \log n - \log n + O(1) \\ &= \Theta(n \log n). \end{align}$

In other words, as $n$ grows the $n \log n$ term dominates. That is, the cost of building the heap on line 1 is negligible compared to the cost of executing the loop.
> 12 votes

# Answer
I had a different view altogether on this. I could not ignore the fact that in the MAX\_HEAPIFY step in the sort (which has a order of $\log n$, where $n$ is the heap size) receives a diminished heap size in each iteration. So to me the Summation looked more or less like $\sum\_{k=1}^{n-1}\log k\approx \log (n!)$. Now I know that $n! =\Theta(n^n)$ that way $\log(n!)=\Theta(n\log n)$, but it was never convincing.
> 0 votes

---
Tags: algorithms, algorithm-analysis, landau-notation, sorting
---


title: Is the given language decidable?

text:
# Question
Title: Is the given language decidable?
**L = { \< M \> | M is a turing machine and  }**

Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language .

Now, L(M) is reducible to decidable language.

**I think this language is not decidable**, as this language is non-trivial in the sense of rice theorem, as no recognizable language can be a part of L(M) and even this context free language belongs to L(M).

**Is my understanding right ?**

# Answer
> 2 votes
Yes, your understanding is right.

The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ (which it does, trivially) and prove that the set is nontrivial. So the whole exercise bogs down to: exhibit $M$ satisfying the reduction property, and $M′$ not satisfying it.

To prove/disprove reduction you may have to use the fact that the language $0^p1^{2p}$ is decidable, as you argued.

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


# Question
Title: The meaning of "at most" in the definition of space complexity of a Turing machine
From Ullman and Hopcroft's *Introduction to automata theory, languages, and computation* 1ed 1979

> Consider the off-line Turing machine M of Fig. 12.1. M has a read-only input tape with endmarkers and k semi-infinite storage tapes. If for every input word of length n, M scans **at most** S(n) cells on any storage tape, then M is said to be an S(n) space-bounded Turing machine, or of space complexity S(n). The language recognized by M is also said to be of space complexity S(n).
>
> ...
>
> The family of languages of space complexity S(n) is denoted by DSPACE(S(n));

1. Does "at most" mean taking the maximum or an upper bound?
2. By the definition, assume there is another function S'(n) so that S'(n)\>S(n).

* If an offline Turing machine M has space complexity S(n), does M also have space complexity S'(n)?
    * If a language is in DSPACE(S(n)), is it also in DSPACE(S'(n))?
3. Is it incorrect to say that **the** complexity of an offline Turing machine is S(n)? Instead should we say that an offline Turing machine has complexity S(n) or S'(n)?

Thanks.

# Answer
> 1. Does "at most" mean taking the maximum or an upper bound?

It means "at most". $x$ is at most $y$ iff $x\leq y$.

> 2. By the definition, assume there is another function $S'(n)$ so that $S'(n)\>S(n)$. If an offline Turing machine $M$ has space complexity $S(n)$, does $M$ also have space complexity $S'(n)$?

Yes. Let $\ell(x)$ be the number of tape cells used for input $x$. We have $\ell(x)\leq S(|x|)\leq S'(|x|)$, where the first inequality is by the fact that the machine uses space at most $S(|x|)$ and the second by the assumption about $S'$. Therefore, $M$ has space complexity $S'(n)$.

> If a language is in DSPACE(S(n)), is it also in DSPACE(S'(n))?

Yes. If you can decide it using at most some amount of space, you can also decide it using some bigger amount of space.

> 3. Is it incorrect to say that **the** complexity of an offline Turing machine is $S(n)$? Instead should we say that an offline Turing machine has complexity $S(n)$ or $S'(n)$?

It's a little loose to say that **the** complexity is $S(n)$, since "the" suggests a unique thing, whereas, as you've observed, a language actually has infinitely many space complexities. But people say it all the time, so don't worry about it.
> 3 votes

# Answer
The purpose of including the phrase 'at most' in the definition is to account for the fact that Turing machines often rescan one or more cells as they run, but a cell scanned more than once only counts as one cell for purposes of counting total used space. So the answer to (1) above is that S(n) is an upper bound on the total number of scanned cells (which can only be achieved in practice by machines which never rescan any cells). That 'looseness' is helpful if one cannot figure out precisely how cells are re-used -- simply assume they never are, and analyze accordingly.

And I would say that the phrase 'THE complexity is S(n)' should be reserved for when we can show that S(n) is the -smallest- function (in the big-O sense) that successfully measures the machine's complexity \[i.e if S'(n) is a 'smaller' function than S(n), then the machine must take more than S'(n) space on one or inputs, but never more than S(n) space\].
> 0 votes

---
Tags: complexity-theory
---


title: Lamport's Bakery algorithm

text:
# Question
Title: Lamport's Bakery algorithm
I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 to that and give that number to itself. The thread with the lowest number can enter the critical zone and if two or more threads have the lowest number then the thread with the lowest process id will be allowed to enter the critical area. When a thread exits the critical area then it put it's number to 0, meaning it's not interested in going inside the critical area. First when it picks a number higher than 0 it is interested going inside the critical area.

Now here is what I don't understand:

1. If a thread wants to get into the critical area it picks a number, but what if it changes its mind while it's waiting in line? does it then change its number to 0 or does it go through the critical area anyway when it is its turn?
2. In Lamport's bakery algorithm there is a Boolean value of "true" or "false". If a thread wants to enter it sets the Boolean value to true, but what is that Boolean value used for in the code? Because when a thread has been inside the critical area it changes its number to 0, so other threads in that way can see it's not interested in going inside the critical area, and if it decides it wants inside the critical area again, then it has to ask all the other threads what their number is and then add 1 to the maximum value which will be its number. So the true and false Boolean seems useless to me. Anybody understand why they are there?

# Answer
Let me try to help you with.

1) The problem here is that you are missing the big picture. Lamport's Bakery Algorithm (LBA) is just a deadlock-free algorithm that is used for mutual exclusion, so inside a bigger software. One typical way to use it is this (Java-like example):

```
mutex.lock();
try {
    CS(); // critical section
} finally {
    mutex.unlock(); // mutex has to be released also in case of error
}

```

For the way LBA is designed it does not allow a thread to "change idea" while waiting (there is no timeout notion in the algorithm): once a thread has called lock() it has to wait until lock() returns (possibly waiting all the other threads' unlock()). This does not mean that a thread is forced to enter in the CS once the lock is acquired. One thread could call lock(), wait until it returns and check if it is still required to run the CS. See below:

```
mutex.lock();
try {
    if(!tooMuchTimeHasPassed()) {  // is it still meaningful to enter CS?
        CS(); // critical section
    }
} finally {
    mutex.unlock(); // mutex has to be released also in any case
}

```

The example allow this scenario: one thread acquires the lock, notices that running CS is useless and stops by releasing the lock.

2) The boolean value, as you can see here, is not used to notify other threads about the fact that you have a certain priority or that you are inside the CS: it is only used to say to the other threads that you are still choosing a number. How can some threads decide which of them has the highest priority if some threads have not picked a number yet? In order to acquire the lock one thread A must ensure he has a priority higher then all the others (the outer for loop). If A discovers that another thread B is still searching for a number (the max() operation is not atomic and may require a lot of time) then it waits for B to pick a number and later checks who can go first.

Hope it helped!
> 2 votes

# Answer
**To answer your first point (1.)**

Yes. By clearing your ticket back to zero, you are forfeiting the lock. That means, obviously, that you cannot enter the critical section and do anything there. You have to return with some error code such as *"interrupted"* or *"timed out"*.

If your algorithm may timeout, or fail in some way, while calculating the `Number[j] = 1 + max(Number)` value, make sure to also set the Boolean value back to false: `Entering[j] = false`. Not doing so will block the lock mechanism otherwise. (Why would that happen? I implemented `snaplock` which allows me to obtain locks between any number of computers, at times the calculation of the ticket number fails and I have to make sure the `Entering[j]` value is set back to false.)

**To answer your second point (2.)**

The Boolean value is used to properly handle the calculation of `max(id1, id2, id3, ...)`, because while you are calculating a ticket, the `while()` loop cannot be sure that your state is going to be properly defined so it has to skip over you or wait for you (the Wikipedia implementation waits).

The algorithm from Wikipedia shows that the `for()` loop sits there if someone is currently *entering*. This is because testing `Number[j]`, while it is being calculated, is not going to be viewed correctly.

*Why is that you might ask?*

If thread A enters, it will run the first 3 lines of code to determine the largest `Number`. While A does that, B enters and starts determining its own largest `Number`. Once A has its `Number`, it enters the `for()` loop, at that moment, B is in an unstable state until `Entering[B] = false`. You cannot be sure whether `Number[B]` is going to be:

1. zero,
2. a larger `Number` than `Number[A]`, or
3. a smaller `Number` than `Number[A]`

And that choice is crucial to the algorithm.

```
  Entering[i] = true;
  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  Entering[i] = false;

  for (integer j = 1; j <= NUM_THREADS; j++) {
      // Wait until thread j receives its number:
      while (Entering[j]) { /* nothing */ }

      // Wait until all threads with smaller numbers or with the same
      // number, but with higher priority, finish their work:
      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
  }

```

Reading the Wikipedia page (link above) may enlighten you further on the question as they describe the algorithm with different words than mine.
> 0 votes

---
Tags: algorithms, distributed-systems, concurrency, mutual-exclusion
---


# Question
Title: In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree?
Recently, I am reading the book \[1\]. I am trying to solve the following problem:

> **1.2 Pigeons and holes.** Properly speaking, we should call our representation of Königsberg a *multigraph*, since some pairs of vertices are connected to each other by more than one edge. A *simple* graph is one in which there are no multiple edges, and no self-loops.
>
> Show that in any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree. Hint: if $n$ pigeons try to nest in $n - 1$ holes, at least one hole will contain more than one pigeon. This simple but important observation is called the *pigeonhole principle*.

The following is my attempt to solve the problem: Let $G$ be a finite simple graph that has $N\_V$ vertices and $N\_E$ edges. Because each edge connects two vertices, the number of total degrees is $2 N\_E$. Let $d\_i$ be the degree of the $i$th vertex for $i = 1, 2, ..., N\_V$, then $$\sum\_{i = 1}^{N\_V} d\_i = 2 N\_E. \tag{1}$$ On the other hand, we know $$0 \leq d\_i \leq N\_V - 1. \tag{2}$$ When $d\_i = 0$, it means that the $i$th vertex does not connect with any other vertices. A vertex can connect with at most $N\_V - 1$ vertices.

Then I don't know how to continue. Could any one please tell me the correct solution? Thanks in advance.

Note: It is not my homework. I am just interested in solving the problem.

# Reference:

\[1\] C. Moore and S. Mertens, *The Nature of Computation*, Oxford University Press, 2015.

# Answer
This one is a bit tricky! Here is the idea. We would like to use the pigeonhole principle. However, there are $n$ vertices and $n$ possible degrees $0,\ldots,n-1$, so the pigeonhole principle allows the situation in which each degree appears exactly once. We can flatly rule it out for values of $n$ which are of the form $4m+2$ or $4m+3$ using the handshake lemma, which states that the sum of the degrees is even, but what about the general case?

It turns out that to solve the general case we don't even need the handshake lemma. The following observation suffices (and explains why we need $n\>1$):

> If $n \> 1$ then a graph cannot contain both a node of degree $0$ and a node of degree $n-1$.
> 4 votes

---
Tags: graphs
---


# Question
Title: Does expressive power belong to semantics of a programming language?
* A programming language can be studied from different aspects: syntax, semantics, and pragmatics.

Does the expressive power of a programming language belong to the semantics of a programming language?
* What does the expressive power of a programming language include? For example, is its expressive power all about Turing-completeness of the programming language?

Thanks.

# Answer
In a nutshell, the "expressive power" of a programming language, defined as the breadth of ideas that can be directly represented and communicated in it, is an issue that belongs to the semantic level.

In principle, the behavior of a program written in any language - that can be formally studied - is completely describable at the syntactic level, so you could say that any language that is Turing-complete is also equivalent in "expressive power" (in this wider sense).

This approach is not very practical, though. Very quickly, *meaning* becomes an important conceptual metaphor that allows us to think about programs and languages in a powerful way, and there's even an entire discipline dedicated just to this endeavor.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Measuring Fitness in Genetic Programming Functionology
I recently begun working on a genetic algorithm to solve for patterns in data. More specifically, it solves for functions given a sample of ins and outs. So a possible solution would be X+2 = Y. The problem is scoring.

I began by trying to use the distance between the result and the expected result as a way of measuring fitness. The problem is the difference is not a reflection of the distance from a correct solution.

**So the question**: Given a random set of values, is it possible to measure how many operations(+,-,/,\*) it would take to get to an certain number without using brute force. And of course, if so how?

**EDIT** The random set will always contain {0,1,2}.

# Answer
I don't know how to solve your original problem, but I can describe how to solve a simpler version of it. Given numbers $a\_1,\dots,a\_n$ and a target $y$, if you only allow operations +,-, you can count how many operations it will take to reach $y$.

In particular, this amounts to asking for integers $x\_1,\dots,x\_n$ such that

$$a\_1 x\_1 + \dots + a\_n x\_n = y,$$

while minimizing $|x\_1| + \dots + |x\_n|$.

This can be solved using integer linear programming. Introduce variables $w\_1,\dots,w\_n$ and the constraints $w\_i \ge 0$ and $-w\_i \le x\_i \le w\_i$ as well as

$$a\_1 x\_1 + \dots + a\_n x\_n = y,$$

and then minimize the objective function $w\_1 + \dots + w\_n$.

While integer linear programming is NP-hard in the worst case, when the numbers aren't too large, I expect that this will yield an efficient solution.

Introducing the \*,/ operators makes your problem much harder.

To deal with your full problem, you might consider using the A\* algorithm. For instance, you might build a heuristic function that estimates the distance to the target by using integer linear programming to get an overestimate of the distance to the target (you know that the distance using +,-,\*,/ operators will be at most the distance using +,- operators, and the latter you can compute efficiently using ILP). I don't know for sure whether this will work well or not, but it's something you could try.
> 2 votes

---
Tags: genetic-algorithms
---


# Question
Title: Proving the regularity of a certain language
I've been fumbling around with this problem for the last hour, and I'm incredibly stumped.

Let $A = \\{\\; 0^ku0^k \mid k ≥ 1 \text{ and }u ∈ Σ^\*\\;\\}$. Show that $A$ is regular.

The language obviously satisfies the Pumping Lemma, but that is not conclusive for regularity. How on earth do I prove that this language is regular? I'm aware of all the normal methods (closed-under, etc), but I cannot for the life of me figure out the appropriate condition to continue.

# Answer
> 14 votes
It is a trick question. You can find a simpler form to describe the language.

# Answer
> 10 votes
The language can be re-written as $A=\\{0u0 \mid u\in \Sigma^\*\\}$.

The basic idea is that no matter what the value of $k$ is, it all gets "absorbed" into $u$ which is the complete language $\Sigma^\*$.

# Answer
> 8 votes
If it were this language:

$B = \\{\\; 0^k1u10^k \mid k ≥ 1 \text{ and }u ∈ Σ^\*\\;\\}$

you'd be in trouble. $B$ is *not* regular.

The key problem is that when trying to recognise strings from $B$, you need to "remember" an unbounded amount of information from the initial string of $0$s (how many there were), because you need to distinguish between the strings like $0^k1...10^k$ and the ones like $0^k1...10^j$ (where $j≠k$). Regular expressions (or DFAs) are unable to express this sort of "unbounded memory".

$A$ *looks* like it has the same problem, but actually there's no need to tell the "balanced" and "unbalanced" cases apart. For any string $0^ku0^j$ (whether or not $j$ and $k$ are equal, but both are at least 1), you can *also* write it as $0v0$, where $v=0^{k-1}u0^{j-1}$. Such a string also meets the rule for $A$'s strings (by choosing $k=1$ and $u=v$), and so it didn't actually matter that the leading and trailing $0$s were balanced after all.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Determining a minimal-state regular language $A$ such that $A \cap B = C$ given regular languages $B$ and $C$
Suppose I have a regular language $B$ and a regular language $C$ such that $C \subseteq B$.

How do I find a regular language $A$ such that $A \cap B = C$, where $A$ is represented by a DFA with as few states as possible?

I don't really know where to start looking for research on this, so even pointers to some work in this area would be appreciated.

The motivating case for this general question is building state machines to recognize certain regular expressions within UTF-8 streams, where I can rely on the UTF-8 stream being well-formed. (Or rather, my engine need not return correct values for malformed UTF-8 streams)

# Answer
> 5 votes
This question is essentially answered here. You are asking for the smallest DFA such that its language contains all words from $C \cap B$ and no words from $C \setminus B$. This called a *minimal separating* DFA (for $C \cap B$ and $C \setminus B$) in answer number one of the linked other question, where also a link to a paper with an algorithm is given. The other answer in that thread gives a reference to a paper showing that the problem is at least NP-hard. Since the size of the separating automaton is bounded (by the product of the DFA sizes for $B$ and $C$), the (decision version of the) problem is NP-complete.

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


# Question
Title: Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC
Consider an equation of the form:

$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$

where A-F are integer coefficients (binary quadratic Diophantine equation). I consider here the most general form, so assume all coefficients are non-zero.

Is there an ***efficient*** algorithm which can compute integer solutions for this type of equation?

# Answer
> 2 votes
Yes, such algorithms exist, i.e., if only BDQE has integer solutions, then those solutions can be found computationally, however - in exponential time. There is no polynomial time algorithm to tackle it in the general form (at least on a classical, non-quantum computer).

There's more information in Jeff Lagarias's slides for his talk Complexity of Diophantine Equations.

---
Tags: time-complexity
---


# Question
Title: $\{a^n b^n\} \cap \{a^*b^*\}$ regular or not?
I have been asked a very interesting question in preparation for my exam coming up. The question is as follows:

Is $L=\\{a^n b^n : n \geq 0\\} \cap \\{a^\*b^\*\\}$ regular or not?

Assume $L$ is regular. Then, $L^c$ should be regular as well. Thus, $L^c = \\{a^n b^n : n \lt 0\\} = \\{\\}$, so if I compliment the compliment, I should get $L = U$ (the universal set). So, then $L=\\{a^n b^n : n \geq 0\\} \cap \\{a^\*b^\*\\} \neq U$, because $L$ does not contain words of the form $baba$, or $baaaababa$, etc. Therefore the language is not regular.

Is this an acceptable answer for the upcoming exam? Does this persuade anyone?

# Answer
The complement of $\\{a^nb^n \mid n \geq 0\\}$ is not $\\{a^nb^n \mid n \< 0\\}$. And the complement of the complement should always equal the original set. The rest of your argument falls apart here.

As an example, `abb` is a string that is not $a^n b^n$, thus it should be in the complement of L.

---

To hint at an answer, is there any string $a^nb^n$ that is not $a^\*b^\*$? What does this say about the intersection of the two?
> 5 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Simplest combination of logic gates to produce a given set of outputs
Given a truth table for a truth function that takes *n* inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?

A few rules for specificity:

* Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
* The "simplest" solution is the one which uses the fewest logic gates
* The output of a logic gate may either be the output, or it may be an input to exactly *one* other logic gate.

Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?

# Answer
> 2 votes
This problem is discussed in Circuit Minimization Problem, by V. Kabanets and J.-Y. Cai.

Obviously the decision version is in NP (does there exists a circuit of size $\le k$ which agrees with the given truth table), since you could provide the circuit $\mathcal{C}$ and verify that $\forall x\in\left\\{0,1\right\\}^n : \mathcal{C}(x)=f(x)$. This can be done in polynomial time (relative to the input's size), since the size of the truth table is $2^n$.

It's an open question how hard the problem is. The above paper shows that any proof that this problem is in $P$, or any proof that it is $NP$-complete, would extend our current knowledge and imply a solution to long-standing open problems in complexity theory.

If the Circuit Minimization Problem is in $P$, then it is shown that $BPP=ZPP$ (so for now, showing your problem is in $P$ is open).

Since this is believed to happen anyway (under the assumption that $P=BPP$), they give more consequences which are less likely. For example, it is enough to show $2^n/n$ circuit lower bound for the class $E$ to obtain a $2^{c\cdot n}$ lower bound (If high circuit complexity functions exist in $E$, then very high circuit complexity functions exist too). They also show how to factor Blum integers efficiently on average (Which, they say, is the strongest evidence for the fact that this problem lies outside of $P$).

If the Circuit Minimization Problem is $NP$-hard (under what they call a "natural reduction", where the reduction's output size depends only on the input's size and not structure) then $BPP\subseteq SUBEXP$ and $BPP=P$ unless the exponential time hypothesis fails.

# Answer
> -1 votes
This is the (optimization version of) the problem of circuit minimization for Boolean functions ; it is known to be $\Sigma^p\_2$-complete, so it resides at the second level of the polynomial-time hierarchy. In other words, this problem is *hard*. See http://users.cms.caltech.edu/~umans/papers/BU07.pdf for more details.

---
Tags: algorithms, complexity-theory, logic, boolean-algebra
---


# Question
Title: How to understand these exposure algorithm rules for System F sub?
The book "Types and Programming Languages" said System F sub type checking introduce exposure typing rules alongside algorithmic typing and sub-typing rules.

```
       exposure algorithm

       X<:T ∈ Γ        Γ |- T ⇑ T'
       --------------------------- (XA-PROMOTE)
               Γ |- X ⇑ T'

        T is not a type variable
       --------------------------- (XA-other)
               Γ |- T ⇑ T

```

The first one seems simple, but the second rule seems bit wrong to me. "T is not a type variable", which "T" it is referring to?

Does "Γ |- T ⇑ T" mean left and right hand side of "⇑" are same types?

For example, with the type checking

```
          " Γ |- sone: SPos"

```

where

```
          sone= λ A <: Top.
                 λ B <: A.
                  λ C <: A.
                   λ m : A->B.
                    λ n : C. m n.

          and

          SPos= All A <: Top. All B<: A. All C<: A. (A-> B) -> (C-> A).

```

After applying "TA\_TABS" and "TA\_ABS" rules

```
 {A <: Top, B<: A, C<: A, m : A->B, n : C } |- m n :B
-----------------------------------------------------------TA-APP
 {...} |- :- m:T1   ,  {...}|-T1 ⇑ (T11->B)  ,  {...}|-n:T2  , {...}|-T2<:T11

 {...}|-n:T2    we know  T2=C
 then
 {...}|-C<:T11  we get T11=top

 then put it in place

 {...} |- :- m:T1   , {...}|-T1 ⇑ (top->B)
 ------------------------------------------

which rule applies now?

I believe from

{...}|-T1 ⇑ (top->B)

we should get "T1=A->B" , but how?

both (XA-PROMOTE) and (XA-other) seems cannot be applied.

please help!

```

# Answer
> 4 votes
In a typing rule (and more generally any deduction rule), all metavariables¹ are universally quantified. That is, the rule can be applied for any instantiation that is syntactically correct. For example, (XA-PROMOTE) means “for any context $\Gamma$, for any type variable $X$, for any type $T$, for any type $T'$, if $\Gamma$ contains $X \<: T$ and the typing judgement $\Gamma \vdash T \Uparrow T'$ is true, then the typing judgement $\Gamma \vdash X \Uparrow T'$ is true”. The rule (XA-other) states “for any type $T$, for any context $\Gamma$, if $T$ is not a type variable then the typing judgement $T \vdash T \Uparrow T$ is true”.

The question “which $T$ is it referring to?” is not meaningful: the rule does not refer to a particular $T$. On the contrary, the rule applies to any $T$; the conclusion applies to any $T$ that matches the premise.

In $\Gamma \vdash T \Uparrow T$, the left- and right-hand sides of $\Uparrow$ are the same type. The rule states that the relation $\Uparrow$ in any given context $\Gamma$ is symmetric on the subset of the set of all types that consists of the types that are not type variables. Some examples of typing judgements that can be derived by this rule are: $$ \vdash \mathsf{Top} \Uparrow \mathsf{Top} \\ X \<: \mathsf{Top}, Y \<: X \vdash X \rightarrow \mathsf{Top} \Uparrow X \rightarrow \mathsf{Top} \\ X \<: \mathsf{Top}, Y \<: X \vdash (\forall Z \<: Y, X \rightarrow Z) \Uparrow (\forall Z \<: Y, X \rightarrow Z) \\ $$

I don't remember Pierce's presentation and I don't have the book here, but I think the reason XA-other has the premise that $T$ must not be a type variable is to make these rules syntax-directed: there's another rule that allows deriving judgement $\Gamma \vdash T \uparrow T$ when $T$ is a type variable. This is a presentation choice.

¹ <sub> A *metavariable* is a variable that is used to describe the system, for example $X$, $T$, $T'$ and $\Gamma$ in the rule (XA-PROMOTE). We use the term *metavariable* to distinguish this concept from a *variable*, which refers whatever the language calls a variable. </sub>

---
Tags: type-theory, type-checking, types-and-programming-languages
---


# Question
Title: Is it or is it not correct to say that the expected runtime of an algorithm is its runtime on the expected problem size? Why?
Say we have an algorithm that takes time $T$ to process a problem of size $n$.

Is $\langle T(n)\rangle $ = $T(\langle n\rangle)$?

# Answer
In general, it does not hold that $\DeclareMathOperator{\EE}{\mathbb{E}}\EE\[f(X)\] = f(\EE\[X\])$. For example, suppose that $X=0$ with probability $1/2$ and $X=1$ with probability $1/2$, and that $f(x) = x^2$. Then $\EE\[f(X)\] = 1/2$ whereas $f(\EE\[X\]) = 1/4$.
> 2 votes

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


title: Dovetailing in Turing Machines?

text:
# Question
Title: Dovetailing in Turing Machines?
I was going through TM here and encountered a term "**Dovetailing**".

**What is exactly the dovetailing in Turing Machines?**

Can anyone mind to provide a good explaination with some examples?

# Answer
Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.

Why is dovetailing useful? Here is one example. Suppose that $L$ is recursively enumerable (there is a Turing machine enumerating all words in $L$) and also co-recursively enumerable (there is a Turing machine enumerating all words not in $L$). Then $L$ is recursive (there is a Turing machine that, given a word $x$, decides whether $x \in L$). For the proof, we simulate the first two machines in parallel, wait for $x$ to appear, and the answer accordingly.

How is dovetailing implemented? Typically, we alternately simulate one step of each machine.

In contrast to your operating system, in theoretical computer science we are sometimes interested in dovetailing *infinitely* many computations. This can be accomplished by running the first machine for one step, then the first two machines for one step, then the first three machines, and so on. Perhaps you will encounter examples illustrating why this is useful later in your academic life.
> 12 votes

---
Tags: turing-machines, undecidability, semi-decidability
---


# Question
Title: Concatenating polyhedra at their region of contact
Given two polyhedra(with triangulated faces), P1 and P2. I want to create a polyhedron P, which is the result of joining the two at their region of contact. With *join* I do not mean union but physically, it is more like welding P1 and P2, so if there is say a cylinder(P1) and a cube(P2) aligned on same axis with P1 partially out of P2, union operation will result in disappearance of the part of cylinder inside the cuboid but I want to preserve that region in P. In other words, P1 and P2 should be concatenated at their region of contact.

I would like to know if there is any *practical* algorithm for this? I think that it is more like computing overlay of P1 and P2 but I do not find any approach for the same in 3D.

# Answer
> 1 votes
I was recently referred to an article 'Mesh arrangements for solid geometry' by Qingnan Zhou et. al. \[pdf\] and the corresponding code by Dr. Campen which exactly solves this problem.

This algorithm inserts new vertices and edges in the region of intersection between $P1$ and $P2$ thereby a generating new polyhedron $P$ and evaluates boolean operators on $P$ by selecting/rejecting vertices and edges depending on the operator. For my problem, $P$ forms the solution.

However, out of curiosity I would like to know if anyone has an alternative to this approach.

**Update:** I have tested the tool referred above against my original problem, it successfully prevents self-intersection by inserting new vertices and edges at the region of contact between $P1$ and $P2$.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Why would total comparison of functions solve the Halting problem?
> Why would total comparison of procedures solve the Halting problem?

I've read that if all procedures could be represented syntactical e.g. in Scheme, then they could be compared structurally using the predicate `=`, and this would in turn solve the Halting problem.

Having read the ordinary proof why the Halting problem cannot be solved by any Turing machine (by reaching a contradition if such algorithm exists), I still cannot see why the comparison of functions would imply the contrary.

# Answer
The specific representation of functions doesn't really matter here, so we'll talk about the usual encoding of Turing machines. We denote the encoding of a machine $M$ by $\langle M \rangle$ (if this bothers you, think of it as the scheme code of the function).

Nothing prevents you from comparing two machines syntactically (by comparing the encoding/scheme code as strings). The problem arises when you claim that you have an operator "$=$" which checks whether the functions are equivalent semantically, i.e. give the same result for each input. In the language of Turing machines, this means you can decide the following language:

$L = \left\\{\left(\langle M\_1\rangle ,\langle M\_2 \rangle \right) | L(M\_1) = L(M\_2)\right\\}$

The halting problem can be reduced to the above. Given $\langle M\rangle$ and $w\in \Sigma^\*$, ask whether the machine $M\_w$ which disregards the input, simulates $M$ on $w$, and accepts, computes the constant $1$ function. Thus, $L$ is not decidable. In fact, it is $\Pi\_2^0$ complete, so $L$ is not even semi decidable.
> 5 votes

---
Tags: complexity-theory, halting-problem
---


# Question
Title: How to use Type application Rule to get a desired type
In type application Rule :

$$\dfrac{ \Gamma \vdash t\_1 : T\_{11} \to T\_{12} \qquad \Gamma \vdash t\_2 : T\_{11}} { \Gamma \vdash t\_1 \ t\_2 : T\_{12} } \textsf{ (T-App)}$$

if we deriving the term from bottom up, how to get $T\_{11}$ from ? How you'll know what is $T\_{11}$? Its not clear to me.

# Answer
> 9 votes
You can look at this rule in two ways:

As a *checking* rule, it says that, to verify that $t\_1 t\_2$ has type $T\_{12}$, we check that there exists some $T\_{11}$ such that $t\_1 : T\_{11} \to T\_{12}$, and we check that $t\_2 : T\_{11}$. If these checks hold, then the typing of the application must hold.

As an *inference* rule, it says that to infer the type of $t\_1 t\_2$, we infer the type of $t\_1$ and verify that it has the form $T\_{11} \to T\_{12}$ for some types $T\_{11}, T\_{12}$, infer the type for $t\_2$ and check that it is equal to $T\_{11}$. If these checks hold, then we return $T\_{12}$ as the type of the application.

So for knowing what $T\_{11}$ is, it depends on what you're doing. If you're doing checking, then usually it is a type that has already been given to you. If you're doing inference, then you infer the type of the function, and inspect that type to verify that it's an arrow type, and can be broken into its parts. $T\_{11}$ is one of these parts you break it into.

There's nothing saying you need to get $T\_{11}$ only from the function's type. You could alternately infer it from the type of the argument, and then verify that it matched the function type.

# Answer
> 5 votes
The rules state what kinds of proofs are valid. No one ever promised it would always be easy to find a valid proof for any particular term of your choice. There may be multiple rules that *could* be used at any point; it's not the type rules' job to do anything about that.

Instead, that's the role of a type-checking algorithm. Depending on the type system, there may or may not be an efficient algorithm to find a valid proof (one that's deemed valid according to the rules), i.e., a valid sequence of rules to apply that proves the desired result.

# Answer
> 0 votes
You can't derive bottom up. It doesn't matter what T11 is. It's just some type; the rule holds no matter what it is. More precisely: if this is supposed to be a rule in a sequent calculus then I believe it is incomplete. The bottom sequent should have type annotations for every term. So you already have t11. Which suggests that jmite's answer is not quite right, insofar as it says we need to find some t11. But we dont, we're already given it in the premises, and the rule carries it over to the conclusion. If all you have is a,b:T, and you do not already know the types of a and b, you cannot infer them.

# Answer
> 0 votes
T11 is can be find on derivation on the right branch of that rule for type checking. On the right hand branch, you will eventually have

```
    {x:T}|-x:T11

```

something like this. You apply "T\_VAR" rule and get "T11=T". since above statement says, variable "x is type of T in syntax" there T should be equal to T11.

try some type checking, denote T11, then you see eventually T11 equals some type which is already known.

---
Tags: type-theory
---


# Question
Title: Using B trees to search inside dynamically changing array segments
Let $A$ be a sorted array. Suppose that this array is huge and can only be stored in a disk. In the I/O model and algorithms built in this model, every time we access the disk we spend an I/O and we get $B$ elements to the RAM. Since accessing the disk is much more expensive than accessing the main memory, we assume that what ever operations we perform in main memory, they come for free. So even if you scan 1 million times the entire RAM, in the I/O model, this would cost $O(1)$ I/Os, and that's the only thing we care about.

Suppose that you now receive queries in the form $\[l,r, key\]$ where $l$ and $r$ are indices which define a continguous chunk of the array $A$, and $key$ is a value that you want to search inside this chunk. So you want to know whether the key is somewhere in that chunk or not.

If you expect many queries to come, and we will make this assumption as well, it might be worth spending $O(\frac{N}{B})$ I/Os to build a B tree on top of the array $A$, and use the $B$ tree for your searches. Since the height of a B tree is $O(\log\_{B}(N))$ each search will require $O(\log\_{B}(N))$ I/Os.

However I was wondering, if the size of the chunk defined by the query is $n$, is it possible to use the same B tree to achieve $O(\log\_{B}(n))$ I/Os? Because if we always start searching from the root of the B tree, we would first have to find where our chunk is, and then search inside the chunk, which is why the total number of I/Os would be $O(\log\_{B}(N))$.

My idea would be to spend 1 I/O to access the leaf block in the B tree containing element $A\[l\]$, 1 I/O to access the leaf block in the B tree containing element $A\[r\]$, and then spend $O(\log\_{B}(n))$ I/Os to find the least common ancestor block in the B tree of these two leaf blocks. Then since we found the least common ancestor block in the B tree, we can start searching from there, spending in total $2 + O(\log\_{B}(n)) + \log\_{B}(n)$ I/Os.

Unfortunately I am very novice in the I/O model and this approach sounds too good to be correct. Is it really that easy for this problem or am I missing something?

# Answer
I assume the "B-tree" in your post is in fact a "B+-tree" and array $\small A$ is stored in an increasing manner. Your idea is almost good and needs some small revision.

* You need to test whether $\small A\[l\] \leq key$ and $\small A\[r\] \geq key$. If $\small A\[l\] = key$ or $\small A\[r\] = key$, it is done.
* If it is found that $\small A\[l\] \< key$ and $\small A\[r\] \> key$, find the LCA of the blocks containing $\small A\[l\]$ and $\small A\[r\]$, as you have done. The height of the LCA is of $\small \mathcal{O}(\log\_B(n))$.
* If $\small A\[l\] \> key$ or $\small A\[r\] \< key$, then obviously $\small key$ does not exist in $\small \[l, r\]$.

**Why testing $\small A\[l\] \leq key$ and $\small A\[r\] \geq key$ is important?**

The LCA block may contain entries that direct to blocks outside $\small \[l, r\]$. If you start from the LCA, you may find a $\small key$ even if $\small key$ does not exist in $\small \[l, r\]$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, data-structures, search-algorithms
---


# Question
Title: Algorithm for checking unambiguity in the derivation of a string
It is known that given a Context Free Grammar $G$, checking that it is ambiguous or not is undecidable. But, if I have a string $s \in L(G)$, does there exist an algorithm to check whether $s$ particularly can be derived unambiguously in $G$?

# Answer
gnasher's comment more or less answers this. A sketch of an algorithm would be:

* enumerate all derivations of the grammar that do not generate strings longer than $s$. This can be done, because CFGs do not have deleting rules (or if yours do, they can be converted for example to Chomsky Normal Form)
* check how many of the strings generated are equal to $s$.

This takes a long time, of course. But I doubt that there is a fundamentally better way.
> 3 votes

# Answer
The CYK algorithm can be modified in a straightforward way to solve this problem. In particular, the problem is not only decidable -- there is a reasonably efficient algorithm to solve it.

The standard CYK algorithm uses dynamic programming to compute $P\[i,j,X\]$, a boolean that indicates whether $s\[i..j\]$ is a member of $L(X)$, for each pair of indices $i,j$ and each non-terminal $X$. I suggest you also compute $Q\[i,j,X\]$, which indicates whether $s\[i..j\]$ can be derived unambiguously from $X$. It is easy to adjust the recursion to compute both $P$ and $Q$ simultaneously.

This achieves a $O(n^3 \cdot |G|)$ running time, i.e., polynomial time.

You can probably do the same with Earley parsing or any method of GLR parsing.
> 0 votes

---
Tags: context-free
---