Questions tagged [computer-science]

For questions about the scientific approach to computations and its applications.

Filter by
Sorted by
Tagged with
1
vote
0answers
62 views

When were brains seen as computers for the first time?

Let me state firstly that I don't think that the nervous system is a computer. Not down up, nor top down. On top of that, brains cannot truly be separated from the body. I am curious still. Who were ...
5
votes
0answers
164 views

What is the source of Donald Knuth's remark about naming programming languages?

(This question toes the line between belonging here and belonging on the Retrocomputing Stack Exchange.) Here is the quote; sometimes the first sentence is omitted: The most important thing in a ...
0
votes
0answers
41 views

Derek Oppen and the Nelson-Oppen combination procedure

Derek Oppen was a student of Stephen Cook known for the Nelson-Oppen combination of decision procedures method. Yet, there is no Wikipedia entry dedicated to him and his publication list extends ...
7
votes
0answers
58 views

What was the first automated theorem prover?

From a lot of googling, it seems like the answer might be "Mizar", but I am not completely sure. What was (or is?) the first automated theorem prover (i.e. not necessarily active right now)?
4
votes
0answers
31 views

Are there other articles by Ada Lovelace than translation of Menabrea's notes on Analytical Engine?

Ada Lovelace is well known as an translator of Luigi's Menabrea article on Babbage's Analytical engine. She also added notes to the translation which are in the end longer than the translation itself. ...
3
votes
0answers
95 views

Where does the term “arm's-length recursion” come from?

I've recently seen the term "arm's-length recursion" for a recursive method with a check that short-circuits the method's true or intended base case. What's the origin of this term? How did ...
1
vote
0answers
143 views

The mathematics of multiple values

tl;dr Why has the array paradigm, which emerged in the 1950s and 60s amongst mathematicians, and which underpins certain programming languages, apparently failed to capture and maintain interest ...
4
votes
2answers
531 views

How did Von Neumann come up with his Merge Sort algorithm?

Since merge sort is the first $O(n\log n)$ time general purpose sorting algorithm I find it rather surprising that it was discovered without having any obvious conceptual predecessors. Are there any ...
2
votes
1answer
72 views

Where does the term “pivot” come from in the quicksort algorithm?

The quicksort algorithm is based on recursively choosing an element to partition the array. In every modern exposition that I've seen, this element is called the "pivot". However, as far as ...
6
votes
0answers
134 views

What was Holon Programming?

Donald Knuth credits Pierre-Arnoul de Marneffe's idea of "Holon Programming" as the main influence on Literate Programming. See page 13 of "Literate Programming", Knuth's paper ...
5
votes
1answer
96 views

Was Charles Sanders Peirce aware of Charles Babbage's difference engine?

Is there any indication that Charles Peirce was aware of Babbage and his work on mechanical computing?
1
vote
1answer
156 views

Was a work of Ada Lovelace and Charles Babbage inspiration for pioneers of modern computing?

Recently, I came across a book about Grace Hopper where it is stated that Howard Aiken wanted her to become familiar with papers by Ada Lovelace and Charles Babbage as he considered some of Babbage's ...
7
votes
1answer
288 views

Does Blum's speedup theorem have any conceptual predecessors?

Blum's speedup theorem seems to me that bears at least some superficial resemblance to Godels research on the length of proofs under certain axiomatic systems. Does Blum's speedup theorem has any ...
4
votes
1answer
198 views

Why so hard to find references to pictures of Raymond Boyce?

Raymond Boyce was one of the first pioneers of the relational database and a co-developer of SQL, yet it is almost impossible to find any pictures of him: https://www.google.com/search?q=raymond+f+...
4
votes
2answers
248 views

How did Yao come up with his minimum spanning tree algorithm?

I recently stumbled upon this text about Yao's algorithm for the minimum spanning tree (MST) and I was wondering if there are some preceding algorithms (other than Sollin's algorithm) that were ...
2
votes
1answer
60 views

Did Kolmogorov complexity influence the development of communication complexity?

I was reading a wikipedia article about communication complexity and it seems to me that it bears some resemblance to Kolmogorov complexity. Was the founder of communication complexity influenced by ...
2
votes
1answer
117 views

Origins and reason for Volume A and B divide in Theoretical Computer Science

At some point in history, theoretical computer science emerged as a sub-discipline of computer science. Later, apparently it segregated into "volume A" work and "volume B" work. This can be seen for ...
6
votes
1answer
110 views

Origin of O/L for false/true in German computer-science texts

In Konrad Zuse's Plankalkül ZIA ID 0020 from 1972, in his patent submission Z23624 "Rechenmaschine" ZIA ID 0177 from 1936 and modern German Wikipedia article on the dyadic system, 2020-01-17 we see L ...
1
vote
1answer
89 views

When did the study of the rate of convergence of algorithms begin?

I was reading a book about computational complexity theory and the author made a claim that the study of time complexity of algorithms started with a result on the upper bound on the number of ...
10
votes
1answer
273 views

What is the first reference to a nondeterministic Turing machine?

I am looking for the first reference of a Nondeterministic Turing machine. There is no mention of them in the 1936 paper "On Computable Numbers."
8
votes
0answers
129 views

When did computer pioneers realize that some problems are intrinsically hard?

In my theory computation class, I was told that early computer pioneers didn't realize that some problems are intrinsically hard—what we now call NP-hard problems. Instead, it took a while to realize ...
1
vote
2answers
248 views

Can you provide pages 7, 8, 25 of the 1969 edition of the Art of Computer Programming?

A paper published in 1975 references The Art of Computer Programming (then published in 1969), so it's probably the first edition. I can't even find this edition for sale anywhere. Would you be so ...
1
vote
0answers
53 views

Is there a reason $⊑$ in CSP is analogous to $⊇$ (as opposed to $⊆$)?

The 'square' subset symbols are sometimes used to express analogous concepts to subsets, like prefixes or suffixes. However their use in CSP seems to be counterintuitive to their shape: $⊑$ appears ...
3
votes
1answer
252 views

What is the origin of “banana brackets”?

"Banana" brackets are used to denote catamorphisms: Another notation found in the literature is . These symbols are very similar to the composition of a $($ and a $|$, is this similarity ...
2
votes
1answer
230 views

How did Lenna become the most used image in image processing?

$Lenna$ despite being an playboy model posing nude here and there, is one of the most used images for image processing. How she came into the world of image processing? Was it done intentionally by ...
4
votes
1answer
123 views

When has the notion of “programming language for machines” emerged?

Nowadays, it seems just common sense to write a program in a high-level programming language and let it be compiler (or interpreted) into machine code to run a computer. However, when did the ...
4
votes
1answer
270 views

Why would Margaret Hamilton and her team at NASA print the code on paper?

This famous photo depicts Margaret Hamilton, leader of the software engineering team for the Apollo Project, next a print out of the code she and her team wrote for the mission. This information is ...
4
votes
1answer
185 views

Why was the 'differential entropy' from information theory so named?

The entropy of a distribution $p$ on a discrete set $\mathcal{X}$ is defined as $$H(p) = -\sum_{x \in \mathcal{X}} p_x \log p_x.$$ Shannon in his classic paper [1] defines the analogue for continuous ...
5
votes
1answer
259 views

Can we fairly assess Ada Lovelace's talent for mathematics?

Dorothy Stein, a biographer of Ada Lovelace, was pretty blunt in her assessment: Lovelace was a mediocre mathematician, for example see here. I wonder if she's fair to her. The fact that Lovelace ...
2
votes
0answers
78 views

In left- or right-rotation for arrays, where did those conventions for the directions come from?

This is a repost from another exchange. I was going to write a paper about code to rotate elements in an array, but I realized I have no idea why rotation towards the start of the array is “left” ...
1
vote
1answer
452 views

What technologies were used before JavaScript?

I made a small research about the history before JavaScript was available to use, but I couldn't find much. I only found several plugins that was used, such as Adobe Flash, ActiveX. So, what I want ...
5
votes
0answers
75 views

Where is the first reference to the “Z combinator”, a call-by-value fix-point combinator?

I'd like to know the earliest reference to the Z-combinator. This could be either where the name was first coined, or even the first discussion of a need for an applicative-order Y combinator. I didn'...
0
votes
0answers
49 views

Frege alluded to a logic algorithm?

Somewhere (I wish I remember where) I read that Gottlob Frege, although he didn't invent a logic algorithm, alluded to one (the Quine–McCluskey algorithm? something else? converting truth tables to ...
5
votes
1answer
52 views

When was the first appearance of the abbreviation RSA?

When was the first publication of the abbreviation RSA (Rivest, Sharmir, Adleman) because it does not appear in Martin Gardner’s article of 1977 which is at the following url: https://simson.net/ref/...
8
votes
3answers
589 views

Did amateurs ever produce important proofs or similar?

Background Mathematics and some areas of physics and computer science have the peculiar appeal that some problems and results are easy to understand and it is conceivable that somebody armed with ...
6
votes
0answers
338 views

Was there an intentional purge of all audio recordings of Alan Turing?

The YouTube video Alan Turing's lost radio broadcast rerecorded contains a re-enactment of Alan Turing's lecture broadcast by the BBC. In the introduction, the narrator (James Grimes, also of the ...
1
vote
0answers
58 views

When was the Server Side Include feature of web servers first made available?

Server Side Include (SSI) is a specific concept and related feature of web servers. See https://en.wikipedia.org/wiki/Server_Side_Includes When was this feature first introduced? The Wikipedia ...
1
vote
1answer
1k views

Who first invented the programmable digital computer?

I read Charles Babbage invented the first mechanical computer (the Analytic Engine) and that Ada Lovelace devised the first computer programs. Also I realize John Von Neumann invented the first ...
1
vote
0answers
66 views

Gentzen and computer science

This is a cross-post from mathstack: https://math.stackexchange.com/questions/2584003/gentzen-and-computer-science?noredirect=1#comment5333947_2584003 I would like to learn a bit about the ...
1
vote
0answers
30 views

How was the “train on 70% of data” convention established?

It's common in machine learning to train on 70% of non-validation data, testing on the remaining 30%. I'm not sure whether the motive for this is theoretical or "empirically this works well", although ...
2
votes
0answers
84 views

Why is $\eta$ used in $\eta$-conversion?

In lambda calculus there are three types of reduction, $\alpha$-renaming $\beta$-reduction $\eta$-conversion The use of $\eta$ in $\eta$-conversion seems rather strange to me. Since they already ...
5
votes
1answer
184 views

Who coined the term “machine learning”?

A lot of sources attribute the definition to Arthur Samuel (1959), "the field of study that gives computers the ability to learn without being explicitly programmed", but none of these sources ...
0
votes
0answers
50 views

Tri-nary processor?

Every now and then, I run across a rumor of the Soviets building a tri-nary processor, way back when. But I can never find a source beyond the infamous guy who knows a guy... The idea is interesting,...
3
votes
0answers
132 views

Etymology of 'qubit'; is there any relation to cubits?

Whilst several not-very-authoritative sources e.g. Wikipedia state that the word qubit was derived, partially, as a play on the word cubit (obviously it also stands for 'quantum bit'), is there any ...
3
votes
1answer
208 views

Entscheidungsproblem vs. Unvollständigkeitssatz

The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it ...
4
votes
1answer
121 views

What did Tim-Berners Lee mean with “HTTP also allows index search” in his paper “World wide web: The Information Univesrse”?

For my work on the history of hypertext systems and the WWW I cam across one sentence on the development of HTTP which I don't understand and where I could not find any information about: Page 55: (...
1
vote
0answers
65 views

Grey Walter and Norbert Wiener Regarding Holism

Grey Walter writes: ``Even in the very simplest system, with two active elements, multiple interconnection between elements give several modes for which simple observation is useless. The study of ...
1
vote
0answers
99 views

What is the relationship between constructivism and object oriented programming?

I am exploring the topic of constructivism from discreet math, and think it is related to object oriented programming. Can anyone confirm or deny the two are related?
0
votes
1answer
965 views

Did Albert Einstein write a computer program?

I am curious whether or not Albert Einstein wrote a computer program. Did he write a computer program?
5
votes
0answers
87 views

Was the Vigenère cipher broken many years before Kasiski?

The Vigenère cipher was broken by Kasiski in 1863 but I read novels and romans from older time, for example during the French Revolution where a student broke Vigenère cipher. Is it likely that ...