on 13-04-2012
André Souto, SQIG - Instituto de Telecomunicações
April 13, 2012, Friday, 16h15m.
Abstract: Given an individual object, how much information does that object contains? Is all that information useful? Kolmogorov complexity rigorously expresses the amount of information of a binary string x by the length of the shortest program that given to a universal Turing machine is able to produce the stringx. An incompressible string has high Kolmogorov complexity and thus has high information but from the computational complexity point of view it is not very useful, in the sense that, with high probability, one can produce another string as useful as the first one by flipping fair coins. So, how can one quantify, the subjective notion of useful information? There are two known approaches to achieve this goal based on Kolmogorov complexity: one measuring the amount of planing necessary to construct the object (static resources) and the second measuring the computational effort (dynamic resources) needed to produce the object. For the former one divide the smallest program producing the object into two parts: the part accounting for the useful regularities (useful information) and the part accounting for the remaining information present in the object so that the two-part description is as short as the shortest one-part description. The resulting measure is known as Sophistication. The latter approach is based on the time required to generate the object from any short description and the resulting measure is called logical depth. These two measures are formally defined with significance levels, i.e., with parameters that describe how far we are from the optimal solution, namely the Kolmogorov complexity of the object. In this talk I will explain how can we relate these two measures using the busy beaver function and prove that they both are not robust in the sense that, small changes in the significance levels can significantly change the values of the measures. This work was developed jointly with L. Antunes, B. Bauwens and A. Teixeira.
Room: 3.10, Mathematics
Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2011.
More Information..
on 30-03-2012
H. P. Sankappanavar, State University of New York, USA
30/03/2012, 16:15 — Room P3.10, Mathematics Building.
Abstract: George Boole (1815-1864), an English mathematician, revolutionized logic in the 19th century by applying methods from the then emerging field of symbolical algebra to logic. The sophistication and mathematical depth of Boole's approach to the logic of classes is not commonly known. Boole's algebra of logic, however, was not perfect. It has received much criticism. Yet, the system seemed, by and large, to work just as Boole claimed it would. In this lecture, I will present:
a) the criticisms pointing to the weaknesses of Boole's Logic;
b) a rigorous modern version of Boole's theorems, based in good part on Vols. I and II of Schroeder's Algebra der Logik, published in the 1890s; and
c) a rigorous modern adaptation of Boole's original algebra of logic, based partly on the work of Hailperin (1976/1986) (time permitting).
The lecture will be mostly based on the recent (unpublished) joint work with Professor Stanley Burris, as well as on his 2010 article, George Boole, in Stanford Encyclopedia of Philosophy.
More Information..