Questions tagged [ho.history-overview]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
93 views

Is there a name for the class of languages based on reversible circuits, as studied by the physicists of the late 70's/early 80's?

I'm interested in the (pre)history of quantum computing, especially in light of the work of physicists and engineers who studied reversible computing in the 60's through the late 70's/early 80's. ...
19 votes
0 answers
745 views

Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?

There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first ...
4 votes
1 answer
156 views

Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?

According to this paper by Barbara Liskov, CLU was "The first implemented programming language to provide direct linguistic support for data abstraction". She then defines "data ...
4 votes
0 answers
74 views

When was the dynamic array first used as an example for amortized analysis?

I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
3 votes
1 answer
290 views

Are there two definitions of Cobham's thesis?

In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states: computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time So ...
8 votes
0 answers
178 views

Where is Yao's original proof that distinguishers imply next-bit-predictors?

In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...
2 votes
0 answers
86 views

When did self-balancing binary search trees become known outside the soviet union?

According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis. The earliest self-balancing binary search tree I can find by a non-soviet block ...
33 votes
12 answers
5k views

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below: The original algorithms,...
11 votes
1 answer
290 views

When was co-NP introduced for the first time?

My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
2 votes
1 answer
137 views

Who proved that a triangulation is 3-colourable implies its dual is bipartite

Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent: (i) $...
16 votes
6 answers
747 views

When have we found better bounds for known algorithms?

Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - ...
8 votes
3 answers
1k views

Are there any intersections between Theory A and Theory B?

In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division ...
3 votes
1 answer
952 views

Are Turing machines still useful as model of computation?

Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s. But when I'm forced to think about a Turing ...
5 votes
0 answers
152 views

Why is the Toffoli Gate named after Toffoli?

I was reading the following paper: Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, Volume 5, Issue 3, July 1961. On page 4, ...
66 votes
5 answers
6k 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 ...
17 votes
0 answers
604 views

Did von Neumann answer to Gödel's letter?

On 20 March 1956, Kurt Gödel wrote a famous letter to John von Neumann, in which he formulated the P versus NP question. Here is a link to that letter: [pdf of letter] I cant seem to find John von ...
9 votes
1 answer
196 views

System F and System T names

Does anyone know where do the names System "F" and System "T" comes from? I am not asking who introduced those names (Girard System F, and Gödel System T), but what the "F" and the "T" means.
1 vote
1 answer
81 views

Searching for the original definition of online algorithms

I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the ...
6 votes
0 answers
250 views

reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected ...
94 votes
7 answers
30k 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 functions/...
41 votes
1 answer
636 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 ...
8 votes
1 answer
235 views

Was counting complexity first introduced by Valiant in 1979?

Was #P first introduced in [1]? [1] Valiant, Leslie G. "The complexity of computing the permanent." Theoretical computer science 8.2 (1979): 189-201.
11 votes
1 answer
277 views

Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it ...
3 votes
0 answers
239 views

Providence of pumping lemmas for regular languages

I'm looking to track down who discovered the following pumping lemmas for regular languages. (where $p$ is the pumping constant.) Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \...
4 votes
2 answers
237 views

Characterisation of P in terms of register machines

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ...
13 votes
1 answer
838 views

Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

I am looking for: Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960 Summary: “We attempt to measure ...
29 votes
1 answer
2k 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, ...
67 votes
14 answers
17k 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 ...
22 votes
2 answers
3k 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 ...
13 votes
0 answers
251 views

historical question: earliest description of beta-normal terms together with "neutral" terms in lambda calculus?

A bit of "folklore" in lambda calculus is the idea of characterizing the class of $\beta$-normal terms inductively as a syntactic category ($R$) defined in mutual induction with an auxiliary syntactic ...
15 votes
5 answers
4k views

History of recursion

Who introduced the idea of recursion? Can someone explain where it came from and how it impacted computer science?
2 votes
0 answers
94 views

Advances in complexity by studying particular problems

When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (...
20 votes
3 answers
2k views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" or "...
88 votes
2 answers
12k 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 ...
9 votes
1 answer
2k views

Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time ...
14 votes
1 answer
2k 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 Simply-...
4 votes
3 answers
629 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 ...
13 votes
2 answers
1k 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 ...
15 votes
1 answer
638 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 ...
23 votes
2 answers
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 ...
35 votes
8 answers
11k 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, ...
13 votes
4 answers
2k 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? ...
28 votes
3 answers
3k 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
1 answer
200 views

who found out Theory of Computer Science? [closed]

who first started to analyse computers theoretically ? who gave birth to Theory of Computation ?
12 votes
2 answers
343 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 $\{(_1,\ldots,(_k,)_1,\...
8 votes
0 answers
669 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 ...
26 votes
1 answer
729 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 ...
19 votes
2 answers
611 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 ...
28 votes
2 answers
1k 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 ...
26 votes
1 answer
2k 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 ...