The history behind the topics: where their name comes from, who discovered them, when they were first proved, how they evolved during the years.
15
votes
5answers
746 views
Why economists should care about computational complexity
When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and ...
23
votes
2answers
1k views
Reference for NP-hardness of 3-colouring?
I have a historical question.
I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard.
The tempting answer ...
4
votes
1answer
119 views
Lambda: The Ultimate Imperative - who is Jensen?
One of the notes in the classical paper LAMBDA: The Ultimate Imperative says:
{Jensensdevice}
The technique of repeatedly modifying a variable passed call-by-name in order to produce side ...
0
votes
2answers
100 views
iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation
A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
2
votes
2answers
453 views
Why were Finite Automata and Turing Machines created?
It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
11
votes
2answers
266 views
Why is the state of a FSM traditionally denoted $q$?
While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is ...
5
votes
6answers
379 views
Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?
This guy asserts:
I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics.
(This problem being Entscheidungsproblem - ...
11
votes
0answers
439 views
Looking for a quotation by Edsger Dijkstra
In one of his papers Edgser Dijkstra makes a statement like:
"What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
11
votes
0answers
207 views
First use of sans serif for complexity classes
(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...)
It seems that it has become popular in recent years to ...
14
votes
1answer
389 views
Who introduced the complexity class AC?
I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$.
The official explanation is that the "A" stands for "Alternation".
I vaguely remember being told ...
23
votes
10answers
1k views
Probabilistic (randomized) algorithms before “modern” computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In ...
7
votes
4answers
166 views
Early References for Transition System Semantics of Programs
I am trying to trace back the origins of transition system semantics for imperative programs. I am assuming a transition system is a tuple $(\mathit{States}, \mathit{Trans})$ consisting of a set of ...
14
votes
0answers
434 views
Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?
I'm sure everybody know's of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.
The implementation of the algorithm in computers ...
23
votes
8answers
3k views
Alan Turing's Contributions to Computer Science
Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
11
votes
3answers
408 views
Alan Turing Documentaries
To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life. However, there are several documentaries to choose from.
Which documentary about Alan Turing is your favorite?
...
6
votes
1answer
163 views
Origin of Church encodings
In which paper did Alonzo Church first describe Church encoding? I can't find any articles that actually cite the paper, but I am interested in reading it.
10
votes
2answers
516 views
The Relation between Babbage and von Neumann
It is well known that Charles Babbage's analytical machine had an architecture strongly ressembling the modern Von Neumann architecture.
Also, it's notable that the tables for representing a program ...
12
votes
4answers
323 views
The origin of the terms “efficient” and “feasible” computation/algorithm
I would like to know about the history of these two terms: "efficient", "feasible".
Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
...
13
votes
1answer
168 views
Early history of certain results on space-time tradeoffs?
I'm interested in the early history of published results on general-purpose space-time tradeoffs. In particular, I want to know who first described the following type of algorithm for evaluating a ...
13
votes
3answers
664 views
Is the concept of the Turing Machine derived from automata?
I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?
I didn't know the answer of course, but ...
9
votes
2answers
253 views
Early references for discrete optimization
(Apologies if this is misplaced or too broad. I'm open to suggestions on how to reformulate it.)
I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete ...
30
votes
2answers
807 views
“Steve's class”: origin of SC
We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse ...
15
votes
1answer
563 views
Why are regular languages called “regular”?
Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.
I suppose that, in the beginning, ...
6
votes
0answers
267 views
Use of calculus of variations
Have results from the calculus of variations been used previously in TCS?
2
votes
1answer
500 views
Why have computer scientists chosen recursor instead of iterator in primitive recursion?
I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more ...
10
votes
2answers
217 views
Exhibits for a Museum of Computing
All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science.
You are involved in the creation of a ...
24
votes
10answers
2k views
If you could rename dynamic programming…
If you could rename dynamic programming, what would you call it?
27
votes
4answers
1k views
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
4
votes
1answer
476 views
Why is the “free store” memory called the “heap”? [closed]
Does it have anything to do with the heap data structure, for example the Buddy blocks implementation, or does it only take the literal English meaning of the word (a big pile)?
I know heap memory is ...
2
votes
1answer
271 views
Using compression to improve edit distance computation
I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common ...
26
votes
5answers
863 views
Historical reasons for adoption of Turing Machine as primary model of computation.
It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more ...
25
votes
2answers
491 views
Papers to credit for spectral partitioning of graphs
If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity
$\phi(S) := \frac {Edges(S,V-S)}{d\cdot ...
33
votes
13answers
2k views
Applications of topology to computer science
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It ...
17
votes
2answers
743 views
Why Ramanujan graphs are named after Ramanujan?
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?
29
votes
7answers
2k views
What is the oldest open problem in TCS?
This problem is inspired by this MO question, which I thought was very interesting.
What is the oldest open problem in TCS?
Clearly this question needs some clarification.
First, what is TCS? ...
17
votes
2answers
738 views
Origins and applications of Theory A vs Theory B?
In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of ...
8
votes
3answers
650 views
About recursion
Where did the idea of recursion originated from? I mean first who thought about it.Can anybody care to explain about the origin of recursion and subsequent impact on the computer science?
11
votes
1answer
320 views
What are the historical roots of Milner's bigraphs?
Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested. They generalise process calculi like CCS and the $\pi$-calculus, but Milner ...
