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

learn more… | top users | synonyms

7
votes
1answer
67 views

Origin of the concept of types

About the state of art that I'm running ahead of Type Theory I have the these question all related between them. Where did the idea of type come from? (It seems that all start when Russell and ...
1
vote
1answer
43 views

How did early computers handle variable word length?

So quoting from the book: A History of Modern Computing (History of Computing) The introduction of reliable core memory made it practical to fetch data in sets of bits, rather than one bit at a ...
58
votes
2answers
6k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the ...
9
votes
1answer
91 views

How did 'Isabelle' (the theorem prover) get its name?

The title says it all, but I'm curious because it isn't obvious how a theorem prover came to be named 'Isabelle'. Was it named for a person? I couldn't find out by some Google searches.
13
votes
4answers
2k views

Why did RSA encryption become popular for key exchange?

This is a soft question. I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message ...
5
votes
1answer
74 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...
3
votes
0answers
15 views

When and where did Remote Rendering Systems originate?

Remote rendering is system in which a server (on the cloud, usually) is performing rendering tasks (such as running a video game) and sends the rendering results to a remotely connected, thin device ...
3
votes
1answer
45 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
4
votes
1answer
81 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 ...
15
votes
4answers
727 views

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
11
votes
5answers
1k views

What is the earliest use of “trees” in computer science?

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.
-4
votes
1answer
38 views

Which commercial company was the earliest adopter of Linux? [closed]

I tried reading some articles and even watched Revolution OS, but was unable to come to a conclusion. Thought this would be a better place to get the answer. From my gathered information: It is ...
3
votes
0answers
51 views

Does the concept of the array pre-date physical computer memory implementations?

Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations? I am trying to gauge whether ...
5
votes
3answers
193 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 ...
1
vote
0answers
17 views

Mailing list history [closed]

in these days I'm doing research about the history of the mailing lists. Someone can suggest me interesting "Papers" or Article on the web in order to learn much about history and principal use of ...
2
votes
1answer
33 views

What does Djikstra mean by “formal techniques” in this essay?

In this essay (and others) by Djikstra, he refers to "formal techniques" a number of times. ... for the computing scientist, formal techniques would play a much more important rôle than they had ...
4
votes
1answer
289 views

Official Name for the “First” Programming Language Developed by Turing?

As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions ...
6
votes
3answers
200 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
8
votes
4answers
504 views

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...
4
votes
4answers
272 views

How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?
15
votes
4answers
4k views

Did 'Eugene Goostman' really pass the Turing test?

It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test. ...
5
votes
2answers
579 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 ...
0
votes
0answers
43 views

When did idea of document file format or markup language first appear?

I'm not necessarily asking for the first well-formed definition of some markup language, nor the first implementation of parser for one such language. What I'd like to know is when did people first ...
2
votes
2answers
91 views

Where can I find a high quality copy of Turing's On Computable Numbers?

Currently, I'm reading a photocopied version of Turing's famous article On Computable Numbers, With an Application to the Entscheidungsproblem. This is the best photocopy of his paper that I can ...
12
votes
1answer
538 views

Who coined the term “machine learning”?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
3
votes
1answer
138 views

Who coined the term “artificial intelligence”?

The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel ...
6
votes
1answer
85 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
0
votes
2answers
156 views

Why does binary search take $O(\log n)$ time?

My question seems like an elementary question, but it's really not. Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with ...
-2
votes
1answer
78 views

from when do we have the field of computer vision? [closed]

when was the field of computer vision created and what are the disciplines that gave birth to it? I would appreciate it if you could give some web references that have the answer.
-1
votes
1answer
318 views

Why was Alan Turing important? [closed]

What is the importance of Alan Turing? What were his inventions or innovations and why are they so influential?
2
votes
0answers
67 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 ...
33
votes
7answers
2k views

What is the definition of Computer Science, and what is the Science within Computer Science?

I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to ...
10
votes
6answers
16k views

Why do we need assembly language?

We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with ...
12
votes
1answer
293 views

Who are the legislators of Paxos?

In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol. According to this ...
2
votes
1answer
1k views

Difference between Analytical and Difference Engines

I'm not sure if one can compare the two, mainly because what I've read so far, I didn't quite understand, but what are the key differences between these 2 engines?
4
votes
2answers
287 views

Parallel Computing: Past Vs Present

Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on ...
10
votes
2answers
2k views

Why is the laplace transform not popular for image processing convolution?

Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.
3
votes
1answer
148 views

Why the name Recursively Enumerable and Recursive? [duplicate]

Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?
4
votes
1answer
110 views

Origin of theta-joins

I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A ...
21
votes
2answers
1k 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
1answer
196 views

Understanding Dijkstra's notation $f.x.y$

I recently discovered that I have a fondness for the work of Dijkstra. I am currently reading random EWDs, and stumbled across one with some notation that I couldn't quite grasp. Dijkstra states that ...
-1
votes
1answer
135 views

Where did the terms memory pool and memory leak come from?

I wonder where those terms came from. Is it computer science related? Or are they related to civil engineering, or swimming sports? Is it some analogy with filling water in a pool, or something ...
8
votes
2answers
747 views

Importance of recursion in computability theory

It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?
2
votes
0answers
121 views

Are there some popular science videos on computer algorithms to recommend?

I am seeking for some popular science videos on computer algorithms for my last lecture delivered in this term. The topic of the videos includes but are limited to algorithm design, algorithm ...
5
votes
1answer
121 views

Origin of quantum complexity theory

Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?
12
votes
4answers
1k 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)?
7
votes
2answers
111 views

Who (and when) first defined interval graphs?

I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949. So, I'm trying to track down the original paper ...
5
votes
2answers
453 views

Don Knuth and MMIXAL vs. Chuck Moore and Forth — Algorithms and Ideal Machines — was there any cross-pollination / influence in their ideas / work?

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms? I'm interested in citations, ...
5
votes
1answer
140 views

Who conceived the concept of Discrete Event Simulation, and when?

I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of ...
7
votes
1answer
361 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...