Hot answers tagged

85

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 clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...


60

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 concept, which can be seen in this book chapter extract: class Linker; begin ref(Linker) Next, Sex, Employment; text ID; procedure Add_to_List(LHead); name LHead; ref(Linker) LHead; ...


46

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, hence the operator's ubiquity. Why did Thompson and Richie pick %? It had to be a printable ASCII character that wouldn't conflict with B's other features. % was available, and it resembles the / ...


34

Why do we need assembly language? Well, there's actually only one language we will ever need, which is called "machine language" or "machine code". It looks like this: 0010000100100011 This is the only language your computer can speak directly. It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also ...


20

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 could be computed? By recursive definitions! So there were recursive function before there were any other model of computation like Turing machines or lambda ...


18

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that ...


16

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 $$ projection function $$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i $$ From now on I will use $\bar{x_n}$ to denote $(x_1, x_2, \...


14

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 dominated. RSA was patented and there was a company behind it, marketing and advocating for RSA. Also, there were good libraries, and RSA was easy to understand and ...


13

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 originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than,...


13

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 rem, and older languages such as Fortran, Algol, Lisp, and Cobol did not use %. But that's just my uninformed guess.


11

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 Computer, Symposium on Automatic Programming, 6–14, 1952 K.E. Iverson and L.R. Johnson, IBM Corp. research reports RC-390, RC-603, 1961 A.J. Perils and C. ...


11

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 the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty ...


11

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 as follows: The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. ...


11

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. The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose ...


11

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 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters. Nowadays people mostly ...


10

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand why and when polynomial algorithms became of interest. I especially focus on the sub-question: When did people realize the role and importance of efficient versus non-efficient algorithms? Because algorithms, in ...


10

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 few trusted parties who store public keys. If you want to connect to your bank, you can ask the trusted party (let's say Verisign) for the bank's public key, as ...


10

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 theorem prover. Small world!


10

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 meaning of the λ was, he just replied “Eeny, meeny, miny, moe.“, which can only mean one thing. It was a random, meaningless choice. Prof. Scott claimed that the ...


10

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 Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.


9

I think the prizes you're referring to are the Loebner Prize. According to the Wikipedia page (see prior link), the winner for 2014 is 'Rose' by Bruce Wilcox. That program did not win one of the one-time-only prizes, but did get $4,000 in prize money. 'Eugene Goostman' competed in 2005 and 2008, finishing second both times. The competition 'Eugene Goostman'...


9

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 such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967." [...]...


9

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 OO language, it may be tricky to find an earlier example specifically in an OO context. EDIT: On DiscreteLizard's suggestion in comments, I took a peek at the ...


9

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 the data members of a class. An object of a C++ class with a virtual function is a fundamentally different beast from a simple C struct. Then why did I not ...


8

He laid down the foundations to understanding "computing" from a mathematical perspective. His paper about what is today called the Turing Machine shows his reflections on a model, in mathematical terms, of how the human_brain/thought_process works. Based on that, he develop a theory of computation (with the aim of automating math thinking; kind of similar ...


8

Turing machines are not programmable. Each Turing machine computes only one function. Hence they do not use any programming language. What you see as a language is the description of the machine itself, not of a program in some programming language. Thus the name "Turing machine" is the only appropriate terminology. Now it turns out that there are devices ...


8

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 later on other equivalent definitions were found. For more information, I recommend Soare's essay.


8

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, the "context" part is the idea that certain rules can be extended to apply based on relative positions of symbols rather than on single specific symbols. ...


8

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 his 1969 book 'Theory of Automata' (Pergamon Press). We move back. The classic 'Finite Automata and Their Decision Problems' by M.O. Rabin and D.Scott (April ...


7

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. J. - Legislator Tωυεγ: Toueg, S. - Legislator Ωκι: Oki, B. M. - Legislator ∆ωλεφ: Dolev, D. - Farmer Σκεεν: Skeen, M. D. - Merchant Στωκµε˘ιρ: Stockmeyer, L. - ...


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