Questions tagged [history]

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

Filter by
Sorted by
Tagged with
106 votes
5 answers

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....
Raphael's user avatar
  • 72.3k
41 votes
7 answers

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 ...
user avatar
31 votes
2 answers

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 ...
Guy Coder's user avatar
  • 5,091
46 votes
5 answers

Why has research on genetic algorithms slowed?

While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on ...
FossilizedCarlos's user avatar
32 votes
2 answers

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
Phil Wright's user avatar
13 votes
2 answers

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?
user5507's user avatar
  • 2,191
16 votes
2 answers

What is the origin of λ for empty string?

I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$. I think $\varepsilon$ is derived from the word "...
nekketsuuu's user avatar
7 votes
1 answer

Who first introduced the pushdown automaton?

I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
templatetypedef's user avatar
4 votes
2 answers

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 ...
gpuguy's user avatar
  • 1,809
2 votes
1 answer

liskov substitution principle seems to have two conventional meanings

This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)? LSP seems to have two meanings in the literature I've ...
Jim Newton's user avatar