25 votes

Counterintuitive results for undergraduates

For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones. Here are some ideas which could be worked out to complete ...
  • 26.8k
22 votes
Accepted

How exactly does lambda calculus capture the intuitive notion of computability?

You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...
  • 26.8k
17 votes

Counterintuitive results for undergraduates

One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one ...
17 votes

Why study type theory?

Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic. A general ...
  • 26.8k
17 votes
Accepted

Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or 𝜆-calculus. They're so subtle that binding representations form an open ...
  • 2,019
14 votes
Accepted

Splay tree potential function: why sum the logs of the sizes?

How to come up with sum-of-logs potential Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into ...
  • 1,120
13 votes

Counterintuitive results for undergraduates

The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.
  • 7,757
10 votes

Counterintuitive results for undergraduates

A counter intuitive result from complexity theory is the PCP theorem: Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof ...
9 votes

Counterintuitive results for undergraduates

One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the ...
7 votes

Why is lambda calculus so "function" oriented?

The idea of how to 'mechanize mathematical proof' was a hot topic at the time; more specifically, Hilbert posed the Entscheidungsproblem - could we have a machine in some factory somewhere that takes ...
  • 2,295
7 votes

Counterintuitive results for undergraduates

building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th ...
  • 10.9k
6 votes

Counterintuitive results for undergraduates

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a ...
6 votes

How exactly does lambda calculus capture the intuitive notion of computability?

You program in it! Take a look at church encodings. You can see how pretty much all arithmetic can be performed which should probably convince you that it is extremely powerful. I like to look at ...
  • 1,131
6 votes
Accepted

What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

I don't understand exactly what you are looking for, I'll try to explain the Curry-Howard correspondence in a nutshell, you'll let me know if it helps. The Curry-Howard correspondence (or isomorphism,...
5 votes

Counterintuitive results for undergraduates

Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models. For example the rule 110 is efficiently (weakly) universal: Given ...
4 votes

What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

Simple summary: Typed $\lambda$-calculi are a way of presenting intuitionistic logics. Combinatory logic is a presentation of logic (propositional, first-order, higher-order, intuitionistic or ...
3 votes

Counterintuitive results for undergraduates

A few good candidates off the top of my head: Every NFA has an equivalent DFA There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i > 0$. Public key cryptography ...
3 votes

Why is lambda calculus so "function" oriented?

I do not know of a source that would allow me to state why Church went for functions. All I can state with confidence is that the concept of a function was of significant interest and controversy at ...
  • 131
3 votes

What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

Let me offer the simple, intuitive way that I think about this. If you restrict yourself to closed lambda expressions, you have an equivalent of the combinatory logic. In fact with just a few simple ...
  • 2,874
2 votes

Explaining computer science algorithms/concepts/ideas using metaphors

There is a very nice metaphor on decidable languages in the book Gödel, Escher, Bach by Douglas Hofstadter. He uses drawings as an analogy for recursively enumerable languages. Every time you draw ...
  • 7,757
2 votes

Explaining computer science algorithms/concepts/ideas using metaphors

B-Trees, N-ary Trees, Autocracy and Democracy http://rkvsraman.blogspot.in/2008/08/b-trees-n-ary-trees-autocracy-and.html
1 vote

Why is lambda calculus so "function" oriented?

This is just a very long comment to Joe Babel answer above. As said above Church invented $\lambda$-calculus to approach the Entscheidungsproblem (i.e. the decision problem for first-order logic) ...
1 vote

Explaining computer science algorithms/concepts/ideas using metaphors

Water filling algorithm for channel allocation http://en.wikipedia.org/wiki/Water_filling_algorithm
  • 10.1k

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