Hot answers tagged

85 votes
Accepted

What does the "Lambda" in "Lambda calculus" stand for?

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated ...
Anton Trunov's user avatar
  • 3,469
61 votes
Accepted

What is the earliest use of the "this" keyword in any programming language?

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years. It also used the this keyword for the same ...
Brian Tompsett - 汤莱恩's user avatar
45 votes
Accepted

Is there any reason why the modulo operator is denoted as %?

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, ...
Foo Bar's user avatar
  • 536
20 votes

Why are computable functions also called recursive functions?

The founders of computability theory were mathematicians. They founded what is now called computability theory before there was any computers. What was the way mathematicians defined functions that ...
Kaveh's user avatar
  • 22.2k
17 votes
Accepted

Why are computable functions also called recursive functions?

Define some basic functions: zero function $$ zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0 $$ successor function $$ succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1 $$ ...
Auberon's user avatar
  • 1,314
14 votes
Accepted

Why did RSA encryption become popular for key exchange?

There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA. So why RSA? As far as I can tell, non-technical historical reasons ...
D.W.'s user avatar
  • 158k
13 votes

What is the earliest use of "trees" in computer science?

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they ...
David Richerby's user avatar
13 votes

Is there any reason why the modulo operator is denoted as %?

This is very likely a historical development. Looking at this table, we see that C was likely the first language to use % for modulo. Its predecesor BCPL used ...
Andrej Bauer's user avatar
  • 30.4k
12 votes

What is the origin of λ for empty string?

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics. Chomsky used $I$ as ...
Jouni Sirén's user avatar
12 votes

What was Robert Floyd's algorithm for inserting brackets?

The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today. ...
rici's user avatar
  • 12k
12 votes

Which Turing Award winners have supervised the PhDs of other Turing Award winners?

Consulting with the Mathematics Genealogy Project, I was able to find the following thesis advisor relationships: John Hopcroft (1986) advised Alfred Aho (2020) Martin Hellman (2015) advised ...
mhum's user avatar
  • 2,032
11 votes

What is the earliest use of "trees" in computer science?

According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS. H. G. Kahrimanian, Analytical Differentiation by a Digital ...
A.Schulz's user avatar
  • 12.2k
11 votes
Accepted

Why call it 'Time Complexity'?

Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define ...
Yuval Filmus's user avatar
11 votes

Why the 127 encodings of ASCII needed to be extended to 256?

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 ...
gnasher729's user avatar
  • 29.4k
11 votes

Mathematical benefit to use CPU/memory that increases by powers of 2 as 8-bit, 16-bit, 32-bit, 64-bit, etc?

Multiplying and dividing binary integers by powers of 2 is very cheap, like multiplying and dividing by 10 for decimal numbers. It's qualitatively different from other factors because the other bits ...
Peter Cordes's user avatar
  • 1,055
10 votes
Accepted

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

A little google-fu (and my own memory) tells me it was apparently named by Larry Paulson after Gerard Huet's daughter. Gerard Huet happens to be one of the people behind the less poetically named Coq ...
cody's user avatar
  • 8,154
10 votes

Why did RSA encryption become popular for key exchange?

Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a ...
Jacen's user avatar
  • 1,040
10 votes

What does the "Lambda" in "Lambda calculus" stand for?

here is some other near-firsthand info/ angle on this by Church student Dana Scott as just reported by Ghica and documented in a youtube video.[1] He says that when Church was asked what the ...
vzn's user avatar
  • 11k
10 votes
Accepted

What was the first programming language with loop break?

I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote: "CPL did have a break command to cause an exit from a repetitive command ...
mlhaufe's user avatar
  • 311
10 votes
Accepted

What is the origin of dot notation?

In [1] (authored by one of the co-creators of Simula), there is a suggestion that Simula 67 may have been the first to use this dot notation. Given that Simula is widely credited for being the first ...
mhum's user avatar
  • 2,032
10 votes
Accepted

Lambda Calculus as a branch of set theory

It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of ...
Andrej Bauer's user avatar
  • 30.4k
9 votes

What is the origin of λ for empty string?

Probably the notation originates from the "Finnish school". My copy of 'Formal Languages' by Arto Salomaa (Academic Press, ACM monograph series, 1973) uses $\lambda$ for the empty string. And so does ...
Hendrik Jan's user avatar
  • 30.5k
9 votes
Accepted

Why are struct and class essentially the same in C++?

Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1): At this point, the object model becomes real in the sense that an object is more than the simple aggregation of ...
HEKTO's user avatar
  • 3,088
8 votes
Accepted

How did each class of languages receive their name?

Regular Languages: There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name Context-Free vs Context-Sensitive Grammars: For CFGs and CSGs, ...
mdxn's user avatar
  • 1,301
8 votes

Why are computable functions also called recursive functions?

Robert Soare wrote an essay about this issue. According to him, the term (general) recursive functions was coined by Gödel, who defined them using some sort of mutual recursion. The name stuck, though ...
Yuval Filmus's user avatar
7 votes

What is the earliest use of "trees" in computer science?

Isaiah: ""And there shall come forth a rod out of the stem of Jesse, and a Branch shall grow out of his roots" The tree as a data model for genealogical information is very ancient indeed.
Michael Kay's user avatar
7 votes
Accepted

Who are the legislators of Paxos?

This is an educated guess of the transliterated names I could find in the Paxos paper. Most of these are people mentioned in the paper's references. Λ˘ινχ∂: Lynch, N. - Legislator Φισ∂ερ: Fischer, M. ...
GEL's user avatar
  • 829
6 votes
Accepted

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

The symbol $q$ to denote the state of a finite automaton appears (for the first time??) in Moore's 1956 paper Gedanken-Experiments on Sequential Machines and since the paper became very popular, I ...
J.-E. Pin's user avatar
  • 6,129
6 votes
Accepted

Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

A large part of what is known goes unpublished, when it is considered trivial. What counts as trivial is, of course, different in different times and for different communities. For instance, we do not ...
André Souza Lemos's user avatar
6 votes

Why the 127 encodings of ASCII needed to be extended to 256?

There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle. English has words with diacritical marks, ...
kviiri's user avatar
  • 1,227

Only top scored, non community-wiki answers of a minimum length are eligible