Skip to main content

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
18k views

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.6k
41 votes
7 answers
5k 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 ...
user avatar
31 votes
2 answers
3k 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 ...
Guy Coder's user avatar
  • 5,101
46 votes
5 answers
14k views

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
3k views

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

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
1k views

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

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