Questions tagged [history]

Questions about genesis and development of computer science as a scientific discipline and its applications.

Filter by
Sorted by
Tagged with
96
votes
5answers
14k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
73
votes
2answers
7k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the term?...
44
votes
5answers
13k views

Why has research on genetic algorithms slowed?

While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on ...
38
votes
7answers
3k views

What is the definition of Computer Science, and what is the Science within Computer Science?

I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to ...
31
votes
2answers
2k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
28
votes
2answers
2k views

How are programming languages and foundations of mathematics related?

Basically I am aware of three foundations for math Set theory Type theory Category theory So in what ways are programming languages and foundations of mathematics related? EDIT The original ...
23
votes
7answers
66k views

Why do we need assembly language?

We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with ...
22
votes
4answers
4k views

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
21
votes
1answer
718 views

What are the first computer science papers that used asymptotic time complexity?

When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, Big Omicron and Big Omega And Big Theta, SIGACT April-June 1976, but the ...
18
votes
1answer
3k views

Who coined the term “machine learning”?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
17
votes
5answers
2k views

What is the earliest use of “trees” in computer science?

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.
17
votes
4answers
5k views

Did 'Eugene Goostman' really pass the Turing test?

It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test. ...
16
votes
4answers
2k views

Why did RSA encryption become popular for key exchange?

This is a soft question. I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g....
15
votes
2answers
612 views

What is the origin of λ for empty string?

I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$. I think $\varepsilon$ is derived from the word "...
15
votes
2answers
910 views

Why is Turing completeness right?

I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can ...
15
votes
1answer
483 views

Who are the legislators of Paxos?

In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol. According to this ...
13
votes
3answers
3k views

What is the origin of the client server model?

I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
13
votes
1answer
313 views

Random Access Machines with only addition, multiplication, equality

The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they cannot be simulated by Turing machines in polynomial time can solve PSPACE-complete ...
11
votes
2answers
2k views

Importance of recursion in computability theory

It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?
11
votes
1answer
208 views

How did 'Isabelle' (the theorem prover) get its name?

The title says it all, but I'm curious because it isn't obvious how a theorem prover came to be named 'Isabelle'. Was it named for a person? I couldn't find out by some Google searches.
11
votes
2answers
3k views

Why is the laplace transform not popular for image processing convolution?

Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.
10
votes
1answer
120 views

What did Turing's mysterious small programme on the Manchester computer calculate?

I am reading Turing's "Computing machinery and intelligence" paper (https://www.csee.umbc.edu/courses/471/papers/turing.pdf) and found a fragment in which he says: I have set up on the Manchester ...
9
votes
4answers
2k views

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...
8
votes
1answer
126 views

Origin of the concept of types

About the state of art that I'm running ahead of Type Theory I have the these questions all related about history of Types. Where did the idea of Type come from? (It seems that all start when ...
7
votes
2answers
129 views

Who (and when) first defined interval graphs?

I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949. So, I'm trying to track down the original paper ...
7
votes
1answer
607 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...
7
votes
1answer
657 views

Historical relation between computer science and the theory of dynamical systems

I have asked this question at math.stackexchange, but I have been redirected here. My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such ...
7
votes
0answers
333 views

What was the first public reference to bloom filters where the number of hash functions vary?

In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter. This idea is ...
7
votes
0answers
127 views

Evolutionary theory applied to programming languages

I'm looking for books applying evolutionary theory to the history of programming languages. Researching the topic I have found an interesting paper - Modelling the Evolution of Programming Languages ...
6
votes
3answers
369 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
6
votes
2answers
825 views

Don Knuth and MMIXAL vs. Chuck Moore and Forth — Algorithms and Ideal Machines — was there any cross-pollination / influence in their ideas / work?

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms? I'm interested in citations, ...
6
votes
2answers
2k views

Richard Karp's 21 NP-Hard problems, the meaning of his research?

In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some ...
6
votes
1answer
132 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...
6
votes
3answers
1k views

How did it happen that Algol 60 was an improvement on its successors?

The original statement referred to by this question is: The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration ...
6
votes
1answer
348 views

What was the first programming language with loop break?

While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL. Algol _? -> CPL -> BCPL -> C -> C++ -> Java -> JavaScript What ...
6
votes
1answer
681 views

What is the origin of dot notation?

In object-oriented programming, dot notation is used when accessing the properties or methods of a class: ...
6
votes
1answer
172 views

Who first introduced the pushdown automaton?

I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
6
votes
1answer
107 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
6
votes
0answers
91 views

Where did our present regex notation originate?

First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base. Where did our present regex notation originate? I am particularly wondering how <...
5
votes
5answers
1k views

Why call it 'Time Complexity'?

P.S. I have added the tag 'history', if there is any historical connotation. Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
5
votes
2answers
100 views

Why is the word “calculus” used to describe systems of logic and computation?

Why is the word "calculus" used in this context? The reason I ask is because these usages of "calculus" seem unrelated to the far more popular use of "calculus" in "differential calculus" and "...
5
votes
1answer
160 views

Origin of quantum complexity theory

Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?
5
votes
1answer
176 views

Who conceived the concept of Discrete Event Simulation, and when?

I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of discrete-...
5
votes
2answers
153 views

When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?

It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and "...
5
votes
0answers
69 views

Which languages, if any, implemented parametric polymorphism before ML?

In particular, was there any kind of implementation at the time Christopher Strachey wrote Fundamental Concepts in Programming Languages? In that work, Strachey lists Ad Hoc and Parametric ...
4
votes
1answer
739 views

Official Name for the “First” Programming Language Developed by Turing?

As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions ...
4
votes
4answers
592 views

How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?
4
votes
1answer
109 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
4
votes
1answer
228 views

Why the name Recursively Enumerable and Recursive? [duplicate]

Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?
4
votes
1answer
77 views

Does the concept of the array pre-date physical computer memory implementations?

Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations? I am trying to gauge whether ...