# Question
Title: How can I explain to my parents that I study programming languages?
I am currently finishing my MSc in computer science. I am interested in programming languages, especially in type systems. I got interested in research in this field and next semester I will start a PhD on the subject.

Now here is the real question: how can I explain what I (want to) do to people with no previous knowledge in either computer science or related fields?

The title comes from the facts that I am not even able to explain what I do to my parents, friends and so on. Yeah, I can say *"the whole point is to help software developers to write better software"*, but I do not think it is really useful: they are not aware of "programming", they have not clue of what it means. It feels like I am saying I am an auto mechanic to someone from the Middle Ages: they simply do not know what I am talking about, let alone how to improve it.

Does anyone have good analogies with real-world? Enlightening examples causing "a-ha" moments? Should I actually show a short and simple snippet of code to 60+ year-old with no computer science (nor academic) experience? If so, which language should I use? Did anyone here face similar issues?

# Answer
If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge that they do this task methodically: *if* this number is greater than 9, *then* add a carry, and so forth. This description they just gave of what to do that is an example of an *algorithm*.

This is how I teach people the word algorithm, and in my experience this has been the best example. Then you can explain that one may imagine there are more complex tasks that computers must do, and that therefore there is a need for an unambiguous language to feed a computer these algorithms. So there has been a proliferation of *programming* languages because people express their thoughts differently, and you're researching ways to design these languages so that it is harder to make mistakes.

This is a very recognizable situation. Most people have no concept that the computers they use run programs, or that those programs are human-written source code, or that a computer could 'read' source code, or that computation, which they associate with arithmetic, is the only thing computers do (and data movement, and networking, maybe).

My research is in quantum computing, so when people ask me what I do, I don't attempt to explain that. Instead, I try to explain that quantum physics exists (they've usually heard of Schrödinger's cat, and things that are in two places at once), and that because of this strange physics, faster computation might be possible.

My goal is to leave the person feeling a little more knowledeable than they did going in, feeling excited about a world they didn't know existed, but with which you have now familiarized them. I find that that's much more valuable than explaining my particular research questions.
> 59 votes

# Answer
I would try something like this:

> Programmers can tell computers what to do. To do that, they need to use a programming language. That is a language that is understood by both computers and humans. For example, if you edit a Word document and press a key, the computer will show the letter you pressed. That's because a programmer wrote a program saying: If the user presses "A", put an "A" into the document. If the user presses "B", put a "B" into the document, and so on. The computer just follows the rules in the program that the programmer wrote.
>
> Now sometimes the programmers write a stupid rule by mistake. The computer will try to follow the stupid rule anyway, but if you follow a bad rule, something bad will happen. For example, sometimes, when you're editing a Word document, suddenly everything freezes and the computer doesn't react anymore. That may be because some programmer at Microsoft wrote a less-than-perfect program.
>
> My work is about inventing methods to check programs for such and other mistakes, using other programs and some mathematics. The basic idea is to figure out how to predict what will happen when a program is executed, without actually executing it.
>
> Of course, since it's research, I only work on a little aspect of this, not everything at once, but that's the big picture of what we're trying to achieve.

I'm using an explanation in a similar style for my field (domain specific languages), and I can report that it often helped me overcome the "oh you're a computer scientist I could never do that let me go away and stop talking to you" issue. The key appears to be to get the first couple of sentences out until one reaches an example the other person can relate to, like Word documents in this case. Bonus points for special-casing the example to the other person, such as Excel for accountants or Powerpoint for bosses or computer games for gamers or web browsers or whatever.

Note that you don't have to stay at this superficial level. If you (and the other person!) wants to, you can delve into the details of what you're exactly doing from there. For example, "In my current project, I'm trying to mathematically prove that what I invented last year actually works. That means I have to define very carefully what a program really means, and what my invention predicts a program means, and then I can show that the prediction is actually right".
> 19 votes

# Answer
Most people understand recipes. If you follow the instructions, you'll get a decent meal. Sometimes, though, the instructions can be difficult to follow. For example, when you're making perogies, you'll find instructions like this, taken word for word from Grandma's Polish Perogies:

> To cook perogies: Bring a large pot of lightly salted water to a boil. Drop perogies in one at a time. They are done when they float to the top. Do not boil too long, or they will be soggy! Remove with a slotted spoon.

Yikes. Let's review Grandma's kind advice to us. *Drop them in one at a time*... so they all have different lengths of time they're in the pot. Got it. *They are done when they float to the top*. Well how many is 'they'? Do I catch each one as it comes up? Do I wait for 80% to float to the top and then get them all? This is crazy inaccurate. *Do not boil too long, or they will be soggy!* How do I measure when they're about to get soggy so they aren't in too long? If five pop up to the top at the same time, will I have time to get them all?

And trust me, I've ruined a lot of perogies in my day. This is a serious problem that any perogie cook has run into before. But in spite of these problems that come out even upon the most basic analysis, people are still able to make perogies using this exact same method. But is there something we can do to make more batches of perogies successful and less batches of perogies fail?

Wouldn't it be grand if someone specialized in making recipes more reliable? Someone who said "we can pipeline the perogies so they pop up and out of the water!" or "we can add a special dye to the perogie, safe to eat of course, that gives them different shades and we know to get the darkest ones out first, since they're most at risk of becoming soggy". We want an expert who can take this recipe and fix the potential problems with it. The lives of perogie cooks around the world will be easier, and fewer soggy pasta-potato lumps will be fed to a dog.

Programmers follow recipes all the time too. But sometimes, the equipment they use, the instructions they use, and the interpretations they use don't come together to make the lavish meal they wanted. Thankfully, there are people who dedicate their careers to making the life of a programmer more productive. In your case, you've specialized in one of the tools a programmer uses, the language, to try to make them better.
> 12 votes

# Answer
Your best bet may be to form analogies with human languages.

Programming languages are used to provide instructions to computers. Human languages are used to communicate ideas to other people and to help form our own thoughts. The Sapir-Whorf hypothesis says that the language that you use influences your thought. (The degree to which the Sapir-Whorf hypothesis is true is debated, but we can just accept it to be true when discussing programming languages. Otherwise, you might as well give up on your PhD. )

There is a wide variety of human languages, some with features that we consider to be exotic. For example:

* Some languages require you to indicate evidentiality with every statement: whether the statement is due to your own experience, your own inference, hearsay, speculation, etc.
* Some languages form huge words by agglutination; each word may be highly modified to encode a lot of information about its grammatical role. Other languages hardly ever modify the words at all, and rely on word order or particles to express that information.
* Languages differ in vocabulary size. Some languages have words that can only be translated with a circumlocution (e.g. 엄친아). Some languages have brilliant expressions that are so good that other languages borrow them (e.g. Schadenfreude).
* Some languages have no concept of left/right; you must express everything in terms of north/south/east/west.
* Some languages have no numbers. Languages also vary in the number of common color names.
* Languages vary in their phonotactics. For example, the syllable rate varies, with Japanese tending to use many simple syllables, while Chinese is slower, but encodes information in tones.
* Languages vary in information density. If you look at a Chinese-English-French translation, you'll see that the Chinese version is very compact on paper, and the French will occupy the most space.
* Some languages, like English, are promiscuous: anyone can freely borrow a word from another language and Englishify it. Other languages, like French, have a standardizing body that resists change. Icelandic, for example, is fiercely conservative by nature.

Is there a *best* language, objectively speaking? The answer might depend on what you are trying to do.

* If you're trying to communicate secretly over the radio, Navajo would be a good bet. (Mention your favorite "write-only" language.)
* If you're trying to write a warning to future generations, and the inscription must be understandable a few thousand years from now, you might want to use Chinese (due to the sheer number of speakers and the stability of its writing system) or maybe English (which has changed dramatically over the last millennium, but is very widely known). (C and JavaScript will probably live "forever".)
* Chinese, having a lot of homophones, is great for punning. (Perl poetry)
* Perhaps neutrality is important, in which case you might choose Esperanto. (Java is designed to be portable; C is less so.)
* Maybe you need to express a thought with complete precision, and no natural language will suffice. You have to resort to Ithkuil!
* It may be very difficult to translate between some language pairs (e.g. Arabic-English) because of vast cultural differences and cultural connotations with certain words. Similarly, some ideas are not easily expressed in certain computer languages because the concept just doesn't exist (e.g. tail-recursiveness).

In the end, everything on a computer gets translated to machine language, but picking the right language for the job can greatly affect the productivity, reliability, performance, and agility of your software. We choose straitjacket languages like Ada or Java for "serious" projects, and Ruby or Perl for maximum whipuptitude. For querying a database, SQL is the usual language; writing your own C code would be idiotic.

Based on these analogies, I'm sure you can expound on ideas like functional programming, type safety, type inference, etc. for a few hours.
> 8 votes

# Answer
Here is how I would (try) to explain this to my mom:

Programming languages are used by people to provide instructions to a computer. Everything that a computer does is done through some computer code written in a programming language by a programmer.

So if, for instance, we want the TV channel to change when we press a button, then we would need to write some code in a programming language to do this. The same goes for everything that happens with a laptop, a smartphone, and anything else whose operation involves a computer.

It might seem like there might be a single programming language that programmers could use to write all programs. But this just isn't the case. Different programming languages exist for all different types of applications.

Some are used to build websites, others to build the laptop applications (like Microsoft Word).

One of the reasons there are many different programming languages is because some are better suited to some tasks than others. Another reason is that some languages are designed to be used with different computers. So you can't always take code written for a smartphone and run it on a laptop. And while some programmers can program in many languages, and many are capable or learning new languages quickly, any programmer is going to know some languages better than others, and some not at all.

So programming languages are one of the key technologies that make computers work. Well designed programming languages can increase the productivity of programmers tremendously. They can also improve security and reduce programming errors, bugs, and defects.

And so basically, this is what I study: How do different parts of programming languages affect programmer productivity? What parts of a particular language make it better for writing code for a web site? Why are some languages more popular than others?

While it may seem that these questions are esoteric and far removed from the average person's daily life, the opposite is true. The study of programming languages is vital to any product or service that uses a computer. And today that means just about everything ;)
> 7 votes

# Answer
* computer languages relate somewhat roughly to human languages. they use standard/ common/ shared words. consider that there are thousands of human languages, some defunct, others active, and their vocabulary and usage is continually evolving over time. some people create new useful words to express concepts that were not previously expressible. another overlapping aspect of computer language and human language is *grammar*. some languages eg english have very complex grammar. consider all the different *tenses* and the complex *rules* that govern them. other languages do not have the same *tenses*. another correlation is with *parts of speech* categories eg noun, verb, adverb, adjective etc, these function somewhat like *types* in computer languages. imagine creating new languages with different parts of speech categories that have not previously been considered, or with new combinations of parts of speech that come from different languages, etc.; so note that linguistics has a connection to computer science eg esp in Chomskian language theory.
* software and hardware often are related to *engines* and *machines* and even are named after this. there is an old software analogy that trying to modify a complex 24/7 production system is like *changing the engines of a plane while it is in flight*. also note that jet engines are highly complex and involve massive precise specifications of *interchangeable parts* and here there is some analogy to computer languages that control hardware. imagine all the complexity of documents that describe exactly how to build jet engines: all the parts, how they are constructed, how they fit together, how they are assembled etc; they are created/ compiled by engineers using a precise format/ structure/ conventional rules; software is somewhat analogous to this.
* re *machines,* anyone without scientific or mathematical education or even a child can understand the basic concept and many aspects of a *Turing machine!* a wondrous creation. one suspects Turing was inspired by typewriters and/or teletype machines. one could describe the state table, and show them a sample state table that computes multiplication, and someone could watch a youtube animation of a Turing machine compute a basic computation like a multiplication. tell them that the state table can compute or literally *decide* a *language,* and that the inputs are literally called *words*. in fact, Turing machines accept *words in languages* etc. then tell them that there are two state tables that both compute multiplication, but one is much faster or more efficient than the other, and that your research involves finding better state table concepts. figuring out how to build state tables effectively involve *programming languages* that summarize the contents of large state tables! a *compiler* converts code written in a programming language into a large state table.
* sorting algorithms are a great entry level metaphor into computer science. one can look at the different *lists of instructions* aka *algorithm* for each sort. one can learn what a bubble sort is versus an insertion sort, one can use a deck of cards. now focus on the different sets of instructions, and consider that they have to be written in a very precise language, *as precise as mathematical statements,* which has a strict *syntax* etc, and has basic commonalities/ structures: *conditional logic, loops, variables* etc, and explain that the art of this precise specification is about *computer languages*, and that some different languages may yield the same algorithms, but that there is some subtle stylistic variations in these languages that are studied at great depth, etc
> 3 votes

# Answer
You simply say "I am helping the guys who teach computers to work"

The idea is programmers teach computers to do stuff using programs and you are helping them. I think it will work assuming they already know a bit about computers.
> 3 votes

# Answer
If you don't want to use comparisons, although I think the "algorithm" one that Lieuwe brought up is very nice to convey the idea, you could say that you want to reduce misunderstandings between humans and computers. After all, you're dealing with languages, and that's something very basic to humans, I guess. So why not pretend the computer is just another mind you want to talk to?

Humans created computers, so we know how the computer's mind works. But the computer usually does not "know" how our minds work. (Or what our actual intention was when we write an intricate and finely crafted bug that lives happily in the brambles of our code for many cycles ;) ) Thus, it is up to us to refine the language we use to communicate with them, and reduce possibilities for misunderstandings. And that's what you do. Analogies like spellchecking or grammar are, of course, very welcome in this context.
> 3 votes

# Answer
Here are two analogies that you may find useful:

* **My work is somewhat like exploring new approaches to musical notation.** (example) Although the predominant notation systems are quite sophisticated, it is valuable to explore alternatives that reduce time/effort/errors for the composer, for the performer, or allow things that are clunky or not possible to express in the predominant system, or even just promote different types of thinking and thus lead to novel compositions. (This makes it easy to understand that one of the challenges is in convincing people to adopt the new stuff.)
* **I am helping to design better *tools* for people in my industry.** Just like people in the manufacturing industry are aided by innovations like cordless drills, laser cutters, and 3D printers (none of which existed 60 years ago), people in the software development industry are aided by more powerful, more precise, more robust, or easier-to-use programming languages and features thereof.
> 3 votes

# Answer
Well, most likely, you have some reason for studying languages - use that reason. E.g.:

> I'm trying to make computers and their applications cheaper, easier to use and safer.

If that's something that piques their attention, feel free to go a bit deeper, but don't forget about *inferential distance* \- most people have huge trouble explaining something that's too far from the student's existing experience and knowledge.

Languages are way down the computer ladder. The people you're trying to explain to likely don't know what *algorithm* is, much less that there are different ways of representing said algorithm that are more or less useful. You can explain anything if you go gently enough, but be prepared to go through many layers if you want to explain something as "deep" as "programming language RnD". It helps if the people you're explaining to already handle math well, but that's about as rare as computer knowledge :)

Go easy on analogies. They sound like they're helping, but from my experience, they usually add to the confusion even if *you* think they're a great help. Programming languages are kind of like lawyer speak... but that's not very helpful for people who don't *already* understand both programming and lawyering, really. If you really need some extra help, examples work well enough - but you do need to accomodate them to the person you're explaining to (and what exactly you're researching)

> You know how you can't divide by zero? I'm trying to make sure that computers never even *try* to divide by zero, so they don't crash when someone makes a mistake.
> 2 votes

# Answer
I find the best analogies are tailored to the person you are talking to. Are they a painter? Discuss how what you're doing is the equivalent of exploring the theory of how to make better brushes, only this field is only 60 years old instead of 600! Equestrians? Compare it to the development of task specific horse-shoes over the years.

If they really want to understand better, my favorite way to explain it is to talk about filling out Tax forms, and the instructions on each line. I find most people over 20 have some experience with IRS Form 1040, and those boxes you fill out correspond pretty nicely to talking about assignment of variables. Then I point out that software does the equivalent of about 2 billion of these a minute (a made up number, but it gets the point across). If you're studying computer languages, its easy for people to grasp why better instructions would actually matter =)

If they still seem interested, this is about the point where I start trying to explain flow control. Usually, by the time I finish discussing flow control over Form 1040, they start getting all excited and start asking if I've sold any of my ideas to the government yet!

I often talk about embedded systems, so sometimes I'll merge the Form 1040 analogy with a robot cooking a loaf of bread (or 500). Usually it works well, though for some reason going from IRS tax forms to making something that leaves a good taste in your mouth is a really hard stretch for some people.
> 1 votes

# Answer
Your parents have some kind of computer. Probably not one, but many. They may have a desktop computer or a laptop, or a phone, or an iPad. If not, then they have a washing machine or a video record or a DVD player or something with a computer inside.

If they don't, you say: "Sorry, but you managed to have a life completely without computers. So I can't explain to you what I'm doing. But the world is changing. You just need to trust me that I know what I'm doing. "

If they have any kind of computer, you say: "This is a computer, and it doesn't just work by magic. It works because some clever man or woman wrote a program that tells your computer how to work. And the job of these clever men and women is really hard, and what I'm doing is helping them to make the job easier".
> 1 votes

# Answer
A while back I decided that a good analogy for programming which could be easily understood for people with little or no computer experience, would be *writing knitting recipes*.

A good knitting recipe contains several sizes in the same list of instructions, which give you loops and if-statements. It is unreadable to those which do not knit, and if it contains errors you end up with misaligned patterns or an extra sleeve. It is then up to you - as the recipe writer - to find out where the recipe was wrong based on the incorrect sweaters and fix it.

You can then use the example of "I am looking at how recipes are different for knitting, crocheting, Nålebinding and similar" and learning to X (where you need to find an analogy for what you actually *do*).
> -1 votes

# Answer
# It's Magic!

When people with no technical background whatsoever ask what it means to write software/programs/do software engineering, I just tell them what it really is: magic. Magicians incant spells in an esoteric language to perform certain tasks, they wave their wands, and something magical happens. I incant certain spells in an esoteric language, I wiggle my mouse, and something magical happens (as far as they are concerned).

If they aren't convinced, I asked them to turn on their smart phone and tell me how anything on it really works. They usually say: "I dunno, it just does. I push buttons and stuff happens." Then I tell them: "Yes, exactly, but I know what is really going on, and it is basically the same as Harry Potter waving his wand and saying: 'Hocus pocus'" For all intents and purposes, to the layperson, I think this is a perfectly legitimate explanation.

Almost everyone knows who Harry Potter is, what he does, and what makes him special (at least that he is a magician and can do powerful things with magic). You can simply explain that sometimes magicians need to write their spells in a new language to make their magic even more powerful, which is not really that far from the truth. You can just tell them that you are studying the process of creating more powerful spellbooks to aid a generation of even more powerful wizards who can create even greater magic on their favorite consumer devices. Everyone appreciates that.

# Epic Fail

If that fails, I fall back to the recipe example, because the non-uniformity of solutions at least teaches people that there is more than one way to skin a cat (or bake a cake), and this is part of what makes programming so tricky. It also helps put the person in the position of being the CPU and sometimes following instructions they might not understand (most people probably don't know the difference between baking soda and baking powder, and why a recipe would have one or the other).

# Dead Ends

I don't like using math as an example, because to do math, you have to understand what the steps are for. You can't do very much math by following instructions blindly (well, you can, but that's not how humans learn it, usually). I don't like sorting as an example because it is too technical for the layperson to appreciate. If I am talking to someone who can appreciate the sorting example, then they probably already have some idea what programming is about, and likely have tried it themselves.
> -1 votes

---
Tags: programming-languages, education, typing, research
---


# Question
Title: Goldbach Conjecture and Busy Beaver numbers?
Background: I am a complete layman in computer science.

I was reading about Busy Beaver numbers here, and I found the following passage:

> Humanity may never know the value of BB(6) for certain, let alone that of BB(7) or any higher number in the sequence.
>
> Indeed, already the top five and six-rule contenders elude us: we can’t explain how they ‘work’ in human terms. If creativity imbues their design, it’s not because humans put it there. One way to understand this is that even small Turing machines can encode profound mathematical problems. Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture.
>
> Aaronson, Scott. "Who Can Name the Bigger Number?" Who Can Name the Bigger Number? N.p., n.d. Web. 25 Nov. 2016.

It seems to me like the author is suggesting that we can prove or disprove the Goldbach Conjecture, a statement about infinitely many numbers, in a finite number of calculations. Am I missing somehing?

# Answer
The statement is *about* infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible.

The surprise may come from the (false) assumption that finding BB(100) would be a "theoretically easier" problem, only made impossible for practical reasons - since there are so many machines, and they can run for such a long time before stopping, if at all - after all, they're just machines...

The truth is that discovering BB(n), for n large enough, has to be an unsurmountable task, for **both** theoretical and practical reasons.
> 11 votes

# Answer
The idea from the author was that you can write a program in 100 lines (any fixed finite number here) which does the following: takes number x, tests conjecture. If not true then stop else continue on the next number.

Knowing busy beaver number you can simulate this machine for that number of steps and then decide if it halts or not. From above, if it halts - conjecture not true, if it doesn't halt - conjecture is true.
> 9 votes

# Answer
Aaronson has recently expanded in detail on this musing/ idea here working with Yedidia.\[1\] they find an explicit 4888 state machine for the Goldbachs conjecture. you can read the paper to see how it was constructed. TMs are rarely constructed but those that have been tend to be compiler-like based on high level languages and the compilers add many states. a "hand built" TM could easily use an order-of-magnitude less amount of states, eg in the 100s or less than 100. in other words there was not really an attempt in this paper to try to really minimize the # of states. the general idea is sound and computer scientists are generally not so worried about exact constants wrt applied work.

this general theory is outlined by the Caludes (also cited by \[1\]) in two excellent papers which lay out some of the long-folklore theorems in this area and which has been noted by other authors (eg Michel).\[2\]\[3\] basically any open mathematical problem can be converted to undecidable problems. this is because most mathematical problems involve searching an infinite number of cases for counterexamples and counterexamples are algorithmically checkable (but maybe inefficiently or requiring large TMs etc).

also, "very small" TMs (counted in # of states) can check/ be equivalent very complex math problems. eg a rough estimate for a TM to resolve the collatz conjecture would be a few dozen states.

so there is an interesting connection/ analogy between undecidability and NP completeness. NP is the class of efficiently checkable problems, ie instances can be checked in P time. undecidable problems are the class of all problems that allow algorithmic checking for counterexamples with no limit on efficiency.

here is a basic way to understand the connection with the busy beaver problem. all undecidable problems are equivalent due to Turing computability/ equivalence. much like all NP complete problems can be converted to each other in P time (reductions), all undecidable problems are equivalent due to Turing completeness and computable reductions (which can take arbitrary time). hence busy beaver problem is in this sense equivalent to the halting problem, and if one could solve busy beaver, then one could solve all open mathematical questions.

\[1\] A relatively small TM whose behavior is independent of set theory / Yedidia, Aaronson

\[2\] Evaluating the Complexity of Mathematical Problems: Part 1 / Calude

\[3\] Evaluating the Complexity of Mathematical Problems: Part 2 / Calude
> 8 votes

# Answer
1. The Goldbach conjecture can be *falsified* (if actually false) by such a TM program; it can not be proven correct in this way (an insightful mathematician, however, might do this).
2. Knowing BB(27) would allow to stop the Goldbach search at some point; nevertheless BB(27) (or Chaitin's Omega(27)) previously will require to know, whether the Goldbach TM eventually stops, or not.

It is therefore misleading to say "BB(27) includes the answer to Goldbach". Though it does, more to the point is: "Goldbach (and many many others) are prerequisites to the number BB(27)", in other words there is no such thing as a "BB-function" you challenge at 27. We just run all 27-state machines, inkl. Goldbach, and only after the fact see BB(27). And, from a practical POV, even BB(6) seems elusive.
> 1 votes

# Answer
I think it feels less mysterious if we restate Aaronson's point in terms of proofs:

> We can name a constant $C$ so that, if there were any disproof of Goldbach's, it would be at most $C$ characters long. Thus, if we knew $C$, we could prove or disprove the conjecture by listing all strings of length at most $C$ and checking if any of them is a valid proof.

It's somewhat magical that one could name $C$ without knowing whether Goldbach's is true or not (though in practice $C$ is way too large). I feel like the easiest way to see this is via Turing Machines. The TM that enumerates and checks all possible counterexamples to Goldbach's has finite description length $n$, so if it halts, it does so in fewer than $BB(n)$ steps. A transcript of this computation would be a valid disproof and would take only $C = O(BB(n))$ characters.
> 0 votes

---
Tags: turing-machines, number-theory, busy-beaver
---


# Question
Title: Lambda Calculus - free vs. bound variables
While I am reducing the following term, I encountered a little Problem:

$$(\lambda w x. w x)(\lambda w x. w x) \rightarrow\_\beta (\lambda x.(\lambda w x. w x) x)$$

Now my first question: Why is it possible to reduce further after doing alpha conversion? Isn't the last x bound be the first lambda?

Second Question: In my Lectures notes there is mentioned that $(\lambda y . a )b$ -\> a. Why can we do this? Shouldn't the result be b? Because we apply b to all free occurrences of y in a, but there are none so our expression reduces to b.

# Answer
> 3 votes
Iterated abstraction uses abstraction to the right:

\begin{align} LHS &= (\quad \lambda wx.wx \space\space\space)\space(\lambda wx.wx) \\ &= (\lambda w.(\lambda x.wx))\space(\lambda wx.wx) \end{align}

The beta reduction axiom is $(\lambda x. M\[x\])N = M\[x := N\]$.

To satisfy your original equation, replace all occurences of $x$ in the beta reduction axiom, with $w$. Then, substitute the following values into the beta reduction axiom: $$M\[w\] = (\lambda x.wx)$$ $$N = (\lambda wx.wx)$$

The beta reduction axiom with substituted values is $$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = M\[w:=(\lambda wx.wx)\]$$

where $M\[w:=(\lambda wx.wx)\]$ means "substitute all occurences of $w$ in $M$ with $(\lambda wx.wx)$". So we get:

$$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = (\lambda x.(\lambda wx.wx)x)$$

as expected.

For the $(\lambda y.a)b \rightarrow a$ equation, $y$ is a bound variable, while $a$ is a free variable. We apply $b$ to all occurences of $y$, but there are none so our expression doesn't change (no $y$ is converted to $b$). The result is still $a$, unchanged.

Source, really well written and accessible if you give it enough time.

---
Tags: lambda-calculus
---


# Question
Title: Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language
I have the language $L = \\{0^i1^j0^i1^j\ |\ i+j \> 0\\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having some problems with the constant $n$ given by the Pumping Lemma. I do not know how to express $i$ and $j$ in terms of $n$. I have come up with a few example of expressing $i$ and $j$ as $n$ but some cases are always left out.

# Answer
You do not need to express $i$ and $j$ in terms of $n$.

Now suppose $L$ were context-free; then there would exist an $n \geq 0$ such that for every $s \in L$ with $|s| \geq n$ there would be a partition of $s = uvwxy$ such that

1. $|vwx| \leq n$
2. $|vx| \> 0$
3. $uv^iwx^iy \in L$ for all $i \geq 0$

Consider the example string $s = 0^n1^n0^n1^n$. Clearly, $s \in L$, and obviously $|s| \geq n$. You must now examine all the possible partitions of $s$ and show that none of them can satisfy all three of the above conditions.
> 0 votes

---
Tags: formal-languages, automata, context-free, pumping-lemma
---


# Question
Title: NP-hardness of resource allocation problem
I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):

$$ \text{min}\sum\_i\sum\_j x\_{ij}\\ \text{subject to} \sum\_jr\_{ij}x\_{ij} \geq R,\ \ \forall \ \ i \in \[L\]\\ \sum\_i x\_{ij} \leq 1,\ \ \forall \ \ j \in \[N\]\\ x\_{ij} \in \\{0,1\\}.$$

This a resource allocation problem in which I am trying to minimize the number of resources utilized while guaranteeing a certain minimum rate for all entities.

$x\_{ij}$ is an indicator random variable that indicates whether or not a resource $j$ is allocated to an entity $i$. The first set of constraints impose a minimum amount of resource guaranteed for each entity. $r\_{ij}$ is the rate that an entity $i$ can get in a resource element $j$. The second set of constraints ensure that a resource is not allocated to multiple users as sharing of resources is not possible in this problem. $\[L\]$ is the set of user entities and $\[N\]$ is the set of resources here.

I have tried looking at several covering problems like set cover that look like this but the second set of constraints seem to be falling out of place every time. Can anyone suggest an existing NP complete problem that can be reduced to this problem to prove it's NP-completeness?

Thanks

# Answer
> 2 votes
If you set $N = 2$, and $r\_{i0} = r\_{i1} = r\_i$ for each $i$, and set $R = \frac12 \sum\_{i \in \[L\]} r\_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each $i \in \[L\]$ either $x\_{i0}$ or $x\_{i1}$, so that summing the $r\_i$ for those $i$ for which you chose $x\_{i0}$ equals $R$, and similarly for $1$.

---
Tags: complexity-theory, np-complete, resource-allocation
---


title: Set notation of the set of all strings

text:
# Question
Title: Set notation of the set of all strings
How do I present the complement using set notation?

I guess it has to be shows with `universal set - {aa,bb}` but I do not know how to represent the universal set in terms of set notation. Since, the strings of the universal set can be anything over alphabets {a,b}. So, how to represent it? I guess something like this might work if we are going from outside to inside `{{{a,b}*}*}`. Any help is appreciated.

# Answer
The universe here is the set of all strings over the alphabet $\\{a,b\\}$ and is usually denoted by $\\{a,b\\}^\*$.

You have way too many brackets.
> 5 votes

# Answer
> How do I present the complement using set notation?

There is no universally standard way of representing a set complement. But there are a few commonly used notations. If $S$ is a set, then its complement can be denoted by:

1. $S^c$. My personal preference.
2. $\overline S$. I've seen this in a few textbooks but I don't like it because I first learned this notation to mean the mathematical closure of a set.
3. $U \setminus S \quad $ (or $U-S$)$\quad$ if the universal set $U$ is known.
4. $\lnot S$

Because there is no universal standard notation for set complement, it's best to pick whichever common notation you like (if one hasn't already been established in the context) and specify what it means the first time you use it.
> 3 votes

---
Tags: sets, notation, mathematical-foundations
---


# Question
Title: Transform Standard-Dual program to Canonical-Dual program
Say I have the following *Standard-Dual* linear program:
$$max\<\vec b, \vec y\>$$ $$s.t.:A^Ty \le \vec c$$ $$\vec y \ge \vec 0$$ Is there a way to transform it to a *Canonical-Dual* and equivalent linear program, i.e., that of the following form: $$max\<\vec b', \vec y'\>$$ $$s.t.:A'^Ty' \le \vec c'$$ $$\vec y' \in \mathbb R^n$$

# Answer
Yes. For each variable $y\_i$, just add the constraint $-y\_i \leq 0$, and then you don't have to assume that $\vec{y} \geq 0$.
> 1 votes

---
Tags: linear-programming
---


# Question
Title: Why AKS primality test is called polynomial?
It's complexity is $\mathcal{O}(\log^6n)$ and $\log^6n$ is not a polynomial. Can we say that primality testing is **strictly** contained in $P$ then?

# Answer
The time complexity of the AKS primality test is $O(n^6)$, where $n$ is the length of the input. The length of an integer $N$ is roughly $\log N$, so the time complexity of the AKS primality test applied to the integer $N$ is $O(\log^6 N)$.

Finally, I'm not sure what you mean by a problem being strictly contained in P. Every problem in P is contained in some smaller class $\mathsf{TIME}(O(n^k))$ for some $k$.
> 6 votes

# Answer
Any function which is $O(\log^k n)$ for any constant $k$ is $O(n)$. The concept of "strictly contained" doesn't really make sense. Properly speaking, the statement is that primality is an element of the set of problems that can be decided in polynomial time. There's no such thing as "strictly an element": something is either an element or it isn't.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: How is tamper-proofing of software evaluated for effectiveness?
> How is tamper-proofing of software evaluated for effectiveness?

I've been implementing a few algorithms listed within *Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection*. The algorithms include tamper-proofing of software by means of introspection (or computing a hash at runtime over some region of code).

However, nothing is said about the evaluation of such tamper-proofing algorithms: How are they compared to each other and how are their effectiveness measured?

Searching Google, I've come across few articles discussing the subject. One of the articles made an emperical evaluation, where they asked "hackers" to break their implementation and then measured the time taken.

Does anyone know how to evaluate tamper-proofing at a theoretical level?

# Answer
> 2 votes
Unfortunately, we don't know of any way to reliably measure the effectiveness of software obfuscation schemes (or the security of pretty much anything else). The best we can do is publish the scheme, wait for other researchers to try to attack it, and see what the best attacks that someone has been able to find are.

As you can imagine, there are many limitations and caveats with that approach. How do we know whether anyone has tried to break it, or whether the right people with the right skills have tried? Or maybe there is some devastating attack that no one has thought of yet, but might be discovered tomorrow.

Anyway, that's the approach typically taken in practical work on software obfuscation. There is also theoretical work on software obfuscation, which tries to prove security theorems (under some complexity-theory assumptions about the hardness of some well-studied problems). Unfortunately, at present there is a significant gap between practice and theory. For the most part, the provably secure schemes aren't practical, and the practical schemes aren't provably secure. There are exceptions, but they tend to be very special-purpose -- they can only obfuscate a small class of special programs -- and can't be used to obfuscate an arbitrary program. The theoretical work is very interesting and has made many advances but still has a way to go before we can find a truly practical, provably secure, and general scheme for software obfuscation.

Finally, if you are interested in practical schemes for practical use, let me share one last caveat. My personal perspective is that *none* of the practical schemes for software obfuscation appear to be terribly secure. They provide a speedbump that will slow down an attacker or require some effort and skill to break, but I would not expect any of them to resist a dedicated, motivated attacker. So, while they're fine if you just want to increase the cost of reverse-engineering, I wouldn't rely on them to hold up to serious attack. That's just my own personal sense and opinion, which others in the field might not agree with.

---
Tags: security
---


title: Asynchronous Encryption with wordlists

text:
# Question
Title: Asynchronous Encryption with wordlists
As I understand it encrypted emails have a high profile (detectable through pgp header / attachment).

Would it be possible to match the encrypted data with a wordlist to hide the fact that the email contains a encrypted message?

I know that the other person would need the same list of words for decrypting and the message would be only a bunch of random words, but the fact that its encrypted world be not as obvious for automated scanning.

EDIT: As pointed out I am referring to steganography to hide from traffic analysis.

# Answer
Yes, this is possible. It is called steganography and there are many techniques that can be used -- there is an entire literature on the subject. You might enjoy reading about it.

It still won't stop traffic analysis.
> 1 votes

---
Tags: encryption
---


# Question
Title: Is inserting into an ordered array by swapping has downsides compared to inserting into a position and offsetting elements
I'm thinking how I can insert an element into an ordered array. Assume the array has a capacity for one element. I've implemented two methods.

The one finds the position to insert, moves elements one position to the right and inserts the element into the position.

The seconds one which seems more intuitive to me is to put an element into the last position in an array and then put it in the correct position by swapping with the left element - the way it's done in the insertion sort.

However, I googled for the solution and almost all suggestions are some modification of the first algorithm. So I'm wondering if there's something I'm missing. Can you guys please help?

# Answer
> 1 votes
Both work. Both approaches are approximately equivalent, in some sense. However, your approach will do about twice as much work.

Think about an array that initially contains $\[2,4,6,8,0\]$ where the $0$ is the final empty element that can be filled in. Imagine you want to insert the number $5$.

* The standard method will read $8$ from index $3$, then write $8$ to index $4$, yielding $\[2,4,6,8,8\]$; then read $6$ from index $2$ and write $6$ to index $3$, yielding $\[2,4,6,6,8\]$; then write $5$ to index $2$, yielding $\[2,4,5,6,8\]$. That's 2 reads and 3 writes -- 5 memory operations.
* Your method will swap $8$ and $0$, yielding $\[2,4,6,0,8\]$ (this involves reading $8$ from index $3$, reading $0$ from index $4$, writing $8$ to index $4$, writing $0$ to index $3$); then swap $6$ and $0$, yielding $\[2,4,0,6,8\]$; then overwrite the $0$ with $5$. Each swap requires 2 reads and 2 writes, so this does a total of 4 reads and 5 writes -- 9 memory operations. That's about twice as much.

Why is your method slower? Because your method keeps reading the $0$ and writing it somewhere. That is extra, unnecessary work. If you care about optimization, that might matter. If you just want a method that you can understand, either one should be fine.

---
Tags: algorithms, sorting, arrays
---


title: Predecessor-subgraph property

text:
# Question
Title: Predecessor-subgraph property
In the proof of the predecessor subgraph property (page 14 of the following notes) http://www.cs.sfu.ca/CourseCentral/307/binay/shortestpath.pdf $d\[v\_i\] \geq d\[v\_{i-1}\]+w(v\_{i-1},v\_{i})$ is assumed true. Why is this? Shouldn't it be the other inequality: $d\[v\_i\] \leq d\[v\_{i-1}\]+w(v\_{i-1},v\_{i})$ by triangle inequality?

# Answer
> 0 votes
I think the LHS is assumed by argument to be: $d\[v\_{i}\]= \Sigma\_{j=1}^{j=i} w(v\_{j-1},v\_{j})$. Since $d\[v\_{i-1}\]= \delta(s,v\_{i-1})$ = $min$$\\{w(p) : s \rightsquigarrow^p v\_{i-1}\\} $ on the RHS, where $w(p)= \Sigma\_{j=1}^{j=k}w(x\_{j-1},x\_{j})$ for any path $p: x\_{0}=s, ... ,x\_{k}=v\_{i-1}$, we have the inequality $d\[v\_{i}\]\geq d\[v\_{i-1}\]+w(v\_{i-1},v\_{i})$.

---
Tags: graphs, algorithm-analysis
---


# Question
Title: A faster, leaner JavaScript for scientific computing: what features should I keep?
Here I'm really interested in lowering barriers to mathematical education.

Target:

I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked **scientific and high-performance computing** libraries (great lists of which are available through Sage and otherwise). And I want that, because I'd like to make it easy for people who learn JavaScript to get into scientific and numerical computing without having to learn Python (& company). (I know it's easy to learn Python, as I basically did it at some point, but this suggests that perhaps it'll be easy to compile some restricted subset of JavaScript to Python.)

Hypothesised method:

I'm primarily interested in a new language with minimal difference from JavaScript, because the market ("human compilers") I'm targeting are programmers who already know JavaScript. What I want to target those people for, is to give them a minimally different language in which to write code that compiles to faster C, in the manner that RPython and Cython do for Python. I'm willing to throw out a lot of JavaScript features, I just want to be careful to add a minimum number of features back in. I'll definitely be looking at Lua, Dart, ECMA Harmony (which has no formal date of release, or am I mistaken?), etc. as these are all close resemblances to contemporary (2012) implementations of JavaScript.

Questionable Motivations:

I'm personally willing to learn any language/toolset that gets things done faster (I'm learning Erlang myself, for this), but here, I am specifically interested in lowering the bar (sorry) for other people who may not have such willingness. This is just one of those "want to have my cake, and eat it too, so I am putting some time into researching the problem" situations. I have very limited prior experience in computer language design, but so far from a hacking-the-ecosystem point of view, the problem seems interesting enough to study, so, I hope to be doing more of that soon.

# Answer
If you want to use JavaScript for scientific computing, why not try Node.js? Node is based on Google's V8 engine with some additional functionality for interacting with the file system, writing servers and linking to C and C++ libraries (this is definitely not an exhaustive list). It sports fast execution times and provides an interactive console as well as a way to execute your programs from the command line. I found @DaveClarke's comment about Python acting as "glue code" interesting because of the wording. Here is an excerpt from the Node documentation on addons:

> Addons are dynamically linked shared objects. They can provide glue to C and C++ libraries.

Node also has an excellent package manager called NPM, which would make it easy to share scientific modules which you have written. The NPM repository already contains some scientific modules, such as "natural" (for natural language processing) or "clusterfck" (a clustering library). There are most definitely many other libraries out there for a variety of applications.

The great thing about this solution is that you wouldn't have to modify JavaScript or create a new language. The syntax is essentially the same, but your code does not need a browser to execute. If you plan to follow up with node, a good first step might be to start creating addons for existing open-source scientific libraries written in C and C++, or you could port them to JavaScript. I was actually thinking about using node for scientific programming today which is what led me to this question. It would be great to see more robust tools like you find in Python.

I initially had links to natural and clusterfck, but I do not have enough rep to post them. Luckily, they come up as the first results if you google "clusterfck node" and "natural node".
> 8 votes

# Answer
The point of the Python scientific libraries is that Python merely acts as a glue code for shuffling around the data between the scientific libraries. Python itself does little of the high performance grind work. Python is a good language for this, as it supports both the procedural and object-oriented paradigms (and functional to a large degree), and one can easily link with external libraries.

Javascript is heavily tied to browser technologies. It is mostly an awful language not at all designed to be efficient or to write large scale software, although in practice both of those happen due to huge investments in compiler technology and careful use of the language, respectively. Javascript is made 1000 times nicer by well designed libraries such as JQuery. I'm not sure whether Javascipt provides any support for linking easily with C libraries (though I guess it must, indirectly through the browser, and via Java).

I don't mean to be discouraging, but the whole idea seems ill-founded. Javascript and high-performance computing are only found together in sentences beginning with "A man walked into a bar ...."

That said, I'm willing to be proven wrong. Real-time Java exists, which is an odd combination, and is reasonable successful, so who knows.
> 7 votes

# Answer
Just an idea: you can use scientific libraries written in Java (I think you'll find a lot of work already available) with Javascript - that has a syntax similar to Java - used only as a wrapping language for:

* scripting
* user interaction
* (re)modeling and standardization of the underlying high level classes/packages/functions ... though I think it would be better to do this in the Java "layer"

See the Rhino project for a stable Javascript interpreter written in Java.

If you want you can use the Java JNI to use scientific libraries written in C/C++.

The whole picture:

```
                              ____ disparate Java libraries
Javascript   ----- Java      /
(scripting,      ("package   \____ JNI ____ C/C++ libraries
 interaction,     remodeling")
high-level stuff)

```

**EDIT**: just Googling around a found stuff like this: Java GNU Scientific library, List of (Java) numerical libraries, Java Graph library, jHepWork Multiplatform environment for scientific computation and data analysis
> 6 votes

# Answer
Creating a new language is not necessary. One can write performant numeric computing in JavaScript today, without compilation/transpilation. As a scripting language, JavaScript compares quite favorably to Python and R. For benchmarks, run the language benchmarks in stdlib, which compares performance across a wide-range of APIs.

For server-side applications, one can write Node.js native add-ons to interface with the same C/C++/Fortran libraries used in other numeric computing environments, such as R, Python, and Julia. As shown in my work, Node.js native add-ons allow linking to hardware optimized numeric computation libraries, thus enabling high-performance numeric computation from JavaScript.

For client-side applications, one can compile to WebAssembly to achieve 1.5-2x of native performance. For older environments, one can compile to asm.js, which is a reduced subset of JavaScript more amenable to compiler optimization. In my work, asm.js can match naive reference (i.e., non-hardware optimized) implementations written in C/C++/Fortran.

In short, there are no technical reasons why you cannot write numeric and scientific computing libraries in JavaScript, itself. What is needed are people with the time and wherewithal to write rigorous and robust implementations.

**disclosure**: I and others are working on the stdlib project, which aims to bring robust, high-performance numeric computing capabilities to JavaScript and Node.js.
> 5 votes

---
Tags: programming-languages, compilers, performance
---


# Question
Title: Does this program have a runtime of O(N) or O(n*m)
This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure I am properly evaluating the run time of this algorithm.

Imagine we have a list of strings, such as this:

```
words = ["eat", "tea", "tan", "nat", "bat", "cat", "act"]

```

We want to visit each character of each word in this list (The above example comes from an anagram grouping prompt). What would the runtime of visiting each character be? Assume that *neither* the number of words or the length of the words are constants. They are both variables.

in python, that could be done as so

```
for w in words:
    for c in w:
        print(c)

```

I have seen the run time of visiting every element in this list as being:

**O(n\*m)**: where n is the number of words in the list and m is the number of characters

**O(N)**: where N is the total number of characters in the list

O(N) is clearly linear, but O(n\*m) is not (according to the answers in the aforementioned question)

How can the same algorithm be both linear and not linear, simply depending on how you describe the inputs.

In the example case I am considering, all words have the same number of characters, but how might our answer change if this was not the case? Does m then represent the average character length? the length of the longest word?

# Answer
Big $O$ is merely a function that describes an upper bound of another function, so it can be used in different ways. You can describe the big $O$ of the memory usage of a function, or the big $O$ of the number of operations a function performs.

What you've encountered is simply that, by using different descriptors of the inputs, you wind up with different descriptors of the function itself. The function you have described is, in fact, linear to the total number of characters in the input. That statement is not *wrong*, but $O(nm)$, where $m$ is the average number of characters of the words in a set, is clearly a more useful description of the behavior of the function.
> 5 votes

---
Tags: runtime-analysis
---


# Question
Title: To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$
I have done the proof until the point when $T(n) \leq cn^{\log7}$.

But when it comes to finding the value of constant $c$, I am getting stuck.

The given recurrence relation is $T(n) = 7T(n/2) + n^2$.

Since we already calculated the solution above which is $cn^{\log 7}$.

Inductive step:

Now we have to prove that $T(n) \leq c n^{\log7}$ where $c$ is a positive constant. If we consider that the solution holds good for $n/2$ then we can prove that it works for $n$ also: $$T(n/2) \leq c(n/2)^{\log7}.$$ Substituting these values in the recurrence relation:

$$ \begin{align\*} T(n) &\leq 7c/(2)^{\log7} \times (n)^{\log7} + n^2 \\ &\leq cn^{\log7}, \text{ since $7/(2)^{\log7}$ is constant so can be ignored and $cn^{\log7} \gg n^2$ for large $n$} \\ &\leq cn^{\log7} \text{ assuming $c$ is a constant $\geq 1$.} \end{align\*} $$

Finally to find constant $c$,

$$(7/(2)^{\log7}) \times cn^{\log7} + n^2 \leq cn^{\log7}. $$

I am not able to find appropriate $c$ for which the condition holds true.

# Answer
> 4 votes
You're headed in the right direction, but you need an intermediate step. Permit me to simplify things a bit by defining $\lg n = \log\_2n$.

**A Dead End**

Your substitution method, where you want to establish that $T(n) \le cn^{\lg7}$ inductively, using the assumption $T(n/2)\le c(n/2)^{\lg 7}$ runs into problems, as you've already seen. Here's what happens: $$\begin{align} T(n) &= 7T\left(\frac{n}{2}\right)+n^2&\text{by definition}\\ &\le 7\left\[c\left(\frac{n}{2}\right)^{lg7}\right\]+n^2&\text{by the inductive assumption}\\ &=7\left\[c\frac{n^{\lg7}}{7}\right\]+n^2&\text{since $2^{lg 7}=7$}\\ &=c\\,n^{\lg7}+n^2 \end{align}$$ and you'll obviously never be able to find a $c$ for which $c\\,n^{\lg7}+n^2\le c\\,n^{\lg 7}$.

**A Way Out**

The problem is that the $n^2$ term is messing you up. If it weren't there, then substitution would work. Suppose, for instance, that we had the simpler recurrence $S(n)=7\\,S(n/2)$. Now life would be easy, since then the proof above would go through nicely. Assume that $S(n)\le c\\,n^{\lg7}$. Then we'd have $$\begin{align} S(n) &= 7S\left(\frac{n}{2}\right)&\text{by definition}\\ &\le 7\left\[c\left(\frac{n}{2}\right)^{lg7}\right\]&\text{by the inductive assumption}\\ &=7\left\[c\frac{n^{\lg7}}{7}\right\]\\ &=c\\,n^{\lg7}&\text{as required} \end{align}$$ and if you do this again and again, driving $n$ down to $1$, you'll find that you can choose any $c\ge S(1)$.

**Transforming the Dead End Into the Way Out**

Let's make the $n^2$ term go away. Let $S(n) = T(n)+k\\,n^2$. Then from $$ T(n)=7\\,T(n/2)+n^2 $$ we have, substituting and simplifying, $$\begin{align} S(n)-k\\,n^2&=7\\,\[S(n/2)-k(n/2)^2\]+n^2&\text{and so}\\ S(n) &= 7\\,S(n/2)+n^2(k-7k/4+1) \end{align}$$ and it's not hard to see that $k=4/3$ will make the $n^2$ term vanish, giving the $S$ recurrence we just solved above. Putting these together we have $$ T(n)+\frac{4}{3}n^2=S(n)\le c\\,n^{\lg7} $$ and so $$ T(n)\le c\\,n^{\lg7}-\frac{4}{3}n^2\<c\\,n^{\lg7} $$

**Lessons Learned**

Truth to tell, I'd attack this problem by iterative expansion, namely the way Yuval did it in his answer, but these "substitution method" questions come up often enough that I thought this cautionary tale was warranted. The lessons to be learned here are

* The method of substitution often doesn't work when applied to a recurrence relation.
* It always applies to recurrences of the form $S(n)=p\\,S(n/q)$ as long as $q\ne0$
* A useful tool to have in your kit is knowing that sometimes you can transform a complicated recurrence into a simple one by suitable addition (or, sometimes, multiplication).

# Answer
> 1 votes
Suppose $n$ is a power of $2$, say $n = 2^k$, and suppose $T(1) = 1$. Then $$ \begin{align\*} T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &= 7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &= 7^k + 7^{k-1} 4^1 + \cdots + 7^1 4^{k-1} + 4^k \\ &= 7^k \left(1 + \frac{4}{7} + \cdots + \left(\frac{4}{7}\right)^k\right) \\ &= 7^k \frac{1-(4/7)^{k+1}}{1-4/7} \\ &= (1 - (4/7)^{k+1}) \frac{7}{3} 7^k \\ &= \left(1 - \tfrac{4}{7} n^{\log\_2 (4/7)} \right) \frac{7}{3} n^{\log\_2 7}. \end{align\*} $$ Therefore for $n = 2^k$, $$ T(n) \sim \frac{7}{3} n^{\log\_2 7}. $$

# Answer
> 0 votes
When you calculate $T(2^k)$, you first start with T(1), which gets multiplied by 7 k times, giving $T(1)·7^k$.

But when you calculated T(2), you added a term $n^2 = 2^2$, which gets multiplied by 7 (k-1) times, giving $2^2·7^(k-1) = 7^k·(4/7)$.

When you calculated T(4), you added a term $n^2 = 4^2$, which gets multiplied by 7 (k-2) times, giving $4^2·7^(k-2) = 7^k·(4/7)^2$.

The same happens for the other intermediate terms, so your result is $7^k$, multiplied by (T (1) + (4/7) + (4/7)^2 + (4/7)^3 + (4/7)^4 ...), which is a geometric series with a sum of T (1) + 4/3. So c = T (1) + 4/3.

(A bit of care is needed: T (1) + 4/3 is the limit, but you asked for an upper bound. In this case since the values add up, the limit is the upper bound, but that wouldn't work for $T(n) = 7·T(n/2) - n^2$. )

You can use this approach for many similar recurrences. And it will show a problem instantly for the recurrence $T(n) = 7·T(n/2) + n^3$.

# Answer
> 0 votes
Use the master theorem:

https://en.wikipedia.org/wiki/Master\_theorem

by case 1, if $f(n)= O(n^{2\<{log\_{2}7}})$ then $T(n)= O(n^{log\_{2}7})$

---
Tags: algorithms, algorithm-analysis, recurrence-relation
---


# Question
Title: If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover?
I was reading the following paper on Robustness and Generalization (and covering numbers)and I was reading their example 1:

which didn't quite make sense to me. The reason it didn't make sense is that intuitively it seems to me that each region $X\_i$ could have the label either +1 or -1, so it seems to me that the partition of Z should be exponential:

$$2^{\frac{K}{2}}$$

because it region can have either label +1 or -1. However, instead it seems to be that instead if 2 times the epsilon cover of the other set X, which seems puzzling. Any ideas why?

---

Ok for background definition:

Epsilon cover means the smallest set size that can $\epsilon$ cover some target set T. i.e.:

$$ N(\epsilon,T,\rho) = \min \\{ |\hat T | \mid T \subset \cup\_{\hat t \in \hat T} B(\hat t; \epsilon, \rho ) \\}$$

where $B(\hat t; \epsilon, \rho ) = \\{ x \mid \rho(\hat t, x) \leq \epsilon \\}$ is the epsilon ball around $\hat t$.

Ab algorithm $A\_s(x)$ has a margin $\gamma$ if every point in the input space around it would be classified the same way. i.e. as the paper wrote:

$$ A\_{s}(x) = A\_s(s\_{j | x}) ; \forall x: \\| x - s\_{j|x}\\|\_2 \< \gamma $$

for more definition the paper has them pretty much on the page and the page before Example 1 I am referencing.

# Answer
> 1 votes
Given a cover for $\mathcal{X}$, you seek to "cover" $\mathcal{X}\times\\{-1,1\\}$. To do so, you take any set $A$ from the cover of $\mathcal{X}$, and consider the sets $A\times\\{1\\}$, $A\times\\{-1\\}$. If your original cover was of size $K$, then this process results in $2K$ sets (the reason you don't end up with $2^K$ sets is that fixing the label for one set does not affect the labeling of another, so there is no multiplication going on).

In a more straightforward approach, let $\mathcal{C}$ be your original $\frac{\gamma}{2}$-cover for $\mathcal{X}$, then a partition $\mathcal{P}$ of $\mathcal{X}\times\\{-1,1\\}$ such that for all $ p\in\mathcal{P}$ and $(x\_1,y\_1),(x\_2,y\_2)\in p$ it holds that $y\_1=y\_2$ and $||x\_1-x\_2||\le\gamma$, is given by $\mathcal{C}\times\\{-1,1\\}$, which is of size $2|\mathcal{C}|$.

# Answer
> 0 votes
I think the answer is easiest to explain with an example. Say that we want to cover $T = \\{ t\_1, t\_2,t\_3 \\}$ (where $t\_i$ can just be $R^d$ vectors). Say the distance between the $t\_i$'s is 1 and that we are requiring an epsilon cover with $\epsilon = 0.5$. Therefore $N(0.5,T,\\| \cdot \\|\_2) = 3$ (just take the covering set to be $\hat T$ be an small enough perturbation of $t\_i$'s or the $t\_i$'s themselves). I like to intuitively imagine as radius balls around the centers $\hat t$ (or even RBFs using those centers). Now when we include $\cal Y = \\{-1,+1\\}$ as coordinate that means that we need to choose new centers with an extra coordinate but this extra coordinate can only be $+1$ or $-1$.

Now consider the new set we want to cover $T\_{new} = T \times \cal Y$:

$$ T\_{new} = \\{ (t\_1,-1), (t\_2,-1), (t\_3,-1), (t\_1,+1), (t\_2,+1), (t\_3,+1) \\}$$

consider the same set as the cover for it $\hat T\_{new} = T\_{new}$ (or just perturb the first d coordinates a little bit if you want). The that means we only need:

$$ | T\_{first}| \cdot | T\_{second}| = 2|T\_{new}|$$

note that we do have $2^{|T|}$ potential labelings for individual "training points" but that is irrelevant because we are not considering sequences or potential training sets.

In a way we are only interested in how to cover some subset of the new space $\cal Z = \cal X \times \cal Y $. We consider the "data points" with all its possible labels but we can see them all at once in the space $\cal Z$. i.e. We since $(t\_1,-1),(t\_1,+1)$ are both part of the new set that requires covering, we can just choose a way to cover both, but in the problem since they are both part of the set there is no sense of order. We are just considering the new set to be covered in the new space.

---
Tags: algorithms, machine-learning, statistics, mathematical-analysis
---


# Question
Title: Finding triples that satisfy given constraints in $O (n \log n) $ time
> Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k \< n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :
>
> $\bullet \text{ }s\[i\] = "a", s\[j\] ="b" \text{ and } s\[k\] = "c"$
>
> $\bullet \text{ } (j + 1)^2 = (i+1)(k + 1) $
>
> We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.
>
> Example case and solution : The string $"ccaccbbbaccccca"$ with $n = 15$. There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$.
>
> The second solution shows that $i$ is not necessarily less than $k$.

---

I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.

I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.

Hence, we would have to iterate and test in order to find the $ \alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.

This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum\_{k=1}^{n}\sqrt{k})$.

---

I've been at this for too many hours and I have no idea how to proceed. How would you solve this? I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.

# Answer
> 3 votes
Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$. Therefore the total number of potential triples $(i,j,k)$ is at most $$ \sum\_{j=1}^n d(j)^2 = O(n\log^3 n). $$ (For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum\_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).

This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.

---
Tags: algorithms
---


title: Uncomputability of Busy Beaver Function

text:
# Question
Title: Uncomputability of Busy Beaver Function
https://en.wikipedia.org/wiki/Busy\_beaver#Proof\_for\_uncomputability\_of\_S.28n.29\_and\_.CE.A3.28n.29

So this is wikipedia's proof of why Busy Beaver Function is uncomputable. But I don't get two things.

1. How do you know that `< Create_n0 | Double | EvalS | Clean >` has $N$ states? I understand that `< Create_n0 | Double | EvalS >` has $N$ states but I don't understand why adding `Clean` doesn't change the number of states.
2. Why do we need to make a `Double` function? Can't we prove like this: Let's say the Turing machine `< EvalS | Clean >` has $n\_0$ states. Let $\textrm{BadS}$ denote `< Create_n0 | EvalS | Clean >`. $\mathrm{BadS}$ has $n\_0$ states but has more than $S(n\_0)$ shifts, therefore, contradiction.

# Answer
> 3 votes
> How do you know that $ M' = \langle Create\_{n0} \mid Double \mid EvalS \mid Clean \rangle$ has N states?

By definition $n\_0$ is the size of the machine $M = \langle Double \mid EvalS \mid Clean \rangle$; in order to build $M'$ you add $Create\_{n\_0}$ but in orther to do this you simply need $n\_0$ more states: on state $s\_1$ write 1, move right and go to $s\_2$; then write 1, move right and go to $s\_3$, and so on. After writing $n\_0$ $1s$, $M'$ enters the state $s\_{n\_0+1}$ which is simply the initial state of $M$ (states $s\_{n\_0+1},...,s\_{2n\_0}$ of $M'$ are a copy of the states of $M$).

> Why do we need to make "Double" function? Can't we prove like this : Let's say turing machine $M = \langle EvalS \mid Clean \rangle$ has $n\_0$ states. Let $BadS$ denote $\langle Create\_{n\_0} \mid EvalS \mid Clean \rangle$. $BadS$ has $n\_0$ states but have more than $S(n\_0)$ shifts, therefore, contradiction.

No you cannot because in this case $BadS$ has more than $n\_0$ states: $|BadS| \> |M| = n\_0$

A note: though the proof of undecidability of $S(n)$ using the undecidability of the halting problem of a Turing machine on a blank tape is easier, the first proof written in Wikipedia (that you reference in your question) is more interesting because it only uses a "self-reference" of $S(n)$ to itself in order to derive a contradiction.

# Answer
> 4 votes
Here's a simple proof of the non-computability of the Busy Beaver function:

Assume *BB* is computable. Then we can build a program that accepts a TM specification *M* and input *x*. Compute *n = BB(|M|)*, where *|M|* is the number of states of TM *M*. Next, simulate *M(x)* for *n* time-steps. If *M(x)* halts, accept. If after *n* time-steps *M(x)* has not halted, reject. This program solves the Halting-Problem, a contradiction - QED.

---
Tags: turing-machines, busy-beaver
---


# Question
Title: Designing CFG that accepts # of 1's = # of 2's + # of 3's
Designing following language $\\{ w \mid w\in\\{0, 1\\}^\* \mbox{ such that } |w|\_0 = |w|\_1\\}$ is easy.

> Note $ |w|\_0 $ means number of occurrences of 0.

$$ S \to 0S1 \mid 1S0 \mid SS \mid \lambda $$

Then how about this? Language $\\{ w \mid w\in\\{1, 2, 3\\}^\* \mbox{ such that } |w|\_1 = |w|\_2 + |w|\_3\\}.$

It is somewhat difficult for me. Below is my solution. Is it correct?

---

$$ S \to XSX \mid \lambda $$ $$ X \to 1123 \mid 1132 \mid 1213 \mid 1231 \mid 1312 \mid 1321 \mid 2113 \mid 2131 \mid 2311 \mid 3112 \mid 3121 \mid 3211 \mid \lambda $$

# Answer
Given a grammar for $\\{ w \in \\{0,1\\}^\* : |w|\_0 = |w|\_1 \\}$, you can obtain a grammar for $\\{ w \in \\{1,2,3\\}^\* : |w|\_2+|w|\_3 = |w|\_1 \\}$ by replacing $0$ in the first grammar by a non-terminal $Z$, and adding the productions $Z\to 2 \mid 3$.
> 0 votes

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


title: Execution time of a linear pipeline

text:
# Question
Title: Execution time of a linear pipeline
> 19. A simple linear pipeline has three stages. The execution times in the stages are 10, 15, and 12 units respectively. If the pipeline is used to process 100 inputs, then the execution time is
>
> (a) 1530 units
>
> (b) 3700 units
>
> (c) 1500 units
>
> (d) 1537 units

I am not able to understand this question. can anyone help me to understand this question and also the solution.

# Answer
> 0 votes
Every input ("job", "task", whatever) must be processed by all three pipeline stages. The respective execution times for each stage are given; they are the same for each input.

If there are no other inputs (imagine an empty system), a single input will leave the pipeline after 10+15+12 time units, right?

But if there is more than only one input, you might have to deal with congestion... that's what this question is all about. So, how long does it take until the last of the 100 inputs has left the pipeline?

(But I'm not giving out solutions here...)

---
Tags: cpu-pipelines
---


# Question
Title: Complex property of sparse horner polynomials by induction
I'm following this article to do a formal proof on elliptic curve cryptography. My question here addresses only a property "easily proved by induction".

**Definitions** (the important part is the addition definition at the bottom)

Let assume the following hierarchy:

```
abstract class shf;
case class const(c: Integer) extends shf
case class POP(i: nat, p: shf) extends shf
case class POW(i: nat, p: shf, q: shf) extends shf

```

where `nat` is the type for naturals including zero. We state also a property on the hierarchy called normality given by the function:

```
def normal(p: shf) = p match {
 case const(c) => true
 case POP(i,p) => i > 0 && normal(p) && p = POW(_,_,_)
 case POW(i,p,q) => i > 0 && normal(p) && normal(q) && p != POW(_,_,0)
}

```

Assume we have some type `shfn` to say that we have a `shf` with the normality property. Then also define these functions:

```
def pop(i: nat, p: shfn) = {
 case i = 0 or p = const(_) => p
 case p = POP(j,q) => POP(i+j,q)
 case _ => POP(i,p)
}

```

Denote nat\* the naturals without zero:

```
def pow(i: nat*, p: shfn) = {
 case p = 0 => pop(1,q)
 case p = POW(j,r,0) => POW(i+j,r,q)
 case _ => POW(i,p,q)
}

```

Finally, define the addition operation:

```
if (x = const(c1)) {
 if(y = const(c2))       c1+c2 (over the integers)
 else if(y = POP(i,p))   POP(i,x+p)
 else if(y = POW(i,p,q)) POW(i,p,x+q)
}

if(y = const(c)) y+x

if(x = POP(i,p) && y = POP(j,q)){
 if(i=j)        pop(i,p+q)
 else if(i > j) pop(j,POP(i-j,p)+q)
 else if(i < j) pop(j,POP(j-i,q)+p)
}

if(x = POP(i,p) && y = POW(j,q,r)){
 if(i=1) POW(j,q,r+p)
 else    POW(j,q,r+POP(i-1,p))
}

if(y = POP(i,p) && x = POW(j,q,r)) y+x

if(x = POW(i,p,q) && y = POW(j,r,s)){
 if(i=j)        pow(i,p+r,q+s)
 else if(i > j) pow(j,POW(i-j,p,0)+r,q+s)
 else           pow(i,POW(j-i,r,0)+p,s+q)
}

```

**The problem**

I'm trying to prove that if $x,y$ are normal then $x+y$ is also normal. But the induction is not trivial to me.

I tried to split it. First I consider $x$ to be constant and everything went well by using the corresponding induction hypothesis.

The problem appears when I consider $x$ to be $POP$ and I do induction on $y$. When $y$ is also $POP$ I have to rely on the $POW$ case because note that as $x,y$ are normal and instances of $POP$ then their second components need to be instances of pow. The other cases for this situation then need the $POP-POW$ case. But proving the $POP-POW$ case could potentially lead to a $POP-POP$ case again.

How can I structure my proof to succeed?

You may want to look at the actual proof on ACL2 here. Also, if you have any ideas to simplify the problem (to make it more easy to reason about and describe it) please let me know.

**Intuition**

Intuitively a POP construct represents a jump in the list of variables where our shf form is evaluated and a POW represents a polynomial in current variable x of the form $x^i \cdot p + q$. So normality for POP means that the jumping index is as big as possible (there cannot be nested POPs) and normality for POW means the power index $i$ is as big as possible.

# Answer
> 2 votes
You need to use induction on some complexity measure $\mu(x,y)$ (on some well-ordered domain) which has the following property:

> When running the addition procedure on $x,y$, all recursive calls are on pairs $z,w$ for which $\mu(z,w) \< \mu(x,y)$.

A complexity measure satisfying this property shows that the addition procedure terminates, and will also allow you to do a proof by induction. Note that you are *not* splitting into cases according to the coarse structure of $x,y$.

It is often the case that you can take $\mu(x,y)$ to be the total description length of $x,y$, so you might start by checking whether this works here. Another possibility is to take the sum of the total degrees of all monomials in $x,y$.

Finally, how should you approach the problem? I suggest forgetting about the formalism (in particular, ignoring POP completely) and writing out the simplification steps in their barest forms. Using $N(p,q)$ for the normal form of $p+q$ (themselves already in normal form), the rules are:

* $N(c\_1,c\_2) = c\_1+c\_2$.
* $N(c,x\_i^jp+q) = x\_i^jp+N(c,q)$.
* $N(x\_i^{j\_1}p\_1+q\_1,x\_i^{j\_2}p\_2+q\_2) = x\_i^{j\_2}N(x\_i^{j\_1-j\_2}p\_1+0,p\_2)+N(q\_1,q\_2)$, where $j\_1 \> j\_2$.
* $N(x\_i^jp\_1+q\_1,x\_i^jp\_2+q\_2) = x\_i^jN(p\_1,p\_2)+N(q\_1,q\_2)$.
* $N(x\_{i\_1}^{j\_1}p\_1+q\_1,x\_{i\_2}^{j\_2}p\_2+q\_2) = x\_{i\_1}^{j\_1}p\_1+N(q\_1,x\_{i\_2}^{j\_2}p\_2+q\_2)$, where $i\_1 \< i\_2$.

Here we are conflating POP and POW, which makes things a littler more concrete.

We want to prove that these rules are correct, namely:

> If $p,q$ are in normal form then $N(p,q)$ terminates, is in normal form, and agrees as a function with $p+q$.

This can be split into several tasks. First, assuming that $p,q$ are in normal form, show that they match exactly one rule. Second, show that in each recursive invocation $N(r,s)$ on the right-hand side, (i) $\mu(r,s) \< \mu(p,q)$, and (ii) $r,s$ are in normal form. Third, show that the right-hand side agrees with $p+q$ as a polynomials (using the inductive hypothesis). Fourth, show that the right-hand side is in normal form (again using the inductive hypothesis).

Proving that the addition procedure as given is valid is similar, only we need to take into account the different encoding which separates POW and POP.

---
Tags: cryptography, induction, software-verification
---


# Question
Title: If a language L is regular then the given operation sort(L) is context free
I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it:

Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in an ascending order. Sort(L) is the outcome language of the operation Sort(w) on each and every string (w) in the language L. I was asked to prove or disprove the following claim:

> If L is a regular language over the alphabet {0,1} where 0\<1 then sort(L) is context free.

I would appreciate any hints or clues on how to approach this type of question.

# Answer
The way to solve this sort of question is using your problem-solving skills. Here are three ways to approach this question:

* Take some DFA (or NFA) for $L$. Now construct a PDA for $\mathsf{sort}(L)$ along the following lines. The PDA starts by reading $0$s, pushing them into the stack. At some point it switches to a second phase in which it only accepts $1$s. At each step it first pops an arbitrary number of $0$s from the stack and feeds them to the DFA, and then reads the next $1$ if any, feeding it to the DFA. It accepts if after processing all the $0$s in the stack and all the $1$s in the input, the DFA is in an accepting state.
* Take a left regular grammar for $L$ (so the rules are of the form $A\to\epsilon$, $A\to a$, and $A\to a B$), and replace $A\to 1B$ with $A\to B1$. The result is a context-free grammar for $\mathsf{sort}(L)$.
* Parikh's theorem states that $\mathsf{sort}(L)$ is of the form $$ \bigcup\_{i=0}^m \\{ 0^{x\_i+n\_1 y\_{i,1}+\cdots+n\_{\ell\_i} y\_{i,\ell\_i}} 1^{z\_i + n\_1 w\_{i,1} + \cdots + n\_{\ell\_i} w\_{i,\ell\_i}} : n\_1,\ldots,n\_{\ell\_i} \geq 0 \\}, $$ where $x\_i,y\_{i,j},z\_i,w\_{i,j} \geq 0$. It's not hard to check that all languages of this form are context-free, for example by constructing a context-free grammar.

Note how all of these approaches rely on the alphabet being binary. The language $(012)^\*$ shows that this assumption is necessary. (Similarly, the language $(01)^\*$ shows that $\mathsf{sort}(L)$ need not be regular.)

Parikh's theorem implies that for languages over the binary alphabet, $\mathsf{sort}(L)$ is context-free whenever $L$ is context-free (that is, we don't need to assume that $L$ is regular, it suffices to assume that it is context-free). You can try proving this fact directly.
> 4 votes

---
Tags: automata, finite-automata, pushdown-automata
---


# Question
Title: Is union of context-free and non-context-free languages non-context-free?
It is known that union of two context-free languages is also context-free.

But how about union of context-free and non-context-free languages?

# Answer
Not in general. Consider a language $L$ over some alphabet $\Sigma$ such that neither $L$ nor its complement $\overline{L}$ is a decidable language. It is obvious that neither of these languages can be context-free. But $L \cup \overline{L} = \Sigma^\*$, which is a context-free language.

And consider $\emptyset$, which is trivially a context-free language. Clearly $L \cup \emptyset = L$ is not a context-free language.
> 3 votes

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


title: functional programming in terms of Set

text:
# Question
Title: functional programming in terms of Set
I'm writing some notes about functional programming, so I'd want to describe some features of the category theory.

I visited wiki page about Category of Set, and I found this:

*"The epimorphisms in Set are the surjective maps, the monomorphisms are the injective maps, and the isomorphisms are the bijective maps".*

I'd want to explain Category theory it in term of computer science, so my question is:

* It's correct to consider only the category of Set?
* It's correct to consider only the category of Set when I explain functional programming in term of Monoid/Functor/Algebraic Data/Product type and so
on?

I know that Category theory is not only Set, but It's important for me define a boundary where all my examples are correct on assumptions and definitions.

thanks Mike.

# Answer
> 5 votes
You can use the category of sets as your model of how functional programming works as long as you do not allow general recursive definitions.

To see why general recursion is not valid in the category of sets, consider the following program (written in Haskell):

```
fix :: (Bool -> Bool) -> Bool
fix f = f (fix f)

```

If we interpret `Bool` as any set $B$ with at least two elements (for instance $B = \\{0, 1, \bot\\}$) then there will be a map $f : B \to B$ which does not have a fixed point (for instance $f(0) = 1$, $f(1) = \bot$, $f(\bot) = 0$). However, `fix` always computes fixed points.

You can use sets as long as all the recursive definitions are well-founded, i.e., the recursive calls always happen on strictly smaller arguments. Typical `fold` and `map` operations on lists and other inductively defined structures are like that.

To model recursion one has to change something. One possibility is to use domains which were invented precisely for this purpose.

# Answer
> 4 votes
A typical mindset would be to consider *them* separate categories:

1. Category of types and programming functions
2. Category of sets and set functions

We can then ask questions such as:

* Is there functors between them?
* Do they both have product, coproduct, endofunctors...?
* Can they be made Cartesian closed categories?

Why separate them? It is more flexible. Depending on your idea of functional programming or specific programming language, sooner or later, you might spot the differences. For a mundane example, maybe the initial object and terminal object in your programming language is the one and only null type, but you know that this is not the case the the category $Set$.

On the other hand, $Set$ is a perfectly fine place to *do programming inside*. You can define what is Boolean, natural number, conditional statements ... inside $Set$. (Actually, except for general recursion. See Andrej Bauer's answer for this)

# Answer
> 1 votes
Generally, programming languages only make use of a *single* category - the category of all available types. If the type system is sufficiently simple, we may take that category to be Set; but usually it is just some arbitrary category of types. We can still talk about Monoids/Functors/Natural Transformations etc, but use just a single category in those definitions. For example, all functors in programming (type constructors) are endofunctors.

N.B. I am not an expert in category theory

# Answer
> 0 votes
> I'd want to explain Category theory it in term of computer science, so my question is:
>
> * It's correct to consider only the category of Set?
> * It's correct to consider only the category of Set when I explain functional programming in term of Monoid/Functor/Algebraic Data/Product type and so on?

I believe you mixed up 2 questions.

1. How to explain category theory in terms of computer science?
2. How to explain computer science in terms of category theory?

Question 2 was addressed in other answers, so I will focus on Question 1.

Suppose you consider only the category of sets and functions when teaching category theory. I would not say that this method is incorrect because "correctness" does not make sense in this context to me. I would say that it is **useless**. As an abstract branch of mathematics, category theory consists of *theories* (examples: category, monoidal category, category with finite products) and *models* of those theories (examples: the category of sets, categories of algebraic structures, categories of domains). Any theorem deduced from a theory is true for every model of that theory. Cost–benefit analysis of this approach follows.

* Benefit. The approach saves thought, so to speak. If we know $n$ models of a theory, every proof yields $n$ theorems instead of $1$.
* Cost. Theories lie on the next level of abstraction. Abstraction is hard.

The more models, the more useful is the theory. No need to dive into category theory if you wish to reap the benefits of abstraction. Abstract algebra, order theory, topology, and other branches were built on the same principle.

After this long prelude, I hope it is clear why I called it useless. If you consider only the category of sets, $n=1$. The benefit is 0, but the cost still exists. The whole point of abstraction is lost. If you do not need the benefits of abstraction, why stress yourself with abstraction? In this case, why explain or learn category theory in the first place?

# Answer
> 0 votes
Thanks for all answers. What I thought is that category of Set was 'similar' (Arrgh! when I speak with mathematicians every word may be not correct) than the others. In programming languages, objects are types and morphisms are functions so I thougtht that the category of Set was ok, except for general recursion. Now I understand that the right way is the category of all available types. I like to know how define mono and epic morphisim in terms of category of all available types. It's clear for me the means in the category of Set, because the injectivity and surjectivity are strictly related to the monomorphism and epimorphism, but not in category of all available types. Probably I have to study!

Now, what I want to describe in my document is a little bit of theory or abstraction if you prefer, related to a functiona programming objects. Example:

Each type A in Hask is transformed to TC\[A\]. List\[Int\] is a type constructor then a functor is F: Int → List\[Int\]

So to explain about Functor (endofunctor) and what 'preserve the stucture' is meaning, the category theory comes in handy.

The same for Product/Coproduct when I want to explain Algebraic Data Type.

Mike.

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


# Question
Title: Necessary and sufficient condition for unique minimum spanning tree
This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees \[Fa’13\].

> Prove that an edge-weighted graph $G$ has a unique minimum spanning tree if and only if the following conditions hold
>
> * For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.
> * The maximum-weight edge in any cycle of $G$ is unique.

Consider the "$\Rightarrow$" direction and the following graph $G$.

$G$ has a unique MST. However, for the partition $\\{A\\}$ and $\\{B,C\\}$, the minimum-weight crossing edge is *not* unique.

> Did I misunderstand some points? Or if there are flaws in the theorem, how can we fix it?

# Answer
> 0 votes
Answer my own question by simply copying the comment made by @JeffE, the author of the lecture note：

> Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) – JeffE

---
Tags: graphs, spanning-trees
---


# Question
Title: Nearest neighbour based on subjective human comparison - is this a thing?
I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into...

I have a collection of items that I would like to have a human subjectively compare such that I can derive some consistent dataset that can be queried for k nearest neighbours for a given item that is present in the data.

i.e. if I ask a human, given item A, which item is most similar, B or C (repeated over a set of such items)

I can later present back, when queried, here are the items most similar to A.

The desire is simply to record a person's subjective comparisons of a set of items and have a means to allow them to query it.

Any pointers as to algorithms or structures to read up on would be greatly appreciated.

# Answer
## Distance metric learning

It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items. If the human tells you that A is more similar to B than to C, then you learn that $D(A,B) \< D(A,C)$ (probably). Based on many instances of this, you can learn a distance metric $D(\cdot,\cdot)$. Then, you can use $k$-nearest neighbors with this distance metric.

## Overview

How does distance metric learning work? Well, you can do a search and you'll find a lot of material. Basically, you identify some features that you think might be relevant. So, let $f(A)$ denote the feature vector associated to $A$. Then you want to learn a distance metric of the form

$$D(A,B) = d(f(A),f(B))$$

where $d : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ is the distance function that you want to learn. There are various methods for this. In one of them, we assume that $d$ takes the form

$$d(x,y) = (x-y)^\top A (x-y)$$

where $A$ is some positive semidefinite matrix that is to be learned. The training set gives us comparisons of the form $d(x\_A,x\_B) \< d(x\_A,x\_C)$, i.e.,

$$(x\_A-x\_B)^\top A (x\_A-x\_B) \< (x\_A-x\_C)^\top A (x\_A-x\_C).$$

You could then form a convex optimization problem of the form

minimize $||A||\_F$

subject to $A \succeq 0$ and $(x\_A-x\_C)^\top A (x\_A-x\_C) \< (x\_A-x\_B)^\top A (x\_A-x\_B)$ for all $x\_A,x\_B,x\_C$ in the training set.

Here $||A||\_F$ is the Frobenius norm. Also $A \succeq 0$ means that $A$ is positive semidefinite). (This can be expressed by writing $A=M^\top M$ and using the entries of $M$ as your unknowns, though sometimes it is easier to leave it in the form $A$.) Then we apply some algorithm for convex optimization to learn $A$ or $M$.

That's one example of a method; there are many others. For instance, you might add a margin to the inequality above, and require that $d(x\_A,x\_B) \< d(x\_A,x\_C)-1$ (so they are well-separated).

The effectiveness will be partly determined both by the metric learning method you use, but the set of features you come up with are also extremely important. You'll want to use your domain knowledge about what attributes of items might be relevant or helpful in determining similarity. If you have good features, you'll probably find that distance metric learning is more effective.

## To learn more

There are many schemes for distance metric learning. A websearch and a search on Google Scholar should turn up a bunch of candidates. You want to learn a distance metric from *relative comparisons*. See also https://en.wikipedia.org/wiki/Similarity\_learning.
> 2 votes

---
Tags: nearest-neighbour
---


# Question
Title: Do all NP complete problem have polynomial verifier?
Say we want to factor a large number.

Factoring it is in NP.

Verifying it is definitely in P.

However, how do we know that there is no other factors besides the one we found?

So it seems that verifying it isn't in NP either.

Now I am getting confused with NP definition here. I know that NP includes all P.

But then there is this side definition that NP are problems with polynomial verifier.

Is there a proof that all NP problems have P verifier?

If the answer is true, yes all NP problems and hence all NP complete problems have P verifier, then please tell me the proof.

# Answer
> 18 votes
A problem is in NP if and only if it has a polynomial verifier – that's the definition of NP. All NP-complete problems are in NP – that's part of the definition – and so have a polynomial verifier.

Factoring is not a decision problem, so it neither belongs to NP nor doesn't belong to NP. You can turn Factoring into a decision problem in many ways, for example asking if the $i$th bit of the $j$th factor of $n$ is equal to $b$. In that case a witness will be the list of factors of $n$. We can check that the factors multiply to $n$, and that they are all prime (since primality testing is in polynomial time).

(We are using here the *unique factorization* theorem, stating that a positive integer can be factored as a product of primes in a unique way. The same property doesn't hold in some more general situations.)

It is suspected that the decision problem corresponding to Factoring is *not* NP-complete, though it is certainly in NP, as the preceding paragraph shows.

# Answer
> 1 votes
Veryfying means that you have factored number correctly.

If you have factored number $C$ as $C = A\_1 * A\_2 * ... * A\_n$ you can check if it's right by simply calculating ${\displaystyle \prod\_{i=1}^{n} A\_i}$ and testing if all $A$ are primes in polynomial time.

# Answer
> 1 votes
The N in NP stands for non-deterministic, the P for polynomial.

An non-deterministic polynomial algorithm can be expressed as a verifier where each choice for a non-deterministic step is part of the input. Simulating that is polynomial in the number of steps taken.

This means that every NP problem has a polynomial verifier.

---
Tags: complexity-theory
---