Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

14
votes
0answers
265 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
1answer
120 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
1answer
71 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 ...
5
votes
0answers
114 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 ...
9
votes
1answer
181 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
1answer
236 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 ...
4
votes
2answers
160 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 ...
14
votes
1answer
745 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 ...
12
votes
0answers
221 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 ...
2
votes
0answers
90 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
3answers
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 "...
9
votes
1answer
1k 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 ...
12
votes
1answer
1k 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-...
3
votes
3answers
463 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 ...
15
votes
1answer
503 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 ...
22
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 ...
11
votes
2answers
788 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 ...
39
votes
1answer
517 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 ...
27
votes
3answers
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
1answer
189 views

who found out Theory of Computer Science? [closed]

who first started to analyse computers theoretically ? who gave birth to Theory of Computation ?
75
votes
2answers
8k 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 ...
8
votes
0answers
561 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
1answer
625 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
2answers
476 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
2answers
935 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 ...
82
votes
7answers
26k 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/...
19
votes
2answers
2k 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
233 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,\...
7
votes
1answer
221 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
250 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 ...
3
votes
0answers
228 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 \...
18
votes
5answers
2k 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 ...
33
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
167 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
166 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
2k 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
398 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
1k 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
470 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 ...
13
votes
0answers
259 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 ...
17
votes
1answer
651 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 ...
27
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
245 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 ...
26
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 ...
34
votes
8answers
10k 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
4answers
1k 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
229 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
2k 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
584 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
216 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 ...