The history behind the topics: where their name comes from, who discovered them, when they were first proved, how they evolved during the years.

learn more… | top users | synonyms

6
votes
1answer
628 views

Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and ...
1
vote
3answers
321 views

Why is lambda calculus so “function” oriented?

I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function? It ...
12
votes
1answer
270 views

Why was Schönfinkel's work on eliminating “bound variables” in logic so crucial?

AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
19
votes
2answers
2k views

What was the original intent for the creation of Lambda calculus?

I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church ...
8
votes
2answers
523 views

How exactly does lambda calculus capture the intuitive notion of computability?

I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"? "Intuitively" I get the computability model of Turing ...
29
votes
0answers
304 views

Does Rabin/Yao exist (at least in a form that can be cited)?

In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function ...
24
votes
3answers
2k views

Impact of Grothendieck's program on TCS

Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's ...
-2
votes
1answer
166 views

who found out Theory of Computer Science? [closed]

who first started to analyse computers theoretically ? who gave birth to Theory of Computation ?
47
votes
2answers
4k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
7
votes
0answers
486 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
25
votes
1answer
529 views

Rabin–Karp vs Karp–Rabin

The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that ...
17
votes
2answers
340 views

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has ...
25
votes
2answers
696 views

Kolmogorov's conjecture that $P$ has linear-size circuits

In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
64
votes
7answers
22k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with ...
17
votes
1answer
1k views

Why did Kolmogorov publish Karatsuba's algorithm?

Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy ...
12
votes
2answers
192 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
7
votes
1answer
176 views

Measurability of an $\omega$-regular language

It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I ...
2
votes
0answers
209 views

Unary subset sum

Who can be attributed with the discovery or invention of the unary subset sum algorithm which is known to have polynomial time complexity but exponential space complexity. I am currently writing a ...
1
vote
0answers
146 views

Providence of pumping lemmas for regular languages

I'm looking to track down who discovered the following pumping lemmas for regualar languages. (where $p$ is the pumping constant.) Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in ...
17
votes
5answers
1k 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 ...
32
votes
2answers
3k 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
148 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 ...
-1
votes
2answers
143 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 ...
4
votes
2answers
940 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 ...
12
votes
2answers
317 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 ...
6
votes
6answers
661 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 - ...
12
votes
0answers
459 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 ...
12
votes
0answers
237 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 ...
16
votes
1answer
456 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 ...
25
votes
10answers
2k 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
224 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 ...
24
votes
1answer
1k views

Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

I'm sure everybody knows 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 ...
31
votes
8answers
6k 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, ...
12
votes
4answers
909 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? ...
7
votes
1answer
206 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
941 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 ...
13
votes
4answers
432 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). ...
14
votes
1answer
198 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 ...
16
votes
3answers
899 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
271 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 ...
31
votes
2answers
970 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 ...
20
votes
1answer
709 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
301 views

Use of calculus of variations

Have results from the calculus of variations been used previously in TCS?
3
votes
1answer
666 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
234 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 ...
37
votes
11answers
3k views

If you could rename dynamic programming…

If you could rename dynamic programming, what would you call it?
47
votes
5answers
2k 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
918 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
297 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 ...
35
votes
5answers
1k 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 ...