Questions tagged [computer-science]
For questions about the scientific approach to computations and its applications.
101 questions
0 votes
0 answers
75 views
Scientific concepts that are named after their inventor "by coincidence"
In theoretical computer science, PPAD is a class of computational problems. The official interpretation of the term is an acronym: Polynomial Parity Arguments on Directed graphs. However, by an ...
2 votes
0 answers
117 views
Was Erdős the source for characterizations involving machines that convert coffee?
There is a familiar mock characterization often attributed to Erdős Pál to the effect of Definition. A mathematician is a machine for turning coffee into theorems. In one of my grad courses in CS, ...
- 657
2 votes
1 answer
120 views
What are the origins of the symbols used to denote levels of the arithmetic hierarchy?
The arithmetic hierarchy is a method of classifying the complexity of problems by treating such problems as logical formulas and organizing them according to the quantifiers they contain. There are ...
- 75
2 votes
0 answers
111 views
Where did the earliest Turing machine undecidability proofs appear?
It is common in any theoretical computer science textbook or class to prove the undecidability of various decision problems for Turing machines. It is often claimed that Turing himself established the ...
- 75
3 votes
1 answer
181 views
From where did the term "context-free" originate?
In Greibach's survey Formal Languages: Origins and Directions, she writes the following paragraph on page 19 about the term "context-free": The theory of context-free languages was being ...
- 75
1 vote
0 answers
108 views
Help With Understanding of Constants in Zeller's Congruence
If this would be better suited over on the Mathematics Exchange, please move it appropriately. I thought I would start here for the history type aspect Background I'm currently working as a Data ...
- 111
13 votes
2 answers
5k 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 ...
- 655
1 vote
1 answer
660 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 ...
- 111