Skip to main content
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,479
62 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
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
  • 161k
13 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
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.9k
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
  • 12.1k
12 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
  • 30.5k
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,102
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

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

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

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,233
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
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,102
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.9k
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.8k
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,098
7 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,237
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
5 votes
Accepted

When did "regular" start referring to Type 3 languages/grammars?

I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language ...
cristoper's user avatar
  • 181
5 votes

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

I posted the following in answer to the same question on CS Theory a couple of years ago: A calculus is just a system of reasoning. One particular calculus (well, actually two closely related ...
David Richerby's user avatar
5 votes
Accepted

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

The word calculus comes from the Latin word for limestone, because limestone pebbles were used for counting; you may have a renal calculus: a kidney stone$^1$. In mathematics, the word is used to ...
Lieuwe Vinkhuijzen's user avatar
5 votes

Who first introduced the pushdown automaton?

Ginsburg (in his book The Mathematical Theory of Context-Free Languages, McGraw-Hill, 1966) states in the Historical References (Section 2.7, page 81): Pushdown acceptors were first formalized by ...
Hendrik Jan's user avatar
  • 30.8k
5 votes

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

The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why foreign languages would affect the American Standard ...
Yufan Lou's user avatar
  • 138
5 votes

Why is the address-of operator in C/C++ represented with the "&" symbol?

Because B did! A user on software engineering.sx contacted Ken Thompson: From: Ken Thompson c copied from b so & and * are same there. b got * from earlier languages - some assembly, bcpl and i ...
Pål GD's user avatar
  • 16.7k
5 votes

Why do combinators look this way?

The combinators $K$ and $S$ first appear in Moses Schönfinkel, Über die Bausteine der mathematischen Logik, though he calls them $C$ and $S$. He actually defines five combinators, $I,C,T,Z,S$, and ...
Yuval Filmus's user avatar
5 votes

Is the reason for a stack to decrease the size of a program (by adding the use of subroutines)?

The reason for having a stack is recursion. You don’t need a stack if you don’t have recursion. CDC super computers in the 70s worked just fine without a stack - until they implemented Pascal. On ...
gnasher729's user avatar
  • 30.5k
4 votes

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

Here's a thought. Consider the venerable spreadsheet. No, not the program, but the piece of paper. It was a regular array of cells, with column and row check sums and corner balancing for verification....
Peter Camilleri's user avatar
4 votes
Accepted

Machine code and punched cards

You normally started by entering a little loader program one word at a time by setting the bits with a line of toggle switches on the front panel, like this: Wikipedia has a bit of explanation of the ...
rici's user avatar
  • 12.1k

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