Questions tagged [history]

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

Filter by
Sorted by
Tagged with
10 votes
7 answers
6k views

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

Historically, processors often increase in bit-size by powers of 2, such as 8-bit, then 16-bit, 32-bit, 64-bit. Although this has not always been the case, it is a well known trend. One benefit is ...
0 votes
1 answer
39 views

Good books about the history of computer science and its pioneers?

I have read a book ‘Men of Mathematics’ by Eric Temple Bell, which includes the development of mathematics through ages and the biography of famous mathematicians . I am looking for such an history ...
0 votes
1 answer
43 views

Computability = Enumerating a sequence in the particular order?

In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
0 votes
0 answers
59 views

What is the earliest compiler in chain that was used to create what we nowadays have as a modern C compiler?

My apologies if the title is confusing. First I begin with the statement that may be wrong but what I always thought what happened. "Dennis Ritchie created C compiler which was used to create ...
3 votes
0 answers
184 views

What is the etymology of "swizzle"?

The word swizzle can refer to an operation performed in GPU algorithms: [The] ability to compose vectors by arbitrarily rearranging and combining components of other vectors. Swizzle (computer ...
4 votes
2 answers
516 views

Origin of "Cookie" in Computing?

"Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997. Many ...
2 votes
0 answers
44 views

Has Triangle Finding ever been faster than Matrix Multiplication?

The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
1 vote
0 answers
33 views

Did Jon von Neumann know about Claude Shannon's work when he wrote the "First Draft of a Report on the EDVAC?"

In the "First Draft" JvN described an adder circuit to do binary addition, which was a much faster way of doing computer addition than using decimal lookup tables as the ENIAC had done. JvN'...
1 vote
4 answers
205 views

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

The stack allows subroutines to be used. It can store return address for "return from subroutine" instruction (RTN) and also arguments for the function. It is not possible to store return ...
2 votes
1 answer
80 views

Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?

This is probably a computer science history question. Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?
1 vote
4 answers
483 views

Why is C still the fastest? Critique my take

A friend and I were surprised that C still has near-best performance among languages. I thought about why this is, and I wrote up a few paragraphs. I wonder if the friendly folks on CS stack could ...
5 votes
0 answers
202 views

Why did the Mathematica Language choose term rewriting instead of the Lambda Calculus as its basis? [closed]

Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda ...
8 votes
2 answers
154 views

Does the concept of "side-effect" predate functional programming?

When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
2 votes
2 answers
91 views

Why do combinators look this way?

Out of curiosity, why do combinators look this way? For example, why is $K = \lambda x y \to x$ and why is it called $K$? Why is it not $\lambda x y f m \to f m x$? These are just arbitrary letters, I ...
1 vote
0 answers
55 views

First piece of code in scientific papers

What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
7 votes
3 answers
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
1 answer
1k views

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

John McCarthy won the Turing Award in 1971 [1]. Two students whose PhD he supervised went on to win Turing Awards: Raj Reddy (1994) [2] Barbara Liskov (2008) [3] What other Turing Award winners ...
0 votes
0 answers
28 views

SMP operating system that had been "proven" to be bug free?

Many years ago someone told me about a historical SMP operating system (or program?) that had been all but proven to be bug free (or something close to this). But yet turned out to have bugs that were ...
1 vote
2 answers
86 views

Who said first "In practice, log log N is at most (single digit number)?"

In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like In practice, $\log(\log(N))$ is at most 9. ...the idea being that even though the ...
31 votes
2 answers
3k 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 ...
2 votes
0 answers
28 views

History of the category of effectful computations

The 1971 paper A Catalog of Optimizing Transformations contains this passage: irreducible subprograms require special handling. (An irreducible subprogram is one which maintains a history, performs I/...
1 vote
1 answer
44 views

Oldest publication of the lower bound on comparison sort

We all know that the worst case complexity for comparison sort is in $\Omega(n\log(n))$, but who was the first to publish this? Everywhere I look, people have their own proofs but no reference to the ...
3 votes
0 answers
19 views

What is the historical origin of the concept of a "clipping path"

Algorithms for clipping lines to a rectangle seem to have been invented by Ivan Sutherland in the late 60s. At some point the rectangle was generalized to an arbitrary polygonal area, and these days ...
7 votes
0 answers
70 views

P=NP turns 50. 1971 STOC conference

Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case ...
3 votes
0 answers
130 views

What is a good general-knowledge-level title description of Dr. Aho's and Dr. Ullman's body of work for which they were awarded the 2020 Turing Award?

I recently read in the New York Times that my old "Data Structures and Algorithms" class professor Dr. Ullman had received the Turing Award along with Dr. Aho. The article title was "...
5 votes
1 answer
355 views

What was Robert Floyd's algorithm for inserting brackets?

In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
3 votes
0 answers
90 views

What happened to Active Databases?

When reading the literature on declarative programming technology. A particular technology that sounded promising is active databases. It essentially allows the programmer to specify rules about data ...
3 votes
1 answer
165 views

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

I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) ...
14 votes
3 answers
4k 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)?
3 votes
1 answer
164 views

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

In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes ...
1 vote
0 answers
57 views

How close are current computer technologies in terms of energy efficiency to the Landauer Limit?

I'm trying to figure out how close (in orders of magnitude) current computer technologies are in terms of energy efficiency to the Landauer Limit. However, I'm finding (seemingly) conflicting ...
26 votes
3 answers
6k views

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

I would like to know if there is any reason why many programming languages use the notation % for the modulo operator? It is used in the most "famous" ...
9 votes
2 answers
495 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 ...
0 votes
0 answers
49 views

How did we go from Binary to something like Python?

If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
4 votes
1 answer
388 views

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

The title says it all, I think. We know there are universal Turing-machines that only use a binary alphabet. But who proved this first? Turing himself showed the existence of a universal Turing ...
2 votes
0 answers
37 views

Is the discrepancy in Turing's representation of complete configurations intentional?

On page 235 of Turing's 1936 paper, in the figure marked (C), the illustration appears not to match the description. The description states that space has been made on the left of the scanned symbol, ...
0 votes
0 answers
18 views

Term for language that abstracts program location?

What is the technical term that describes a programming language that abstracts (or at least largely abstracts) the machine location of programs? I’m thinking here specifically of the evolution of ...
3 votes
0 answers
47 views

What was the impact of Impagliazzo's A Personal View of Average Case Complexity?

I'm studying his paper and I was wondering how the community reacted to it. Yes, Average Case Complexity has come a long way since then, but I want to know if it was directly influenced by it.
0 votes
1 answer
544 views

Who invented the adder, full-adder, half-adder?

I didn't find, in the digital design books, who invented the adders. The same person invented the half-adder and the full-adder? What's the oldest publication on digital arithmetic design?
1 vote
0 answers
27 views

Origin of GUI terminology

I'm wondering where the GUI terminology like modal dialogue comes from. Who first used these terms? Is there a paper or a book, or was it just sw?
4 votes
2 answers
144 views

Origin of using ">" to represent child in a tree

What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child e.g. ...
8 votes
3 answers
2k 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 ...
54 votes
1 answer
11k views

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

I understand the this (or self or Me) is used to refer to the current object, and that it is ...
0 votes
3 answers
2k views

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

As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages". I still ...
3 votes
0 answers
90 views

What is the first programming language where the keyword "new" appeared?

It's really interesting when this keyword first appeared as a lot of popular languages but relatively old languages( C++, C#, Java, JS ) use it. I understand use of "new" in C++ in practical manner( ...
1 vote
1 answer
288 views

Famous hacker koan: who was it about, though?

Read this many years ago and can't remember who it was about. Nor can I remember the exact quote. The story goes: Famous computer scientist/professor is teaching a class. Student is having some ...
2 votes
0 answers
47 views

Similarities between Babbage's difference engine and the Turing machine

What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
106 votes
5 answers
18k 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....
2 votes
0 answers
23 views

When did our current concepts of program modularity develop?

I take it that the concept of a modular subroutine call/return existed prior to the concept of a call stack (and hence to the possibility of recursive subroutines or of recursion limits). I would ...
4 votes
1 answer
489 views

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

struct and class in C++ are nearly identical (as covered for example here). But why is this so? What did happen when C++ was ...