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 ...
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 ...
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 ...
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 ...
16
votes
Accepted
Would an optimal sorting network ever have to swap two numbers the "wrong" way
How do you decide what the "wrong way" is?
Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn'...
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 ...
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$.
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 ...
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 ...
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 ...
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 ...
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
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 ...
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
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
intuition × 17soft-question × 6
ds.algorithms × 3
lambda-calculus × 3
big-picture × 3
ho.history-overview × 3
computability × 2
big-list × 2
fourier-analysis × 2
constructive-mathematics × 2
fft × 2
cc.complexity-theory × 1
reference-request × 1
complexity-classes × 1
lo.logic × 1
approximation-algorithms × 1
optimization × 1
type-theory × 1
ds.data-structures × 1
sorting × 1
convex-optimization × 1
p-vs-np × 1
proofs × 1
upper-bounds × 1
polynomial-hierarchy × 1