# Question
Title: Is it a problem to be a programmer with no knowledge about computational complexity?
I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess.

Then I made the most trivial thing that came into my mind and then showed to my lecturer. After a brief observation, he perceived that the runtime complexity of my solution was inviable and shown something more efficient. And there is a tradition of programmers who have no idea on what is computational complexity (I was one of those), so is it a problem if a programmer has no idea on what is computational complexity?

# Answer
> 42 votes
Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it.

In your specific case, your example of finding connected components might have worked for graphs of up to say $100$ nodes. However, if you tried a graph with $100.000$ nodes then your lecturer's algorithm would probably have managed that in 1 second, while your algorithm would have (depending on how bad the complexity was) taken 1 hour, 1 day, or maybe even 1 eternity.

A somewhat common mistake students make in our algorithms course is to iterate over an array like this:

```
while array not empty
    examine first element of array
    remove first element from array

```

This might not be the most beautiful code but in a complicated program something like this might show up without the programmer being aware of it. Now, what is the problem with this program?

Suppose we run it on a data set of $100.000$ elements. Compared to the following program, the former program will run $50.000$ slower.

```
while array not empty
    examine last element of array
    remove last element from array

```

I hope you agree that having the knowledge to make your program run $50.000$ times faster is probably an important thing for a programmer. Understanding the difference between the two programs requires some basic knowledge about complexity theory and some knowledge about the particulars of the language you are programming in.

In my pseudocode language, "removing an element from an array" shifts all the elements to the right of the element being removed one position from the left. This makes removing the last element an $O(1)$ operation since in order to do that we only need to interact with 1 element. Removing the first element is $O(n)$ since in order to remove the first element we need to shift all the other $n-1$ elements one position to the left as well.

A very basic exercise in complexity is to prove that the first program will do $\frac{1}{2}n^2$ operations while the second program uses only $n$ operations. If you plug in $n=100.000$ you will see one program is drastically more efficient than the other.

This is just a toy example but it already requires a basic understanding of complexity to tell the difference between the two programs, and if you are actually trying to debug/optimize a more complicated program that has this mistake it takes an even greater understanding to find out where the bug is. Because a mistake like removing an element from an array in this fashion can be hidden very well by abstractions in the code.

Having a good understanding of complexity also helps when comparing two approaches to solve a problem. Suppose you had come up with two different approaches to solving the connected components problem on your own: in order to decide between them it would be very useful if you could (quickly) estimate their complexity and pick the better one.

# Answer
> 27 votes
This is a rebuttal of Tom van der Zanden's answer, which states that this is a must.

The thing is, most times, 50.000 times slower is not relevant (unless you work at Google of course).

If the operation you do takes a microsecond or if your N is never above a certain threshold (A high portion of the coding done nowadays) it will NEVER matter. In those cases thinking about computational complexity will only make you waste time (and most likely money).

Computational complexity is a tool to understand why something might be slow or scale badly, and how to improve it, but most of the time is complete overkill.

I've been a professional programmer for more than five years now and I've never found the need to think about computational complexity when looping inside a loop O(M * N) because always the operation is really fast or M and N are so small.

There are far more important, generally used, and harder things to understand for anyone doing programming jobs (threading and profiling are good examples in the performance area).

Of course, there are some things that you will never be able to do without understanding computational complexity (for example: finding anagrams on a dictionary), but most of the time you don't need it.

# Answer
> 14 votes
I've been developing software for about thirty years, working both as a contractor and employee, and I've been pretty successful at it. My first language was BASIC, but I quickly taught myself machine language to get decent speed out of my underpowered box. I have spent a lot of time in profilers over the years and have learned a lot about producing fast, memory efficient optimized code.

Regardless to say, I'm self taught. I never encountered the O notation until I started interviewing a few years ago. It's never come up in my professional work EXCEPT during interviews. So I've had to learn the basics just to handle that question in interviews.

I feel like the jazz musician who can't read sheet music. I can still play just fine. I know about hashtables (heck, I invented hashtables before I learned that they had already been invented) and other important data structures, and I might even know some tricks that they don't teach in school. But I think the truth is that if you want to succeed in this profession, you will either need to go indie or learn the answers to the questions that they will ask during interviews.

Incidentally, I most recently interviewed for a front end web developer role. They asked me a question where the answer required both a knowledge of computational complexity and logarithms. I managed to remember enough math from twenty years ago to answer it more or less correctly, but it was a bit jarring. I've never had to use logarithms in any front end development.

Good luck to you!

# Answer
> 9 votes
The question is quite subjective, so I think the answer is *it depends*.

It doesn't matter that much if you work with small amounts of data. In these cases, it is usually fine to use whatever e.g. the standard library of your language offers.

However, when you deal with large amounts of data, or for some other reason you insist that your program is fast, then you must understand computational complexity. If you don't, how do you know how a problem should be solved, or how quickly it is even possible to solve it? But understanding just theory is not enough to be a really good programmer. To produce extremely fast code, I believe, you also have to understand how e.g. your machine works (caches, memory layout, the instruction set), and what your compiler does (compilers do their best, but are not perfect).

In short, I think understanding complexity clearly makes you a better programmer.

# Answer
> 4 votes
It depends, but not on amount of data you're working with, but on kind of work you do, programs you develop.

Let's call programmer that doesn't know about conceptual complexity noobish programmer.

The noobish programmer can do:

* develop big data databases - he doesn't have to know how it works inside, all he has to know are rules about developing databases. He knows things like: what should be indexed,... where it is better to make redundancy in data, where it is not...
* make games - he just has to study how some game engine works and follow its paradigms, games and computer graphics are quite a big data problems. Consider 1920\*1080\*32bit = cca 7.9MB for single picture/frame... @60 FPS it's at least 475MB/s. Consider, that just one unnecessary copy of fullscreen picture would waste around 500MB memory throughput per second. But, he doesn't need to care about that, because he only uses engine!

The noobish programmer shouldn't do:

* develop very frequently used complex programs no matter of size of data it's working with,... for example, small data won't cause noticeable impact of improper solution during development, because it will be slower than compilation time, etc. So, 0.5sec for one simple program ain't that much from noobish programmer perspective, Well, consider server server, that runs this program twenty times per second. It would require 10cores to be able to sustain that load!
* develop programs for embedded devices. Embedded devices work with small data, but they need to be as efficient as it's possible, because redundant operations make unnecessary power consuption

So, noobish programmer is fine, when you want just use technologies. So, when it comes to development of new solutions, custom technologies, etc. Then it's better to hire not noobish programmer.

However, if company doesn't develop new technologies, just uses already made ones. It would be waste of talent to hire skilled and talented programmer. The same applies, if you don't want to work on new technologies and you're fine putting customers ideas into designs and programs using already made frameworks, then it's waste of your time, to learn something you won't ever need, except if it's your hobby and you like logical challenges.

# Answer
> 4 votes
It is certainly a problem if someone who is developing significant algorithms does not understand algorithm complexity. Users of an algorithm generally rely on a good quality of implementation that has good performance characteristics. While complexity is not the only contributor to performance characteristics of an algorithm, it is a significant one. Someone who does not understand algorithm complexity is less likely to develop algorithms with useful performance characteristics.

It is less of a problem for users of an algorithm, assuming the algorithms available are of good quality. This is true for developers who use languages that have a significant, well-specified, standard library - they just need to know how to pick an algorithm that meets there needs. The problem comes in where their are multiple algorithms of some type (say, sorting) available within a library, because complexity is often one of the criteria for picking between. A developer who does not understand complexity then cannot understand the basis for picking an effective algorithm for their task at hand.

Then there are developers who focus on (for want of a better description) non-algorithmic concerns. For example, they may focus on developing intuitive user interfaces. Such developers will often not need to worry about algorithm complexity although, again, they may rely on libraries or other code being developed to a high quality.

# Answer
> 3 votes
I'm somewhat hesitant to write an answer here but since I found myself nitpicking on several others' \[some of my comments got moved to chat\], here's how I see it...

There are levels/degrees of knowledge to a lot of things in computing (and by this term I mean roughly the union of computer science with information technology). Computation complexity surely is a vast field (Do you know what OptP is? Or what the Abiteboul-Vianu theorem says?) and also admits a lot of depth: most people with a CS degree can't produce the expert proofs that go into research publications in computational complexity.

The level of knowledge and skill/competence required in such matters depends a lot on what one works on. Completely clueless O($n^2$) sorting is sometimes said to be a major cause of slow programs<sup>\[citation needed\]</sup>, but a 2003 SIGCSE paper noted "Insertion sort is used to sort small (sub) arrays in standard Java and C++ libraries." On the flip side, premature optimization coming from someone who doesn't understand what *asymptotic* means (computational complexity being such a measure) is sometimes a problem in programming practice. However, the point of knowing at least when computational complexity matters is why you need to have some clue about it, at least at an undergraduate level.

I would honestly dare compare the situation of knowing when to apply computational complexity concepts (and knowing when you can safely ignore them) with the somewhat common practice (outside of Java world) of implementing some performance-sensitive code in C and the performance-insensitive stuff in Python etc. (As an aside, this was called in a Julia talk the "standard compromise".) Knowing when you don't have to think about performance saves you programming time, which is a fairly valuable commodity too.

And one more point is that knowing computational complexity won't automatically make you good at optimizing programs; you need to understand more architecture-related stuff like cache locality, \[sometimes\] pipelining, and nowadays parallel/multi-core programming too; the latter has both its own complexity theory and practical considerations as well; a taste of the latter from a 2013 SOSP paper "Every locking scheme has its fifteen minutes of fame. None of the nine locking schemes we consider consistently outperforms any other one, on all target architectures or workloads. Strictly speaking, to seek optimality, a lock algorithm should thus be selected based on the hardware platform and the expected workload."

# Answer
> -1 votes
If you don't know big-O you should learn it. It's not hard, and it's really useful. Start with searching and sorting.

I do notice that a lot of answers and comments recommend *profiling*, and they almost always mean *use a profiling tool*.

The trouble is, profiling tools are all over the map in terms of how effective they are for finding what you need to speed up. *Here I've listed and explained the misconceptions that profilers suffer from.*

The result is that programs, if they are larger than an academic exercise, can contain *sleeping giants*, that even the best automatic profiler cannot expose. *This post* shows a few examples of how performance problems can hide from profilers.

But they cannot hide from *this technique.*

---
Tags: algorithms, algorithm-analysis, education, applied-theory
---


# Question
Title: Does every infinite recursive language contain an infinite regular subset?
My intuition is telling me that this is not the case. But I am having trouble formulating a proof for this.How do I prove it ?

# Answer
> 2 votes
Take the language $L= \\{a^{2^p}\mid p\geq 1\\}$.

> It is easy to show with the pumping lemma that it contains no infinite regular subset.

Try to prove it is a counter-example.

> The reason is that the pumping lemma requires, for infinite regular sets, that some infinite sequence of strings in the language grows linearly in size. But the language $L$ contains no such sequence because its strings grow exponentially. Hence it cannot contain an infinite regular subset.

---
Tags: computability, regular-languages
---


# Question
Title: Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant
Given a directed weighted graph, is there an algorithm that does the following:

* Removes as many edges possible.
* Reduces as many weights as possible.

Given the constraint that the net weight of all edges connected to the vertex (sum of incoming edge weights minus sum of outgoing edge weights) remains the same and every edge weight remains non-negative.

Examples:

The graph "A -10-\> B -10-\> C" could be reduced to "A-10-\>C" since vertex B has net zero weights (10 incoming and 10 outgoing)

The graph "A -10-\> B -3-\> A" could be reduced to "A-7-\>B".

Thanks.

# Answer
The second objective is just a simple circulation problem http://en.wikipedia.org/wiki/Circulation\_problem as the maximum circulation gives the highest reduction in weight. This problem is basically equivalent to max flow for which efficient algorithms are well known.

Not so sure about trading of the first and second objective. You might achieve something like this by modelling it as a min concave-cost network flow problem with capacities, e.g. by some cost function that is nearly flat at arc saturation, such that it favours saturating arcs once they are close, but this is NP-hard: http://link.springer.com/article/10.1007/BF02283688

Maybe there is a more efficient way depending on what you are trying to achieve, but the constraint that net edge weights remain the same indicate that you are looking for some network flow type algorithm.

Do you have an application for this in mind?
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Order a list of edges to make the the complexity of searching for an edge O(lg E)
I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related (connected).

Now, at a certain point, there's a question:

> How can you organize an edge list to make searching for a particular edge take O(lg E) time?

I was thinking to the trivial solution of sorting, but it is not so easy to sort a list of edges. For example, let the following be our initial list of edges:

```
[[3, 2], [1, 2], [1, 3]]

```

Now, if we try to sort it by using the first vertex, we obtain:

```
[[1, 3], [1, 2], [3, 2]]

```

I am not visualizing well if this search would be `O(lg E)`, where `E` is the number of edges.

Could you please explain how could we organize the edges in order to have a *edge searching algorithm* with a time complexity of `O(lg E)`? And why it should be `O(lg E)`?

# Answer
*Any* total order will do; more is not needed for sorting and searching with binary search in a sorted list.

The lexicographic order would be a canonical choice for sorting tuples.

If your elements are (unordered) sets (e.g. edges of undirected graphs) you can sort them before comparing by the order on tuples as well.
> 3 votes

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


# Question
Title: Deterministic processing on probabilistic input
I've designed an algorithm, is which responsible to process some samples from normal distribution under aegis of some deterministic steps. In other words, the algorithm generate unique response to a unique set of the random set of input.

Now I am prone to plan a title for the corresponding paper and there is a noticeable ambiguity regarding the manner by which the algorithm could be addressed...

It is neither non-deterministic nor randomized and probabilistic. What is this algorithm type? Should I name that as typical deterministic?!...

Edit: This algorithm is supposed to be fed by a number of agent coordinates (are which random normal-driven integer numbers). It should colonize the agents into groups in a specialized manner. Thus, the input is probabilistic but both the algorithm process and the output are considerably deterministic.

The current idea regarding the title is:

`Optimal Communication of Agents by the Probabilistic Colonization of the Robot Swarm`

But that `Probabilistic` word does not sound so deserving...

# Answer
> 0 votes
How about ...

```
Optimal Communication of Agents under Randomized Spatial Distribution

```

---
Tags: algorithms, terminology
---


# Question
Title: What are the main ideas used in a Fenwick tree?
While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called **Fenwick tree** (a.k.a **binary indexed tree**) was at the heart of this technique. So in an effort to understand Fenwick trees, I researched all online sources in vain because reading them in details is a pain!

No one seems to be able to explain the main concepts behind this data structure in a concise and clear way. Can anyone please give a high level exposition of the main ideas related to Fenwick trees without going into unnecessary details?

# Answer
A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array.

Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on top of the array. Furthermore, label all the left edges in this tree with a "0" and all the right edges with a "1". We get something like this:

This is the so called Fenwick tree (or binary indexed tree). As can be seen, all the leaf nodes are indexed by a 4-digit binary number from 0000 till 1111 (left to right). Don't worry about this indexing for the time being. Now suppose that every leaf node contains the numeric value of its mapped array element and that every non-leaf node contains the sum of its two children. This means that the root node of the tree will contain the sum of the whole array. Also the left(right) child of the root will contain the sum of the left(right) half of the array and so on and so forth.

Up till this point we haven't really done anything special apart from storing partial sums. What we really want to do is to use these partial sums to compute cumulative sums in the array. We can do this for example by carefully selecting some nodes and returning their sum. This poses the question: *Is there a strategic way to mark some nodes of the index tree that allows efficient cumulative sum calculations?* It turns out that there is and this is the main idea behind Fenwick trees.

Before describing this marking, we first elaborate on the concept of uniform arcs. A uniform arc in a binary indexed tree is a directed path from any leaf to any other leaf situated to its left such that the labels on this path have the form: "00...011...1" (read from left to right). We can also assume the existence of a uniform arc from every leaf node to itself (with a length of 0). For example, the uniform arc connecting the fourth leaf to the first has a label of "0011". See the following figure for some illustrative examples of uniform arcs.

**Now comes the crucial idea of Fenwick trees**. The marking that allows us efficient computation of cumulative sums is obtained by coloring the middle node of the largest uniform arc emanating from every leaf node. This marking is illustrated in the following figure:

The nodes coloured in red are the so called *responsibility* nodes. This is due to the fact that each red node is *responsible* for maintaining the sum of values of all leaf nodes beneath it. Note that there are 16 responsible nodes and the whole tree can be implemented using a single array of the same size of the original array and here is when the binary indexing becomes handy. The yellow nodes are not needed and are used here only for pedagogical purposes. Note that all non-leaf responsible nodes have indexes length \< 4 bits. We can restore the 4 bit length by padding successive "1"s to the right of the corresponding index. After applying the padding, the indexes of all responsible nodes fit nicely into a single array. See the following figure:

All we have to do now is figure out a way to compute (or update) the cumulative sum for every leaf node as follows:

**A**\- To read the cumulative sum at a leaf, we first prepend a "0" and append a "1" to its index then we use the "flipping" technique as follows. Starting from the right most bit we first note the first "1" to "0" transition then flip all "1"s to "0"s one at a time. The sum of the found responsible nodes is then returned. The following examples illustrate this technique: (*note: node "" is the root*)

*leaf "1010", becomes "010101" =\> responsible nodes: {"1010", "100", "0"}*

*leaf "1011", becomes "010111" =\> responsible nodes: {"10", "0"}*

*leaf "0111", becomes "001111" =\> responsible nodes: {"0"}*

*leaf "1111", becomes "011111" =\> responsible nodes: {""}*

**B**\- To update a value, trace all responsible nodes from the leaf to the root and update them accordingly. The tracing is done by prepending and appending a "0" to the index of the leaf and then successively noting all "0" to "0" and "1" to "0" transitions in the resulting index starting from rightmost bit. The following examples illustrate this technique: (*note: node "" is the root*)

*leaf "1000", becomes "010000" =\> responsible nodes: {"1000", "100", "10", ""}*

*leaf "1111", becomes "011110" =\> responsible nodes: {""}*

*leaf "0100", becomes "001000" =\> responsible nodes: {"0100", "010", "0", ""}*

*leaf "0000", becomes "000000" =\> responsible nodes: {"0000", "000", "00", "0", ""}*

You can verify the above examples by direct visual inspection of the third figure. A detailed explanation of Fenwick trees can be found at BIT: What is the intuition behind a binary indexed tree and how was it thought about? and https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/. Hopefully by now reading the mentioned sources will be much easier.
> 22 votes

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


# Question
Title: Advantage of byte addressable memory over word addressable memory
What is the reason that almost all computers (besides some DSPs) use byte addressable memory? With byte addressable memory and a 32 bit address you can have 4GB while with word addressable memory you can have 4GB * wordsize. Are single bytes used that much that you can't use routines that filter out single bytes from a word because there is an advantage of having more memory?

# Answer
> 4 votes
For 32-bit addresses and 32-bit words, the benefit of being able to address a larger memory is relatively minor, adding only two generations of Moore's Law to the lifetime of the architecture. Compared to a transition from 16-bit addresses to 32-bit addresses (sixteen generations), this is a relatively minor extension.

For the CDC 6600, having 18-bit addresses and 60-bit words and targeting technical computing, the use of word addressing made more sense. Technical computing emphasizes performance over price (so wasting some memory was less important than fast memory access) and has less use for finer-grained accesses.

Many 16-bit DSPs use word addressing. This more significantly increases addressing range than for a 32-bit processor and the benefit of finer-grained access is much smaller for the targeted workloads.

For business and general purpose computing, system cost is a more significant consideration and data element size is more variable. The cost of memory provides an incentive to use smaller data elements. Not supporting direct access to such elements not only increases instruction count (which somewhat directly relates to performance) but code size (which increases memory pressure).

Having a single flat address space simplifies software development. If sub-word addressing requires special handling, this has an effect similar to segmentation where some accesses have to be treated differently than others. Even if such is handled by the compiler, such makes performance less transparent (as well as making compiler development more complex, reducing the resources spent on other features).

Word addressing also requires the use of *atomic* read-modify-write operation to support simple sub-word stores. (The atomicity requirement may only be with respect to interrupts, but this does add complexity.) A further complication occurs for memory-mapped I/O, where read-modify-write cannot be used since accesses can have side effects. While this issue can be managed by having regions that translate word addresses to specific sub-word granularities, such is an awkward solution. This was how the Alpha 21064 handled byte I/O addresses without byte loads or stores (also 2-byte I/O accesses). (Some 32-bit microcontrollers use bit-banding regions, where an address region uses bit-granular addressing.)

A large part of the reason that byte-addressing (with 8-bit bytes) is popular *is*, in fact, historical. Not only did IBM's S/360 have a strong influence on the de facto standardization on byte addressing and 8-bit bytes, but the IBM's choice of Intel's 8088 further solidified this trend. With early microprocessors, 8-bit processors would naturally use 8-bit word addressing, maximizing the use of existing software (often written in assembly language) would increase the incentive for using byte-addressed memory. (Note: Reasonable alternatives to the 8086/8088 also used byte-addressing, though IBM's requiring a cheaper and more compatible 8-bit interface may also have been a significant factor. I am not suggesting that word-addressing was only avoided because of the choice of Intel's 8088 for the IBM PC.)

As noted, compatibility with existing I/O interfaces can be particularly problematic.

As Richard L. Sites notes in "Alpha AXP Architecture" (PDF) perhaps more significant benefits of word addressing are avoiding extra shifting of the load result and supporting moderate overhead ECC in a fast writeback cache. Traditional SECDED ECC would require 7 extra bits over 32-bit granules (22% overhead) versus 4 extra bits over 8-bit granules (50% overhead). (Sites' argument about library writers being lazy and using simplistic byte-based string operations is less convincing; forcing extra effort may encourage a moderate addition of effort for higher performance code but it may simply annoy programmers.)

A similar issue applies to unaligned memory accesses. Architecturally disallowing unaligned accesses can simplify hardware but makes some not uncommon operations significantly more complex. Even with MIPS-like load/store unaligned, software must special case unaligned accesses since such instructions increase dynamic instruction count and should not be used if the accesses are known to be aligned. Support for unaligned memory accesses can be particularly beneficial for short vector operations where the individual elements might be properly aligned (e.g., 16-bit elements aligned at 16-bit granularity) but the start of the vector might not be aligned. (This is effectively the same problem as string handling.)

---

It might be worth noting that *software-based* pointer compression has some popularity. On a 64-bit architecture, software can choose to use simple 32-bit pointers or even exploit structure alignment to store larger pointers in 32-bit memory locations. (A similar software technique uses bits that can be ignored based on known alignment to store metadata. SPARC even architecturally defined such use by supporting tagged arithmetic operations. Storing metadata in the more significant bits of a pointer is also a common technique. ARM's AArch64 allows the most significant 8 bits to be used for metadata without requiring extra masking, and Azul Systems' Vega processor used the most significant 16 bits for metadata.) In pointer-intensive programs, the reduction in cache misses may justify the additional left shift when loading a pointer. Obviously, this technique has limited use since it requires knowing that the data set will fit within the smaller region and that the objects will be aligned. These factors are easier to enforce at the application or even virtual machine software level than at the architectural/hardware level, especially for a merchant processor (a processor sold to various system vendors).

(Using segments identified by the least significant two bits might be better than word addressing. Like word addressing, such would extend the reach of 32-bit pointers by exploiting structure alignment but it would allow further reach by changing segment addresses. This would require special instructions to distinguish dynamic segment specification (which masks out two bits) and static segment specification (which allows byte granular addresses). HP PA-RISC used a *similar* segmentation system, but used the most significant two bits to identify the segment — allowing simple byte-granular addressing in dynamically specified segments within a GiWord region but making the 64-bit transition messier than if the least significant bits were used. This choice may hint at how important byte granular addressing is for general purpose computing.)

# Answer
> 1 votes
Historically, computers addressed memory as bytes, and since then computers have had to be compatible with older ones. So this has passed down through the generations of computers, however modern CPUs can address words as well as bytes from the RAM, but addressability-wise, a 32 bit address can select any of the 4\*1024\*1024 bytes in the 4GB memory range. Using words instead would be more confusing to program too, and sometimes the CPU needs single bytes - having to input a whole word and filter that byte out would take precious CPU time. But, if the CPU needs to, it can address a word - it just gets two bytes back. I hope this helps somewhat.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Extension of Tarski's result on the decidability of reals
Due to Tarski's result, it is well-known that the first-order theory of reals $(\mathbb{R},+,\cdot,\<,=,0,1)$ is decidable. I am working on a paper where I need an extension of this result. More precisely, I would like to consider formulas that involve rational functions, rational coefficients, minima and maxima. Trigonometric functions or exponential functions, instead, are excluded.

While this seems to me to be a straightforward consequence of Tarski's result (essentially, rewrite any formula with the above functions into one with polynomials only; e.g., rewrite $\sqrt\[2\]{x}$ into $\exists z (z^2 = x)$; for two polynomials $p$ and $q$, rewrite the formula $p / q \leq 1$ into $p \leq q$ and so on).

To my surprise, I could not find any paper that formally establishes this.

Before providing the proof on my own, I wanted to ask around whether someone is aware of a paper that establishes this result.

# Answer
> 3 votes
I doubt there's a proof you can cite, since the result is obvious. The "features" you're adding are first-order definable, and first-order logic is closed under substitution.

---
Tags: decision-problem, first-order-logic
---


# Question
Title: Proving a language isn't regular using the pumping lemma
Let the language $$ L = \\{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \\} $$

> Show that $L$ isn't regular using the pumping-lemma.

Let's assume by contradiction that $L$ is regular, then there's a constant $p$ which answers the conditions of the lemma for every $w\in L$.

Let's observe at the word $w = a^pb^p$. Obviously, $w\in L$ and since $\left|w\right| \gt p$, we may use the pumping lemma for $w$.

$w = xyz$. Let's assume that $xy$ has the form $a^k$ or $b^k$. WLOG, $xy \in a^p$. Then, $w = a^ka^jb^p$ where $k + j = p$.

Let's observe at $w' = xy^0z = xz = a^kb^p$. By the pumping lemma, $w' \in L$.

But, it is **uncertain** that $k$ and $p$ has the same quotient.

**Question:** Is that enough to claim that it is uncertain? If not, what should I do instead?

# Answer
> 1 votes
This problem can be tidied up using the floor function, where $\lfloor x\rfloor$ denotes the smallest integer greater than or equal to $x$. For example, we have $\lfloor 3.14\rfloor=3$ and $\lfloor 6\rfloor=6$. In particular, if $n$ and $m$ are positive integers, then $\lfloor n/m\rfloor$ is the quotient you obtain when you divide $n$ by $m$ (i.e., throw away the remainder).

Then, for integers $q\>0$ you have a family of languages $$ L\_q=\\{a^nb^m\mid \lfloor n/m\rfloor=q\\} $$ We'll generalize your proof slightly to show that $L\_q$ is not regular for any integer $q\>0$. For a fixed $q$ assume that $L\_q$ was regular. Then the Pumping Lemma implies that there is an integer $p$ such that any string $w\in L\_q$ of length greater than or equal to $p$ can be written as $w=xyz$ with

1. $xy^iz\in L\_q$ for any $i\ge 0$
2. $|y|\>0$
3. $|xy|\le p$

Choose the string $a^{pq}b^p\in L\_q$ and write $a^{pq}b^p=xyz$ as above. Then, as you noted, we may say $xy=a^k$ without loss of generality (the case where $xy=b^k$ will be handled in the same way as below and the case where $xy=a^ib^j$ will produce an immediate contradiction for $xy^2z$, since it will be the wrong form to be in $L\_q$).

Now we know that $y=a^j$ for some $0\<j\le p$. The first inequality comes from condition (2) of the PL and the second comes from condition (3). As you noted, we'll then have $$ xyz=(a^r)(a^j)(a^{pq-r-j}b^p) $$ and so $$ xz=(a^r)(a^{pq-r-j}b^p)=a^{pq-j}b^p $$ Now we'll show that $xz\notin L\_q$, contradicting condition (1) of the PL. If, to the contrary, $xz\in L\_q$, we'd have to have $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=q $$ but $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=\left\lfloor q-\frac{j}{p}\right\rfloor $$ But now we came to the heart of your question: since $0\<j\le p$ by (2) and (3) we'll have $q-1\le q-(j/p) \< q$, so $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=q-1 $$ and so $xz\notin L\_q$, giving us the contradiction we needed, completing the proof that $L\_q$ is not regular for any $q\>0$.

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


# Question
Title: Is there a more intuitive proof of the halting problem's undecidability than diagonalization?
I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.

While the proof is *convincing* (I understand each step of it), it is not *intuitive* to me in the sense that I don't see how someone would derive it, starting from the problem alone.

In the book, the proof goes like this: "suppose $M\_H$ solves the halting problem on an input $M;x$, that is, decides whether Turing machine $M$ halts for input $x$. Construct a Turing machine $D$ that takes a Turing machine $M$ as input, runs $M\_H(M;M)$ and reverses the output." It then goes on to show that $D(D)$ cannot produce a satisfactory output.

It is the seemingly arbitrary construction of $D$, particularly the idea of feeding $M$ to itself, and then $D$ to itself, that I would like to have an intuition for. What led people to define those constructs and steps in the first place?

Does anyone have an explanation on how someone would reason their way into the diagonalization argument (or some other proof), if they did not know that type of argument to start with?

**Addendum given the first round of answers:**

So the first answers point out that proving the undecidability of the halting problem was something based on Cantor and Russell's previous work and development of the diagonalization problem, and that starting "from scratch" would simply mean having to rediscover that argument.

Fair enough. However, even if we accept the diagonalization argument as a well-understood given, I still find there is an "intuition gap" from it to the halting problem. Cantor's proof of the real numbers uncountability I actually find fairly intuitive; Russell's paradox even more so.

What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

**P.S.**

@babou summarized what was troubling me better than myself: "The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat."

# Answer
> 21 votes
In your edit, you write:

> What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

A common "popular" summarization of Turing's proof goes something like this:

> "If we had a machine $M\_H$ that could decide whether another Turing machine halts or not, we could use this to construct another machine $D$ that, given a Turing machine $M$, would halt if and only if $M$ did *not* halt. But then we could pass $D$ as input to itself, and thus obtain a paradox: this machine would halt if and only if it did not halt!"

Now, it's easy to see that the summarization above glosses over an important detail — the halting of the Turing machine $M$ also depends on its input, which we have not specified! But this issue can be fixed easily enough: we just need to have $D$ pick some suitable input $x\_M$ for each input machine $M$, before passing them both to $M\_H$.

What's a suitable choice for $x\_M$, given that we ultimately want to derive a contradiction? Well, a natural choice is suggested directly by the "handwavy" proof above, where we ultimately obtain the contradiction by running the machine $D$ on itself.

Thus, for the behavior of $D$ to really be paradoxical in this case, i.e. when invoked as $D(D)$, what we want is for the halting of $D(M)$ to depend on the behavior of $M$ *when invoked as $M(M)$*. This way, we'll obtain the contradiction we want by setting $M = D$.

Mind you, this is not the only choice; we could also have derived the same contradiction by, say, constructing a machine $D'$ such that $D'(M)$ halts if and only if $M(D')$ (rather than $M(M)$) does not halt. But, whereas it's clear that the machine $D$ can easily duplicate its input before passing it to $M\_H$, it's not quite so immediately obvious how to construct a machine $D'$ that would invoke $M\_H$ with its own code as the input. Thus, using this $D'$ instead of $D$ would needlessly complicate the proof, and make it less intuitive.

# Answer
> 19 votes
It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context.

Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (which uses a diagonalisation argument) and Gödel's first incompleteness theorem (which uses a diagonalisation argument). In fact, Gödel's result is deeply related to the proof of undecidability of the Halting Problem (and hence the negative answer to Hilbert's Entscheidungsproblem).

So my contention is that your question is in a sense badly founded and that you *can't* reach the Halting Problem without going past the rest (or something remarkably similar) first. While we show these things to students without going through the history, if you were a working mathematician it seems unlikely that you go from nothing to Turing Machines without anything in between - the whole point of them was to formalise computation, a problem many people had been working on for decades at that point.

Cantor didn't even use diagonalisation in his first proof of the uncountability of the reals, if we take publication dates as an approximation of when he thought of the idea (not always a reliable thing), it took him about 17 years from already knowing that the reals were uncountable, to working out the diagonalisation argument.

In reference to the "self-application" in the proof that you mention, this is also an integral part of Russell's paradox (which entirely depends upon self-reference), and Gödel's first incompleteness theorem is like the high-powered version of Russell's paradox. The proof of the undecidability of the Halting Problem is so heavily informed by Gödel's work that it's hard to imagine getting there without it, hence the idea of "self-application" is already part of the background knowledge you need to get to the Halting Problem. Similarly, Gödel's work is a reworking of Russell's paradox, so you don't get there without the other (note that Russell was not the first to observe a paradox like this, so prototypes of the diagonalisation argument has been around in formal logic since about 600BCE). Both Turing and Gödel's work (the bits we're talking about here that is) can be viewed as increasingly powerful demonstrations of the problems with self-reference, and how it is embedding in mathematics. So once again, it's very difficult to suggest that these ideas at the level Turing was dealing with them came *a priori*, they were the culmination of millennia's work in parts of philosophy, mathematics and logic.

This self-reference is also part of Cantor's argument, it just isn't presented in such an unnatural language as Turing's more fundamentally logical work. Cantor's diagonalisation can be rephrased as a selection of elements from the power set of a set (essentially part of Cantor's Theorem). If we consider the set of (positive) reals as subsets of the naturals (note we don't really need the digits to be ordered for this to work, it just makes a simpler presentation) and claim there is a surjection from the naturals to the reals, then we can produce an element of the power set (i.e. a real) that is not in the image of the surjection (and hence derive a contradiction) by take this element to be the set of naturals who are not in their own image under the surjection. Once we phrase it this way, it's much easier to see that Russell's paradox is really the naïve set theory version of the same idea.

# Answer
> 13 votes
# Self application is not a necessary ingredient of the proof

## In a nutshell

**If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine $L$ with a halting behavior (halting characteristic function) that cannot be the halting behavior of any Turing machine.**

The paradox built on the self applied function $D$ (called $L$ in this answer - sorry about notation inconsistencies) is not a necessary ingredient of the proof, but a device usable with the construction of one specific contradiction, hiding what seems to be the "real purpose" of the construction. That is probably why it is not intuitive.

It seems more direct to show that there is only a denumerable number of halting behaviors (no more than Turing machines), that can be defined as characteristic halting functions associated with each Turing machine. One can define constructively a characteristic halting function not in the list, and build from it, and from a machine $H$ that solves the halting problem, a machine $L$ that has that new characteristic halting function. But since, by construction, it is not the characteristic halting function of a Turing machine, $L$ cannot be one. Since $L$ is built from $H$ using Turing machine building techniques, $H$ cannot be a Turing machine.

The self-application of $L$ to itself, used in many proofs, is a way to show the contradiction. But it works only when the impossible characteristic halting function is built from the diagonal of the list of Turing permitted characteristic halting functions, by flipping this diagonal (exchanging $0$ and $1$). But there are infinitely many other ways of building a new characteristic halting function. Then non-Turing-ness can no longer be evidenced with a liar paradox (at least not simply). The self-application construction is not intuitive because it is not essential, but it looks slick when pulled out of the magic hat.

Basically, $L$ is not a Turing machine because it is designed from the start to have a halting behavior that is not that of a Turing machine, and that can be shown more directly, hence more intuitively.

**Note**: It may be that, for any constructive choice of the impossible characteristic halting function, there is a computable reordering of the Turing machine enumeration such that it becomes the diagonal ( I do not know). But, imho, this does not change the fact that self-application is an indirect proof technique that is hiding a more intuitive and interesting fact.

# Detailed analysis of the proofs

I am not going to be historical (but thanks to those who are, I enjoy it), but I am only trying to work the intuitive side.

I think that the presentation given @vzn, which I did encounter a long time ago (I had forgotten), is actually rather intuitive, and even explains the name diagonalization. I am repeating it in details only because I feel @vzn did not emphasize enough its simplicity.

My purpose is to have an intuitive way to retrieve the proof, knowing that of Cantor. The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat.

The proof that I give is not exactly the same as in the question, but it is correct, as far as I can see. If I did not make a mistake, it is intuitive enough since I could retrieve it after more years than I care to count, working on very different issues.

## The case of the subsets of $\mathbb N$ (Cantor)

The proof of Cantor assumes (it is only an hypothesis) that there is an enumeration of the subsets of the integers, so that all such subset $S\_j$ can be described by its characteristic function $C\_j(i)$ which is $1$ if $i\in S\_j$ and is $0$ otherwise.

This may be seen as a table $T$, such that $T\[i,j\]=C\_j(i)$

Then, considering the diagonal, we build a characteristic function $D$ such that $D(i)=\overline{T\[i,i\]}$, i.e. it is identical to the diagonal of the table with every bit flipped to the other value.

There is nothing special about the diagonal, except that it is an easy way to get a characteristic function $D$ that is different from all others, and that is all we need.

Hence, the subset characterized by $D$ cannot be in the enumeration. Since that would be true of any enumeration, there cannot be an enumeration that enumerates all the subsets of $\mathbb N$.

This is admittedly, according to the initial question, fairly intuitive. Can we make the proof of the halting problem as intuitive?

## The case of the halting problem (Turing)

We assume we have an enumeration of Turing machines (which we know is possible). The halting behavior of a Turing machine $M\_j$ can be described by its characteristic halting function $H\_j(i)$ which is $1$ if $M\_j$ halts on input $i$ and is $0$ otherwise.

This may be seen as a table $T$, such that $T\[i,j\]=H\_j(i)$

Then, considering the diagonal, we build a characteristic halting function $D$ such that $D(i)=\overline{T\[i,i\]}$, i.e. it is identical to the diagonal of the table with every bit flipped to the other value.

There is nothing special about the diagonal, except that it is an easy way to get a characteristic halting function $D$ that is different from all others, and that is all we need (see note at the bottom).

Hence, the halting behavior characterized by $D$ cannot be that of a Turing machine in the enumeration. Since we enumerated them all, we conclude that there is no Turing machine with that behavior.

*No halting oracle so far, and no computability hypothesis*: We know nothing of the computability of $T$ and of the functions $H\_j$.

Now suppose we have a Turing machine $H$ that can solve the halting problem, such that $H(i,j)$ always halts with $H\_j(i)$ as result.

We want to prove that, given $H$, we can build a machine $L$ that has the characteristic halting function $D$. The machine $L$ is nearly identical to $H$, so that $L(i)$ mimics $H(i,i)$, except that whenever $H(i,i)$ is about to terminate with value $1$, $L(i)$ goes into an infinite loop and does not terminate.

It is quite clear that we can build such a machine $L$ if $H$ exists. Hence this machine should be in our initial *enumeration of **all** machines* (which we know is possible). But it cannot be since its halting behavior $D$ corresponds to none of the machines enumerated. Machine $L$ cannot exist, which implies that $H$ cannot exist.

I deliberately mimicked the first proof and went into tiny details

My feeling is that the steps come naturally in this way, especially when one considers Cantor's proof as reasonably intuitive.

One first enumerates the litigious constructs. Then one takes and modifies the diagonal as a convenient way of touching all of them to get an unaccounted for behaviour, then gets a contradiction by exhibiting an object that has the unaccounted for behaviour ... if some hypothesis were to be true: existence of the enumeration for Cantor, and existence of a computable halting oracle for Turing.

**Note:** To define the function $D$, we could replace the flipped diagonal by any other characteristic halting function, different from all the ones listed in $T$, that is computable (from the ones listed in $T$, for example) provided a halting oracle is available. Then the machine $L$ would have to be constructed accordingly, to have $D$ as characteristic halting function, and $L(i)$ would make use of the machine $H$, but not mimic so directly $H(i,i)$. The choice of the diagonal makes it much simpler.

## Comparison with the "other" proof

The function $L$ defined here is apparently the analog of the function $D$ in the proof described in the question.

We only build it in such a way that it has a characteristic halting function that corresponds to no Turing machine, and get directly a contradiction from that. This gives us the freedom of not using the diagonal (for what it is worth).

The idea of the "usual" proof seems to try to kill what I see as a dead fish. It says: let's assume that $L$ is one of the machines that were listed (i.e., all of them). Then it has an index $j\_L$ in that enumeration: $L=M\_{j\_L}$. Then if $L(j\_L)$ halts, we have $T\[j\_L,j\_L\]=H(j\_L,j\_L)=1$, so that $L(j\_L)$ will loop by construction. Conversely, if $L(j\_L)$ does not halt, then $T\[j\_L,j\_L\]=H(j\_L,j\_L)=0$ so that $L(j\_L)$ will halt by construction. Thus we have a contradiction. But the contradiction results from the way the characteristic halting function of $L$ was constructed, and it seems a lot simpler just to say that $L$ cannot be a Turing machine because it is constructed to have a characteristic halting function that is not that of a Turing machine.

A side-point is that this usual proof would be a lot more painful if we did not choose the diagonal, while the direct approach used above has no problem with it. Whether that can be useful, I do not know.

# Answer
> 8 votes
There is also a proof of this fact that uses a different paradox, Berry's paradox, which I heard from Ran Raz.

Suppose that the halting problem were computable. Let $B(n)$ be the smallest natural number that cannot be computed by a C program of length $n$. That is, if $S(n)$ is the set of natural numbers computed by C programs of length $n$, then $B(n)$ is the smallest natural number not in $S(n)$.

Consider the following program:

1. Go over all C programs of length at most $n$.
2. For each such program, check if it halts; if it does, add it to a list $L$.
3. Output the first natural number not in $L$.

This is a program for computing $B(n)$. How large is this program? Encoding $n$ takes $O(\log n)$ characters, and the rest of the program doesn't depend on $n$, so in total the length is $O(\log n)$, say at most $C\log n$. Choose $N$ so that $C\log N \leq N$. Then our program, whose length is at most $N$, computes $B(N)$, contradicting the definition of $B(N)$.

The same idea can be used to prove Gödel's incompleteness theorems, as shown by Kritchman and Raz.

# Answer
> 6 votes
There's a more general idea involved here called the "recursion theorem" that may be more intuitive: Turing machines can use their own description (and thus run themselves). More precisely, there is a theorem:

> For any Turing machine `T`, there is a Turing machine `R` that computes `R(x) = T(R;x)`.

If we had a Turing machine that could solve the halting problem, then using the idea described above, we can easily construct a variety of "liar" turing machines: e.g. in python-like notation,

```
def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

```

The more complicated argument is essentially just trying to do this directly without appealing to the recursion theorem. That is, it's repeating a recipe for constructing "self-referential" functions. e.g. given a Turing machine `T`, here is one such recipe for constructing an `R` satisfying

```
R(x) = T(R; x)

```

First, define

```
S(M; x) = T(M(M; -); x)

```

where by `M(M; -)`, what I really mean is that we compute (using the description of `M`) and plug in a description of a Turing machine that, on input `y`, evaluates `M(M; y)`.

Now, we observe that if we plug `S` into itself

```
S(S; x) = T(S(S; -); x)

```

we get the duplication we want. So if we set

```
R = S(S; -)

```

then we have

```
R(x) = T(R; x)

```

as desired.

# Answer
> 5 votes
the Turing proof is quite similar to Cantors proof that the cardinality of reals ("uncountable") is larger than the cardinality of the rationals ("countable") because they cannot be put into 1-1 correspondence but this is not noted/ emphasized in very many references (does anyone know any?). (iirc) a CS prof once showed this years ago in class (not sure where he got it himself). in Cantors proof one can imagine a grid with horizontal dimension the *n*th digit of the number and the vertical dimension the *n*th number of the set.

the Turing halting proof construction is quite similar except that the contents of the table are Halt/ Nonhalt for 1/ 0 instead, and the horizontal axis is *n*th input, and the vertical axis is *n*th computer program. in other words the combination of computer programs and inputs are countable but the infinite table/ array is uncountable based on a universal machine simulator construction that can "flip" a halting to a nonhalting case assuming a halting detector machine exists (hence *reductio ad absurdam*).

some evidence that Turing had Cantors construction partly in mind is that his same paper with the halting proof talks about computable numbers as (along the lines of) real numbers with computable digits.

# Answer
> 3 votes
At this point it is worth noting the work by Emil Post who is (justly) credited with being a co-discoverer of the basic results of computability, though sadly was published too late to be considered a co-discoverer of the solution to the Entscheidungsproblem. He certainly participated in the elaboration of the so-called Church-Turing thesis.

Post was motivated by very philosophical considerations, namely the *theoretical* limitations of the human ability to compute, or even get precise answers in a *consistent* manner. He devised a system, now called Post canonical systems, the details of which are unimportant, which he claimed could be used to solve *any problem which can be solved soely by manipulation of symbols*. Interestingly, he explicitly considered mental states to be part of the "memory" explicitly, so it is likely that he at least considered his model of computation to be a model of human thought in it's entirety.

The Entscheidungsproblem considers the possibility of using such a means of computation to say, determine the theoremhood of any proposition expressible in the system of the Principia Mathematica. But the PM was a system explicitly designed to be able to represent all of mathematical reasoning, and, by extension (at least at the time, when Logicism was still in vogue) all of human reasoning!

It's therefore very unsurprising then, to turn the attention of such a system to the Post canonical systems themselves, just as the human mind, via the works of Frege, Russel and logicians of the turn of the century had turned their attention to the reasoning faculty of the human mind itself.

So it is clear at this point, that self-reference, or the ability of systems to describe themselves, was a rather natural subject in the early 1930s. In fact, David Hilbert was hoping to "bootstrap" mathematical reasoning itself, by providing a formal description of all of human mathematics, which then could be mathematically proven to be consistent itself!

Once the step of using a formal system to reason about itself is obtained, it's a hop and a skip away from the usual self-referential paradoxes (which have a pretty old history).

Since all the statements in *Principia* are presumed to be "true" in some metaphysical sense, and the *Principia* can express

> program `p` returns result `true` on input `n`

if a program exists to decide all theorems in that system, it is quite simple to directly express the liar's paradox:

> this program always lies.

can be expressed by

> The program `p` always returns the opposite of what the principia mathematica say `p` will return.

The difficulty is building the program `p`. But at this point, it's rather natural to consider the more general sentence

> The program `p` always returns the opposite of what the PM say `q` will return.

for some arbitrary `q`. But it's easy to build `p(q)` for any given `q`! Just compute what PM predicts it will output, and return the opposite answer. We can't just replace `q` by `p` at this point though, since `p` takes `q` as input, and `q` does not (it takes no input). Let's change our sentence so that `p` *does* take input:

> The program `p` returns the opposite of what PM says `q(r)` will return.

Arg! But now `p` takes 2 pieces of input: `q` and `r`, whereas `q` only takes 1. But wait: we want `p` in both places anyways, so `r` is not a *new* piece of information, but just the same piece of data again, namely `q`! This is the critical observation.

So we finally get

> The program `p` returns the opposite of what PM says `q(q)` will return.

Let's forget about this silly "PM says" business, and we get

> The program `p(q)` returns the opposite of what `q(q)` will return.

This is a legitimate program *provided we have a program that always tells us what `q(q)` returns*. But now that we have our program `p(q)`, we can replace `q` by `p` and get our liar's paradox.

---
Tags: computability, proof-techniques, undecidability, halting-problem, intuition
---


# Question
Title: Is the minimal number of colors needed to color a graph some fixed number?
Consider to following decision problem:

> **Input**: Undirected graph $G=(V,E)$
>
> **Question**: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices aren't colored the same) **exactly** 2015?

Note that 2015 could be any fixed number. This number is not part of the input.

I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma \_{2} \cap \Pi \_{2}, \Sigma \_{2} \cup \Pi \_{2}$.

I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma \_{2} \cap \Pi {2}$ since we can think of it as

> **exists** $f$ some 2009-coloring function, **for-all** $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.

So by the above, it seems that the language is in $\sf \Sigma \_{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi \_{2}$, I think.

And maybe the there is some deterministic polynomial-time algorithm?

# Answer
The problem is always in $\Delta\_2 = \Sigma\_2 \cap \Pi\_2$, as you mention. For some values of 2015 it is easier: deciding whether a graph has chromatic number 3 is NP-complete, and deciding whether a graph has chromatic number 2 or 1 is in P (since you can check whether a graph is bipartite in polytime).

Since deciding whether a graph has chromatic number 3 is NP-hard, so is deciding whether it has chromatic number 2015, by reduction: add a clique of size 2012, and connect it to all vertices; this increases the chromatic number by exactly 2012. So there is no hope for a polynomial time algorithm.
> 3 votes

---
Tags: complexity-theory, graphs, time-complexity, complexity-classes
---


# Question
Title: TM recognizing $0^n1^n$ requires Ω(log n) space
I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space.

I believe this can be done using a *crossing sequence* argument. I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.

What I have tried is:

Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$. Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.

Let $C$ be the set of configurations of $M$ on $x$. That is, $C$ is the set of tuples of the form

(state, work tape head position, work tape contents).

Then $|C| \leq |Q\_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.

The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations occurring as the input head moves across that boundary. Each term of a crossing sequence can be any of the $|C|$ elements from $C$.

Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.

Therefore, number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.

The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.

# Answer
> 2 votes
As you correctly point out by counting configurations, it holds that $SPACE\[o(\log n)\]\subseteq TIME\[o(n)\]$.

There is a theorem stating that $TIME\[o(n\log n)\]=REG$. See e.g. here.

If, by contradiction, we had $\\{0^n1^n: n\in \mathbb{N}\\}\in SPACE\[o(\log n)\]$, it would then follow that $\\{0^n1^n: n\in \mathbb{N}\\}\in REG$, which is clearly false.

Thus, $\\{0^n1^n: n\in \mathbb{N}\\}$ cannot be solved in $SPACE\[o(\log n)\]$.

---
Tags: complexity-theory, context-free, space-complexity, lower-bounds
---


# Question
Title: Optimizing iteration over all permutations of a bit array
**edited for clarity:**

I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ which satisfy the condition $T(x) = true$. I also know that if $b$ is a binary subset of $a$ then $f(a) \> f(b)$ (e.g. $f(0b1101) \> f(0b1001)$. I have no such insight about $T$. Can I avoid iterating over candidates which are subsets of inputs which satisfy $T$?

My current solution is this: beginning with $x = 1^n$ and an empty array as a cache, iterate through the various permutations in order of descending population count. Test if the next input $x$ is a subset of any values in the cache. If it is not a subset and $T(x)=true$, then compute $f(x)$ and add $x$ to the cache of supersets.

However, this strategy must search through the cache on every iteration. Instead, I am imagining a tree which (for $n=5$) looks like $$0b11111$$ $$0b11110\qquad0b11101\qquad0b11011\qquad0b10111\qquad0b01111$$ $$...$$ The root node is $1^n$, and child nodes are created by changing a single $1$ to a $0$ so that all children are binary subsets of their parents. Iterating from the root node, when we reach a node $x$ for which $T$ is true, we could skip calculating $f$ or $T$ for all of its child nodes because they are binary subsets of $x$. Unfortunately, the tree as constructed has $n!$ nodes instead of $2^n$, and nodes begin to appear multiple times in each sub-tree, so pruning the tree is not so simple. Is there a way to realize this type of optimization?

# Answer
There's no possibility of an efficient algorithm here, unless you have more information about $T$. $T$ might only return true for one input and, in the worst case, you'd have to try all $2^n$ possibilities for that input before finding the right one. Or $T$ could return true iff its input contains $n/2$ $1$'s: there are exponentially many such strings and you'd have to try all of them to maximize $f$, since none of those strings is a binary subset of any of the others, so you have no information about the behaviour of $f$ on that set of strings.
> 2 votes

---
Tags: algorithms, optimization
---


# Question
Title: Who invented the state elimination algorithm for converting finite automata into regular expressions?
The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. However, I can't seem to find any references to who first invented this algorithm.

Does anyone know who invented the state elimination algorithm? Ideally, I'd like a reference to a specific paper or textbook.

Thanks!

# Answer
According to my information the technique is by J.A. Brzozowski and E.J. McCluskey. The method is described in Signal Flow Graph Techniques for Sequential Circuit State Diagrams, IEEE Transactions on Electronic Computers, 67 - 76, 1963. https://doi.org/10.1109/PGEC.1963.263416 (subscription needed)

> Abstract: This paper considers the application of signal flow graph techniques to the problem of characterizing sequential circuits by regular expressions. It is shown that the methods of signal flow graph theory, with the proper interpretation, apply to state diagrams of sequential circuits. *The use of these methods leads to a simple algorithm for obtaining a regular expression describing the behavior of a sequential circuit directly from its state diagram.*

(emphasis mine)

Curiously, I could only find the technique in the French edition of wikipedia: Méthode de Brzozowski et McCluskey
> 5 votes

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


title: Converting reality to Petri net

text:
# Question
Title: Converting reality to Petri net
I'm autistic and I think a bit differently. I have superior memory and visual thinking, but I have a problem with converting real thing to abstract. I'd like to model reality processes with Petri nets. But... when I think of cooking meal or using a coffee vendor machine, I see in my head vegetables, kitchen utensils, cooking books and coffee machines I have seen in my entire life, but no graphs.

I am able to draw for example binary counters, because their graphs look like real things. But I can't see Greek salad as a graph. I need some help. When I see the examples, I should learn it all very quickly, but now I have nothing to start and nobody to ask.

# Answer
> 4 votes
I'm not sure how to approach your particular problem, but here is an attempt.

Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "make dressing", "shred lettuce", "slice cucumber" etc. The dependencies are given through resources, which here are ingredients, possibly in some processed state, like oil, vinegar, cucumber, *sliced* cucumber, etc.

To model this process as a Petri net, you use

* places to represent the various resources, i.e. you have a "vinegar" place, a "shredded lettuce" place, etc,
* tokens on those places to represent the amount of each resource you have; initially this would be something like one token on each unprocessed ingredient,
* transitions to model actual steps in the recipe; for example you could have a "make vinaigrette" transition consuming a token from the "oil" and "vinegar" places and producing a token in the "dressing" place.

The amount of detail here depends on what you want to do with the model; you might for example want to keep track of equipment in addition to ingredients (with the "make vinaigrette" transition additionally consuming a clean whisk and producing a used whisk), etc.

Is this the kind of example you had in mind?

---
Tags: modelling, petri-nets
---


# Question
Title: Regularity of unary languages with word lengths the sum of two resp. three squares
I think about unary languages $L\_k$, where $L\_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L\_k=\\{a^n\mid n=\sum\_{i=1}^k {n\_i}^2,\\;\\;n\_i\in\mathbb{N\_0}\\;(1\le i\le k)\\} $$ It is easy to show that $L\_1=\\{a^{n^2}\mid n\in\mathbb{N\_0}\\}$ is not regular (e.g. with Pumping-Lemma).
Further, we know that each natural number is the sum of four squares which implies that for $k\ge 4$ all languages $L\_k$ are regular since $L\_k=L(a^\*)$.

Now, I am interested in the cases $k=2$ and $k=3$:

$L\_2=\\{a^{{n\_1}^2+{n\_2}^2}\mid n\_1,n\_2\in\mathbb{N\_0}\\}$, $L\_3=\\{a^{{n\_1}^2+{n\_2}^2+{n\_3}^2}\mid n\_1,n\_2,n\_3\in\mathbb{N\_0}\\}$.

Unfortunately, I am not able to show whether this languages are regular or not (even with the help of Legendre's three-square theorem or Fermat's theorem on sums of two squares).

I am pretty sure that at least $L\_2$ is not regular but unhappily thinking is not a proof. Any help?

# Answer
> 8 votes
Let's start with $L\_2$. It is known that the upper density of integers which are the sum of two squares is 0. If $L\_2$ were regular then it would be eventually periodic, and so, since its upper density is 0, finite. But we know that there are arbitrarily large integers in $L\_2$, so that $L\_2$ cannot be regular.

Regarding $L\_3$, consider the words $w\_k = 1^{4^k 7}$. I claim that for $k \< \ell$, the words $w\_k,w\_\ell$ are inequivalent. Indeed, $w\_k 1^{4^k 8} \notin L\_3$ while $w\_\ell 1^{4^k 7} \in L\_3$. The Myhill–Nerode criterion then shows that $L\_3$ is irregular.

# Answer
> 5 votes
Suppose $L\_3$ is regular. Then so is its complement, which by Legendre's three-square theorem is $\\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\\}$. By Parikh's theorem, this would imply that the set of lengths $S=\\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\\}$ is semi-linear, i.e. a finite union $\bigcup\_{i=1}^NS\_i$ of linear sets $S\_i=\\{a\_i + rb\_i\ |\ r\in\mathbb{N}\\}$.

Consider two elements $s\_1 = 4^{k\_1}(8l\_1+7), s\_2 = 4^{k\_2}(8l\_2+7)\in S$ with $k\_1\>k\_2$, and let $r:=k\_1-k\_2$. If $s\_1,s\_2$ are both in the same $S\_i$, then so is either $2s\_1-s\_2$ or $2s\_2-s\_1$ (depending on whether $s\_1\<s\_2$ or $s\_1\>s\_2$). But

* $2(4^{k\_1}(8l\_1+7))-(4^{k\_2}(8l\_2+7)) = 4^{k\_2}(8l'-7)$, where $l'=4^{r-1}(8l\_1+7)-l\_2$,
* $2(4^{k\_2}(8l\_2+7))-(4^{k\_1}(8l\_1+7)) = 4^{k\_2}(8l'-7\*4^r+14)$, where $l'=2l\_2-4^rl\_1$.

Neither of these are in $S$, so $s\_1,s\_2$ would have to be in different members of the union. But this is impossible, since $S$ is a finite union, and there are infinitely many different $k$.

Therefore, $L\_3$ is not regular.

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


# Question
Title: What usage is the delta defined in the polynomial hierarchy?
At the Wikipedia page, the polynomial hierarchy also defines the following:

$\Delta\_0^\text{P} = P$, $\Delta\_i^\text{P} = \text{P}^{\Sigma\_{i-1}^\text{P}}$

However, the only usage of this anywhere else on the page is the following set of inclusions:

$\Pi\_i^P \subseteq \Delta\_{i+1}^P \subseteq \Pi\_{i+1}^P$.

What usage does this $\Delta\_i^P$ class have?

# Answer
> 3 votes
The polynomial hierarchy is an analog of the arithmetical hierarchy in recursion theory, which also has $\Sigma,\Pi,\Delta$, and several other hierarchies also have $\Delta$ terms.

The usage is exactly the same as the usage of $\Sigma\_i^P$ and $\Pi\_i^P$. For a given problem, you try to find its exact location in the polynomial hierarchy. If a problem is in $\Delta\_i^P$ then it can't be $\Sigma\_{i+1}^P$-hard (unless the polynomial hierarchy collapses), but perhaps it is $\Delta\_i^P$-hard. So you might need these classes for some problems.

---
Tags: complexity-theory
---


title: Dijsktra's algorithm example

text:
# Question
Title: Dijsktra's algorithm example
In the following example, how does Dijkstra's algorithm find the shortest path?

I think we'll get abedz, while the shortest should be acedz.

# Answer
You have a mistake in your steps, maybe because you misunderstood the algorithm.

The following table show the values i get when executing the algorithm:

```
              a    b    c    d    e    z
------------------------------------------
Distance      0    Inf  Inf  Inf  Inf  Inf
Visited       F    F    F    F    F    F
Predecessor   -    -    -    -    -    -
------------------------------------------
              0    3    4    Inf  Inf  Inf
              T    F    F    F    F    F
              -    a    a    -    -    -
------------------------------------------
              0    3    4    9    8    Inf
              T    T    F    F    F    F
              -    a    a    b    b    -
------------------------------------------
              0    3    4    9    5    Inf
              T    T    T    F    F    F
              -    a    a    b    c    -
------------------------------------------
              0    3    4    7    5    17
              T    T    T    F    T    F
              -    a    a    e    c    e
------------------------------------------
              0    3    4    7    5    14
              T    T    T    T    T    F
              -    a    a    e    c    d
------------------------------------------
              0    3    4    7    5    14
              T    T    T    T    T    T
              -    a    a    e    c    d

```

Then the shortest path is `a -> c -> e -> d -> z` with weight 14, as you correctly guessed.

Compare this table with your steps to find where is your mistake.

Important facts to take in count:

1. Visited vertices are never re-visited.
2. When a vertex has been marked as visited, the path to that vertex is the shortest route from the starting vertex.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Better algorithm for determining if a vertex is on any cycle in a graph
The problem I'm facing is the following:

> Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$.

The algorithm I can think of is to remove an edge from $u$ to one of its neighbours $v$ at a time and ask if there is still a path from $u$ to $v$ in the resulting graph, placing $(u,v)$ back before the next iteration.

I estimate the time complexity as $O(\Delta\cdot(m+n))$, with $\Delta$ being the greatest degree of the graph and $(m+n)$ for using a BFS on each iterarion.

Is there a better algorithm than this one? Does a simple DFS solve this problem and I'm just losing time with this?

---

BFS: Breadth-First Search
DFS: Depth-First Seatch

# Answer
You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.

Then you can check whether one neighbour can reach another.

Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).

I let you work out the details.
> 2 votes

---
Tags: algorithms, graphs, efficiency
---


# Question
Title: Use the pumping lemma to show that the language is not regular
I am working on this problem : Use the pumping lemma to show that the language $\\{0^n 1^{n} \mid n ≥ 1\\}$ is not regular. May someone give me some suggestion about how to solve this problem?

# Answer
Suppose that $L=\\{0^n1^{n+2}| n\geq1\\}$ is regular and choose the word $\sigma=0^N 1^{N+2}$(with $N$ the pumping lemma constant) to find a contradiction.
> 0 votes

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


# Question
Title: Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$
> Prove/Disprove: $L\_1, L\_2 \in RE-R \implies L\_1 \cup L\_2 \notin R$

My first intuition is "Yes", since we may look at $M\_1, M\_2$ which accepts $L\_1, L\_2$, respectively. Then, WLOG there's $w$ such that $M\_1$ doesn't halt for, and so the machine $M$ which runs $M\_1, M\_2$ in parallel, **may not** halt.

# Answer
> 7 votes
Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider $$ L\_1 = 0\Sigma^\* \cup 1L, \quad L\_2 = 1\Sigma^\* \cup 0L. $$

---
Tags: formal-languages
---


# Question
Title: Dijkstra function for navigation for disadvantaged
Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be shorter but not preferable to wheelchair bound individuals. The navigation solution should also support all individuals and only give a path discarding stairs if the specified user group is someone who is wheelchair bound etc. So basically i am attempting to write a function that checks if user group = wheelchair bound then removes the shortest path to stairs and gives the path to the nearest elevator. I am pretty new to this so any assistance would be very much appreciated. My apologies for being unclear previously.

# Answer
Dijkstra's algorithm already solves your problem. If a staircase is unusable for the wheelchair-bound, then the corresponding edge should not appear in the graph. If some other route is usable but very slow, then it should be weighted accordingly.

The same kind of problem is already encountered with cars – some paths are too narrow for them. A smart GIS takes this into account, removing the corresponding edges when you navigate your car, and keeping them when you navigate your walk.

The difficult aspect here is obtaining this information – which path is suitable for the wheelchair-bound, and which ones should get penalties. Whether it can be done automatically (with a few mistakes) depends on your situation, which you haven't described in enough detail.
> 2 votes

---
Tags: algorithms
---


# Question
Title: How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs?
As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable?

This is not a "technical" question. I want to understand how importantly does the community view this question if hypothetically someone does this.

---

May be you can just comment and not write an "answer"

# Answer
There is already an explicit construction of Ramanujan graphs, due to Margulis and (separately) Lubotzky–Philips–Sarnak. Their construction only gives graphs with degree $p+1$ for some prime $p$. Later this was extended to cover prime powers $p$.

Recently, Marcus, Spielman and Srivastava gave a probabilistic construction of bipartite Ramanujan graphs of all degrees, and the paper appeared in FOCS 2013, and is due to appear in the Annals of Mathematics. This construction cannot even be implemented by an efficient probabilistic algorithm, and only works for bipartite graphs. In very recent work, the same authors extend their method to give bipartite Ramanujan graphs of all degrees and all sizes, in work that was submitted to FOCS 2015 (per Adam Marcus's homepage).

The community finds the recent line of work exciting not only because of the results themselves, but also because of the very interesting technique, which while (as far as I understand) not entirely new, has reached a new level of sophistication and applications. Improving on their results, either to get efficient algorithms or to remove the bipartiteness assumption, will likely require new techniques, and so will be exciting for the community.

While both papers mentioned above were submitted to FOCS, this is just due to coincidence; they might as well have been submitted to STOC. There is no real difference between these conferences, other than the time of year in which they take place, and the organization sponsoring them. SODA is considered less prestigious than FOCS and STOC.
> 3 votes

---
Tags: complexity-theory, graphs, reference-request
---


# Question
Title: Unambiguous but nondeterministic context-free language?
Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, unambiguous context-free languages may still be nondeterministic.

However, they never give an example. Is there a short, simple example of a context-free language that is

* unambiguous
* but nondeterministic

# Answer
$\\{ww^R\mid w\in\\{a,b\\}^∗\\}$ should do the job. The rest is up to you regarding proofs, such as providing an unambiguous grammar.

From Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL? Third answer by Google.

Another one found similarly at Non-Deterministic CFLs: $\\{x^ny^n \\;\mid\\; n \geq 0\\} \cup \\{x^ny^{2n} \\;\mid\\; n \geq 0\\}$
> 6 votes

---
Tags: context-free
---


title: Intuition behind F-algebra

text:
# Question
Title: Intuition behind F-algebra
I looked at here for getting an intuition about F-algebra, but I am still left with some questions.

Suppose I have a group signature as $\Sigma= (\* : X \times X \rightarrow X, \thicksim: X \rightarrow X , e : \rightarrow X)$, with the following axioms in a unuiversal algebraic way:

1. $x ∗ (y ∗ z) = (x ∗ y) ∗ z$ (Associativity)
2. $e ∗ x = x = x ∗ e$ (Identity element)
3. $x ∗ (\thicksim x) = e = (\thicksim x) ∗ x$ (Inverse element)

A model of the above signature is an assignment of two functions to its function symbols, and a constant to its constant symbol, such that the above three laws hold.

**My Question:**

How the above structure with three axioms, can be encoded (represented) in an F-algebraic notion:

> 1) What is my endo-Functor F and why is that?
>
> 2) How these three laws are represented in F-algebra?

p.s.: I would appreciate if anybody refer to a textbook, or a document that I can read more examples to further understand the F-algebra concept.

# Answer
Given a functor $F:Set\to Set$, an $F$-algebra is just a function $f:F(X)\to X$, where $X$ is some set known as the carrier set.

In your example, $X$ is the set of elements of some group.

The endo functor $F$ in this case is $$F(X)=X\times X+X+1.$$ Think of this as representing the three different operators. The first component of the sum, $X\times X$, captures the arguments of $\*:X\times X\to X$. The second component, $X$, captures the arguments of $∼:X\to X$. The third component, $1$, captures the constant $e:1\to X$ – the $1$ represents a set with one element, thus the function $e$ picks out a single element of $X$.

To understand why these components are summed together, recall that there is an isomorphism $(A\to X) \times (B \to X) \equiv (A+B)\to X$ (where $+$ is disjoint union of sets).

The three functions above can be seen as an element of the set given by the product of their signatures: $$f=(\*,∼,e):(X\times X \to X)\times (X\to X) \times (1\to X).$$ Using the isomorphism, we can find an equivalent function $$f':(X\times X + X + 1)\to X,$$ which is $F(X)\to X$. Thus, an $F$-algebra.

To capture the notion of a group needs additional equations (the expected ones), which falls outside of the basic definition of an $F$-algebra, but are added in a trivial way.

Googling "Universal Algebra" will find you some online textbooks/notes. I'm not sure which ones are good.
> 8 votes

---
Tags: logic, functional-programming, category-theory
---


title: Ford-Fulkerson Running Time

text:
# Question
Title: Ford-Fulkerson Running Time
This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!

In the analysis of Ford-Fulkerson I understand why the while loop runs no more than $val(f^\*)$ times but I don't see why it only takes $O(E)$ time to find an augmenting path. Using a BFS or DFS would give $O(V+E)$ no? The running time I see everywhere says $O(E\cdot val(f^\*))$

Also, given $C$, the maximum capacity of any edge in the network, I see a lot of people stating the bound $val(f^\*)\leq nC$ where $n$ seems to be $|V|$. However it isn't clear why this relation holds. $val(f^\*)\leq C|E|$ makes more sense to me but never seems to be used...

# Answer
> 5 votes
There might be some more clever trick in the analysis to get rid of the $V$, but at the very least, I can provide some intuition as to why you can get rid of it.

With Ford-Fulkerson, it is generally assumed that you are working with connected graphs.

For any connected graph with $V$ nodes, there are at least $V-1$ edges, since each node needs at least one edge (except the "last" one in a sense) to be connected.

This means that, either there are $O(V)$ edges, in which case $O(V + E) = O(E)$, or the number of edges dominates the number of vertices (for example, when there are $O(V^2)$ edges), in which case the $V$ gets dominated and we can just write $O(E)$.

When you learn breadth-first search and depth-first search, one of the main applications is testing for connectedness and finding connected components. Here, you could be dealing with a graph with thousands of components, so it makes sense to not assume that there is one component.

---
Tags: complexity-theory, graphs, runtime-analysis, network-flow
---


# Question
Title: union of two equivalence classes (Myhill–Nerode theorem)
Let a language, $L$ such that the equivalence relation, as defined in Myhill–Nerode theorem has $4$ equivalence classes; $A\_1, \ldots, A\_4$.

Let $S = A\_1 \cup A\_2$.

> 1. Is $S$ always regular?
> 2. How many equivalence classes does the relation $\sim S$ creates?

1. I think we may construct two DFA's, $D\_1, D\_2$ which accept $A\_1, A\_2$, respectively. Let $D$ to be the DFA accepting $L$. We construct $D\_1$ by copying the states of $D$. We choose arbitrary $w\in A\_1$ and run it on $D$. We mark as accepting state only the state which accepted the $w$. Same applied for $D\_2$. Finally, we unite $D\_1$ and $D\_2$ be connecting a new starting state and two $\varepsilon$ arrows to each DFA. So we constructed in that way an NFA and therefore $S$ is a regular language. **Is this construction legal?**
2. My thought is $3$ because every word can be either at $S, A\_3, A\_4$. **Am I right?**

# Answer
> ... **Is this construction legal?**

The construction is legal, but it isn't guaranteed to recognize $S=A\_1\cup A\_2$. The problem is that $D\_1$ and $D\_2$ don't necessarily recognize $A\_1$ and $A\_2$. But they recognize them if $D$ is the minimal DFA recognizing $L$. But you are making your live unnecessary complicated anyway. You could just mark the states corresponding to $A\_1$ and $A\_2$ as the accepting states, and you have your DFA recognizing $S=A\_1\cup A\_2$.

> My thought is 3 because every word can be either at $S$, $A\_3$, $A\_4$. **Am I right?**

No, at least this argument is not convincing. The DFA constructed above still has 4 states, so we only know that it cannot be more than 4. We also know that it must be more than one, which leaves 2, 3, and 4 as possible answers. My own guess would be actually 4, but I assume here that $A\_1$ and $A\_2$ are just two arbitrary equivalence classes, i.e. that the indices have no significance.
> 1 votes

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


# Question
Title: Local Cache miss using MESI Coherence Protocol
My notes on MESI state that there are a few courses of action when we experience a local cache miss on read, depending on the global state of the data (whether other copies already exist, and the state they exist in)
I'm having some trouble understanding how we know the state of the data when we miss on a read.
As far as I'm aware, MESI data is attached to each cache line, so if we have do not have a copy of the required data (we missed on the read) then how do we know the relevant MESI data, so we can make the decision on how to react to the miss? (whether we should read from memory, check for shared/modified copies etc)

# Answer
> 3 votes
In cache coherence protocols there needs to be a single location where the global state can be figured out. There are two ways to implement this location. The first is to use a *directory*. The second way is to broadcast all information on a shared *bus*.

If you are using a directory, then the cache that misses sends a message to the directory node that "knows" the global state for that cache line. The directory records the list of caches that have a copy of the cache line and what the state is at each of those caches. (This is easier than it sounds at first, the line is either *invalid* everywhere, *modified* in exactly one cache, *exclusive* in exactly one cache, or *shared* in more than one cache.)

In a directory-based coherence protocol, when a cache misses it sends a message to the directory for that line. If the directory sees that the line is invalid everywhere it forwards the request to the main memory, which responds to the cache, and the directory updates its state so that it knows the cache has an exclusive copy.

If the directory sees that the line is modified or exclusive in another cache, it forwards the request to that cache, changes the global state to shared, and (in most versions of the algorithm) saves the identifiers of the two caches that are now sharing the line.

If the directory sees that the line is in state shared, it forwards the request to one of the other caches sharing the line, and adds the requester to the list of sharers.

Directory based cache coherence is elegant, and scalable, but requires more than the necessary number of message hops for small systems, so for small systems a hack is used to replace the directory. Instead of a directory, all requests from caches or responses to requests (from other caches or from memory) are placed on a shared *bus*. Every message is broadcast to all the other nodes on the bus. So in the case of a read miss: the cache that missed broadcasts a request for the data in state "shared". All the other caches and the main memory are listening to the bus (this is called *snooping*). If one of the other caches has the line in state modified or exclusive, it changes its state to shared and sends the data back on the bus to the requester. If several of the other caches have the line in state shared then they will all try to send the data back on the bus to the requester (and the bus arbiter will ignore all but one of the replies). Finally if *none* of the other caches have a copy of the line then the main memory will respond with the data. The cache that made the request sees that the responder was main memory rather than another cache, so puts the newly received line in state exclusive.

---
Tags: cpu-cache
---


title: weights in a simple neural network

text:
# Question
Title: weights in a simple neural network
I have seen that in the material made by Andrew Ng about neural networks, he uses the following weights:

so when I replace the final values of h\_theta(x) in the formula:

I got values near 0 and 1.

The problem that I have is when I use the values that are in the Tom Mithell book about Machine Learning, he uses the values w0=-0.8, w1=w2=0.5. I have performed the calculations and got the values of h\_theta(x) as the following:

0.8,0.3,0.3,-0.2

but when I replace these set of values into the formula of the sigmoid function I got:

0.31,0.42,0.42,0.54

that does not differentiate too much about which values are near 0 and which near 1, something that did not occur with the values that Andrew Ng proposed for the weights. Am I missing something? in this case it would be better to select big values for the weights instead of small ones?

Any help for clarifying this is welcome

# Answer
> 1 votes
It's just that the logistic function reaches its saturated regime around +-4.6, as in the image. So, any absolute values of x much lower than this will give you results around 0.5. Increasing the absolute value of the weights (all of them) you'll get nearer the saturated region, resulting in outputs closer to 0 and 1. Nevertheless, if you use the step function at the output layer instead of the logistic, you'll get the correct values exactly for both sets of weights: 0 0 0 1.

---
Tags: neural-networks
---


# Question
Title: Disadvantages to using simple step functions for activation in neural networks?
From what I have read, the main advantage to using tanh(x) or sigmoid(x) as an activation function for neural networks is that it is very easily differentiable.

I am trying to implement a neural network that uses a genetic algorithm for optimisation rather than backpropogation, and therefore it doesnt matter if my activation function is differentiable or not

When running my algorithm on matlab/octave, it seems like there is a massive bottleneck in the computation when it is trying to calculate sigmoid of the input to the neuron, so I was wondering if there would be any disadvantage to using a simple step function instead of the more complex sigmoid or tanh functions to activate the neuron?

# Answer
> 3 votes
The disadvantage would be that your fitness landscape would look less smooth (a small change in your weights may result in a big change in the output or no change at all). This may affect the convergence speed of your GA, since small changes in the chromossomes may not produce differences in fitness, rendering it blind to some benefical changes. If your problem is performance, I'd suggest to try the hard ReLU activation function instead of a sigmoid one.

---
Tags: machine-learning, neural-networks, genetic-algorithms
---


title: Draw a DFA that accepts ((aa*)*b)*

text:
# Question
Title: Draw a DFA that accepts ((aa*)*b)*
A homework question asks me to a draw a DFA for the regular expression

$((aa^\*)^\*b)^\*$

I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s many times, in terms of a DFA.

I would guess it that $(aa^\*)^\*$ should be the same thing as $\lambda + a^\*$ but I'm not sure if I can formally say that. If I could, it would make my DFA simply

# Answer
**Edited:**

* (a\* a)\* can be change to a\*
* Now we have (a\* b)\*
* i.e. If nothing comes then, we have to be at final state. If b comes then, we have to be at final state. But if a comes then, sequence of a followed by single b is accepted.

DFA for this will be:

M=({q0,q1}, {a,b}, ∆, q0, {q0})

Where,

q0= initial as well as final state

And ∆: ∆(q0, b)=q0 ∆(q0, a)=q1 ∆(q1, b)=q0 ∆(q1, a)=q1

**Explanation:** As q0 is initial as well as final, then, epsilon and b is accepted. If a comes then, it will be followed be a b.
> 1 votes

# Answer
I recommend you first try to understand the language denoted by the regular expression. Once done this can make it easier to build the DFA directly . If you can not think of how to build the DFA you can always turn your regular expression into an NFA and then the NFA into a DFA(Convert regular expression to DFA).

The strings denoted by your regular expression are:

> Empty string or a concatenation of strings formed by a chain of zero or more $a's$ followed by a $b$. This mean that your initial state should be a final state too and a word in this language "always"(except $\epsilon$) finish with a letter $b$ so your DFA can't transition to a final state consuming a letter $a$. I hope those hints can help you to generate your DFA directly.
> 1 votes

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