Thursday, April 30, 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/2n + 1/2n+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:
One way to think about this sequence is this:
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:
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?

Wednesday, April 29, 2009

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 readings of reciprocal sentences with quantified antecedents and establish a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. We argue that this difference should be acknowledged in the Strong Meaning hypothesis.

Moreover, we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics.

Theoretical discussion is followed by the empirical investigations. We study the statement known as Hintikka's thesis: that the semantics of sentences like 'Most boys and most girls hate each other' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading.

Finally, we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model.

In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science.