Skip to main content

Posts

Showing posts from April, 2009

Infinite sums can get tricky!

Here's a neat example of a reasoning taken to be a paradox in 18th century (in relation to infinitesimal calculus). 1. Consider the infinite sum: 1/2 + 1/4 + 1/8 + ... + 1/2 n + 1/2 n+1 ... Intuitively, it won't go above 1, and will be higher than any number below 1. So, we might take it to be 1. 2. Now consider: 1-1+1-1+1-1+... One way to think about this sequence is this: (1-1)+(1-1)+(1-1)+... This way, it becomes 0+0+0+..., and hence it should equal 0. 3. Another way to break it down is to observe that -1+1=-(1-1) and substitute accordingly: 1-(1-1)-(1-1)-(1-1)... But if we count this way, we get 1-0-0-0-0.... = 1. 4. Now, call the whole sum U. U= 1-1+1-1+1-1+... The reverse: -U will be obtained by reversing the signs before the summands: -U= -1+1-1+1-1+1... Add now 1 to each side: 1-U= 1-1+1-1+1-1+1... But this is nothing but 1-U=U! Thus, it should follow that U=1/2. The question some 18th-century mathematicians asked: which one is it?

Szymanik on Quantifiers

Jakub Szymanik was kind enough to send me a surprise gift - a copy of his Quantifiers in TIME and SPACE (his dissertation published by ILLC). I've just discovered it in my mailbox. Thanks, Jakub! It seems fun and I look forward to reading it! Meanwhile, here is the abstract: In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. We argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Then, we discuss the influence of computational complexity theory on cognitive tasks to motivate technical considerations which follow. First, we study computational complexity of quantifier iteration, cumulation, resumption, branching and Ramseyification. Then we investigate the computational complexity of polyadic lifts expressing various rea