# Tag Info

82

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...

76

I'd say the most well known barriers to solving $P=NP$ are Relativization (as mentioned by Ran G.) Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize ...

56

Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft. This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the ...

38

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics. The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define ...

34

Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access. The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Thus, if some proof for, ...

33

Well, machine learning in the sense of statistical pattern recognition and data mining are definitely hotter areas, but I wouldn't say research in evolutionary algorithms has particularly slowed. The two areas aren't generally applied to the same types of problems. It's not immediately clear how a data driven approach helps you, for instance, figure out how ...

30

"So why was assembly language created?" Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day. It works the same as machine level code: with instructions and operands. "Which one came first?" Wikipedia has a good article about the History of Programming Languages "Why am I ...

29

[Note: this paragraphs is now outdated.] The title of your question contains an unwarranted assumption, namely that programming languages are "based on foundations of mathematics". This is generally not the case, although the two areas do have important relationships. A more accurate statement would be that (some) programming languages were designed using ...

28

As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper. Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such ...

26

Why do we need assembly language? Well, there's actually only one language we will ever need, which is called "machine language" or "machine code". It looks like this: 0010000100100011 This is the only language your computer can speak directly. It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also ...

21

Some decades ago, people thought that genetic and evolutionary algorithms were swiss-army-knives, fueled by spectacular early results. Statements like the building block hypothesis were made in an effort to prove that they were in general good strategies. However, rigorous results were slow in coming and often sobering, most prominently the No Free Lunch ...

20

In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people). Several definitions of "computable" were proposed, of which three are best known: The $\lambda$-calculus Recursive functions Turing ...

18

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that ...

17

This is a good question. It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then. However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. ...

17

Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the ...

17

The founders of computability theory were mathematicians. They founded what is now called computability theory before there was any computers. What was the way mathematicians defined functions that could be computed? By recursive definitions! So there were recursive function before there were any other model of computation like Turing machines or lambda ...

14

So why was assembly language created? or was it the one that came first even before high level language? Yes, assembly was one of the first programming languages which used text as input, as opposed to soldering wires, using plug boards, and/or flipping switches. Each assembly language was created for just one processor or family of processors as the ...

14

There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA. So why RSA? As far as I can tell, non-technical historical reasons dominated. RSA was patented and there was a company behind it, marketing and advocating for RSA. Also, there were good libraries, and RSA was easy to understand and ...

13

A critical part of the story, as I see it, is missing from the other answers so far: Genetic algorithms are mostly useful for brute force search problems. In many contexts, simpler optimization strategies or inference models (what you would broadly call machine learning) can perform very well, and do so far more efficiently than brute force search. ...

13

Let me add one less practical aspect. This is (probably) not a historic reason but a reason for you, today. Assembly (compared to high-level languages) is naked. It does not hide anything (that is done in software), and it is simple in the sense that it has a relatively small, fixed set of operations. This can be helpful for exact algorithm analysis. ...

13

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than,...

13

Define some basic functions: zero function $$zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0$$ successor function $$succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1$$ projection function $$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i$$ From now on I will use $\bar{x_n}$ to denote $(x_1, x_2, \... 12 To some extent, machine learning is becoming more mathematical and with algorithms able to be 'proven' to work. In some ways, GAs are very "wth happened in there" and you can't perfectly answer the question "so what did your program do?" (well in some people's eyes, anyway). I personally advocate combining neural nets and GA = GANNs. In my honours thesis, ... 11 Let us start with a quote from one of the fathers of modern Computer Science: “Computer Science is no more about computers than astronomy is about telescopes” - Edsger Wybe DIJKSTRA So in reality if what you are interested in is computers and programming then you are not truly interested in computer science :-) I think Wikipedia has one of the best ... 11 It might be worth mentioning that the German term for "Computer Science" is Informatik, which melts Infomation and Mathematik. I think that's a nice and short description of what Computer Science is all about. (the Italian term is informatica, and I'm sure there are quite a few more languages that follow the same line). 11 According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS. H. G. Kahrimanian, Analytical Differentiation by a Digital Computer, Symposium on Automatic Programming, 6–14, 1952 K.E. Iverson and L.R. Johnson, IBM Corp. research reports RC-390, RC-603, 1961 A.J. Perils and C. ... 10 Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a few trusted parties who store public keys. If you want to connect to your bank, you can ask the trusted party (let's say Verisign) for the bank's public key, as ... 10 The German Wikipedia claims that$\lambda$comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics. Chomsky used$I$as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use$1\$ as the empty ...

10

Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows: The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. ...

Only top voted, non community-wiki answers of a minimum length are eligible