Questions tagged [computer-science]
For questions about the scientific approach to computations and its applications.
90
questions
13
votes
2
answers
4k
views
Who coined the term "signal-to-noise ratio" and when did statisticians start using the term "noise" to describe randomness?
I'm writing about the history of the concept of noise and am having trouble tracking down references from when the term "noise" started being associated with statistical noise such as ...
- 235
9
votes
1
answer
719
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,027
11
votes
1
answer
467
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 Gödel's research on the length of proofs under certain axiomatic systems.
Does Blum's speedup theorem have any ...
- 107
0
votes
0
answers
117
views
Who invented bit permutations like shuffle, butterfly and bit-reversal?
This question is about a class of periodic permutations,that are produced by applying finite permutations to the binary digits of all integers.
In lack of a better name, they shall be called bit ...
- 101
4
votes
2
answers
586
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 ...
- 56
1
vote
1
answer
211
views
What are some examples of galactic algorithms that have become practical?
On the Wikipedia article for galactic algorithm (an algorithm that only becomes efficient when the inputs are so large that the algorithm is not used in practice), one of the use cases is that
...
- 151
0
votes
0
answers
93
views
Technical analysis of von Neumann's contributions to computing?
I have seen the book The Annotated Turing and I found it quite nice to understand the ideas of Alan Turing. Are there similar books for understanding von Neumann's ideas in computing?
- 407
0
votes
0
answers
95
views
When did mathematical logic start being applied in/ with computer science?
I am going through articles about Turing machines which were introduced to solve the entscheidung problem by Alan Turing in 1936. To what I understand, all modern computers are essentially Turing ...
4
votes
1
answer
122
views
How the present technology influences the way history of science is done?
Heard recently about digital humanities as a new paradigm of inquiry into the history of mankind and other humanities. Is the historiography of science informed by technological advances that could ...
- 343
5
votes
2
answers
126
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 ...
- 146
3
votes
1
answer
107
views
Historical examples of frauds discovered because someone tried to mimic a uniform random sequence
So, I'm preparing a talk about the well known fact that humans are bad at the task of generating uniformly random sequences of numbers when asked to do so.
I would like to spice the talk a bit by ...
- 47.6k
5
votes
0
answers
97
views
What was Gauss's algorithmic method to solve a certain "nearest neighbour search" problem in multi-dimensional euclidean space?
In his 1829 paper on a new formulation of mechanics, Gauss presented his principle of least constraint, which parallels previous formulations of analytical mechanics and provides a new point of view ...
- 407
3
votes
0
answers
298
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
17
votes
2
answers
1k
views
The Abacus vs. the Electric Calculator (Nov 12, 1946): Why did the latter lose?
On Nov 12, 1946 the Americans organized a contest in Japan to compare the Japanese Abacus with the American Electric Calculator. The Abacus won:
"Civilization, on the threshold of the atomic age, ...
- 21
2
votes
1
answer
2k
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 ...
- 909
1
vote
0
answers
65
views
What effect were used for manufacturing HDD before 1988?
I understand Hard disk present before 1988
and I came to know that Giant magnetoresistance effect used in applications in Hard Disk manufacturing and this effect is discovered in 1988
So what effect ...
- 11
16
votes
2
answers
926
views
What happened to cybernetics?
Recently, I've been looking into the life of the brilliant Norbert Wiener and the field he spawned, cybernetics. Before reading into it, I thought "cybernetics" was a pseudo-science-new-wave-...
11
votes
0
answers
359
views
How were contour plots of complex functions produced in the days of mechanical differential analyzers?
I was reading an old paper (specifically, the first appearance of the Pearcey function, here) and I was struck by the beauty of the plots it contains, particularly for a paper from 1945-46:
Pearcey ...
- 762
7
votes
0
answers
360
views
What is 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 ...
- 592
5
votes
0
answers
143
views
Early parallel computing with human exchanging messages: is this story true?
As a student in applied maths, I can remember being told that in the 1940s there were early attempts of parallel computing not using any machine but only human calculation power.
I believe the story ...
- 1,039
3
votes
0
answers
133
views
Has Turing's invention of Turing machines contributed to the development of real computers?
Has Turing's invention of Turing machines contributed to the development of real computers, which resulted in the personal computers we currently use?
I often saw it mentioned that this is an ...
- 1,039
3
votes
0
answers
172
views
Who were the major thinkers before Turing to ask whether machines can think? How come Turing's Test lasted as the influential one?
Turing Test has often been referred to both in academia and outside it when talking about AI. Yet there were I suppose many more thinkers except for Turing, possibly Descartes among them, that dealt ...
- 1,039
4
votes
1
answer
339
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 ...
- 1,039
21
votes
3
answers
1k
views
What happened to analog computers?
When was the last analog computer developed? What about one that is still in use (as in computation or experiment)? Were there major improvement done from the day digital computers became so popular?
- 1,039
5
votes
2
answers
2k
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 ...
- 1,039
31
votes
1
answer
3k
views
Was object oriented programming influenced by the mathematical category theory?
Object oriented programming (OOP) is a programming model where code and data are encapsulated into units called objects that behave semi-autonomously. Interaction between objects is arranged through ...
- 1,039
1
vote
0
answers
82
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,039
6
votes
0
answers
394
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 ...
- 231
2
votes
1
answer
728
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 ...
- 400
0
votes
0
answers
83
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 ...
- 135
7
votes
0
answers
103
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)?
- 358
5
votes
0
answers
52
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. ...
- 517
1
vote
0
answers
156
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 ...
- 254
2
votes
1
answer
124
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 ...
- 73.4k
2
votes
1
answer
188
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 ...
- 3,613
5
votes
1
answer
156
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?
- 73.4k
5
votes
1
answer
521
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+...
- 1,174
2
votes
1
answer
164
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 ...
CommunityBot
- 1
16
votes
3
answers
2k
views
Why did Norbert Wiener break off relations with Walter Pitts?
I read on the Wikipedia page on Walter Pitts that Norbert Wiener broke off relations with Walter Pitts, which "sent Walter Pitts into 'cognitive suicide'".
Why did Norbert Wiener break off relations ...
- 1,039
8
votes
0
answers
151
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,039
10
votes
1
answer
902
views
Why is the Halting problem attributed to Alan Turing?
The halting problem is a very famous example from computability theory of a problem that is undecidable. It is often said that the proof of its undecidability was given by Alan Turing, indeed ...
- 1,039
12
votes
1
answer
583
views
Did Turing know of Babbage's work?
Did Turing have any knowledge of Babbage's work? Is it known if he ever mentioned Babbage?
- 1,039
1
vote
1
answer
2k
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 ...
5
votes
1
answer
260
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 ...
- 400
7
votes
2
answers
494
views
What mathematician or scientist has published the most peer-reviewed articles on chess problems?
This question involves not only those provided by the link, but also those "chess-themed" mathematics and computer science problems which are not included in the link. Who has published the most peer-...
- 549
7
votes
1
answer
127
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 ...
- 5,951
1
vote
1
answer
132
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 ...
- 1,516
9
votes
1
answer
1k
views
The origin of logic gate symbols
Who first proposed the distinctive shapes and the rectangular shape labels?
What is the consideration behind the shapes and the labels?
- 836
10
votes
1
answer
364
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."
- 73.4k
1
vote
2
answers
264
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 ...
- 2,147