Towards a logical foundation of randomized computation

This dissertation investigates the relations between logic and TCS in the probabilistic setting. It is motivated by two main considerations. On the one hand, since their appearance in the 1960s-1970s, probabilistic models have become increasingly pervasive in several fast-growing areas of CS. On the other, the study and development of (deterministic) computational models has considerably benefitted from the mutual interchanges between logic and CS. Nevertheless, probabilistic computation was only marginally touched by such fruitful interactions. The goal of this thesis is precisely to (start) bring(ing) this gap, by developing logical systems corresponding to specific aspects of randomized computation and, therefore, by generalizing standard achievements to the probabilistic realm. To do so, our key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations. The dissertation is tripartite. In the first part, we focus on the relation between logic and counting complexity classes. We show that, due to our classical counting propositional logic, it is possible to generalize to counting classes, the standard results by Cook and Meyer and Stockmeyer linking propositional logic and the polynomial hierarchy. Indeed, we show that the validity problem for counting-quantified formulae captures the corresponding level in Wagner's hierarchy. In the second part, we consider programming language theory. Type systems for randomized \lambda-calculi, also guaranteeing various forms of termination properties, were introduced in the last decades, but these are not "logically oriented" and no Curry-Howard correspondence is known for them. Following intuitions coming from counting logics, we define the first probabilistic version of the correspondence. Finally, we consider the relationship between arithmetic and computation. We present a quantitative extension of the language of arithmetic able to formalize basic results from probability theory. This language is also our starting point to define randomized bounded theories and, so, to generalize canonical results by Buss.

Rethinking the block. The 1970s European discourses on the city and the IBA Berlin 1979-87

The dissertation explores the relationship between projects for urban blocks and the discourses on the city between the late 1960s and the 1980s, with a particular focus on the blocks of the Internationale Bauausstellung (IBA) Berlin 1979-87. The main research questions center on whether and how the block changed in connection with the emerging ideas of the city during this period and whether these changes had, in turn, effects on the whole city. Thus far, despite extensive research on the theories and the ideas of the city between the 1960s and 1980s, there is a lack of studies that interweave this research with insights into the block. To fill this gap, this dissertation examines how the block was thematized in the 1970s discourses on the city. It highlights projects for blocks designed between the late 1960s and the 70s in various European cities, particularly West Berlin. Then, it focuses on the blocks of the IBA Berlin 1979-87, examining them through theory, history, and drawings. The study of the examples reveals three distinctive aspects of all blocks considered in the dissertation: the overcoming of small private plots, the individualization of the buildings, and the accessibility of the courtyards from public streets. These aspects reflect the changing understandings of the city and of the urban spaces in the 1970s and 1980s, which resulted in new compositional logics of the block. When examined with critical distance, the blocks of the 1970s and 80s offer a lesson in architectural and urban composition which is still current. - The author has made every effort to contact the owners of the copyrights of the material in the dissertation. The author is available to the right holders with whom it was not possible to communicate as well as for any omissions or inaccuracies in quoting the sources.

Dal sacrificio alla preghiera. La distruzione del Secondo Tempio di Gerusalemme e le trasformazioni cultuali della religione giudaica

La distruzione del Secondo Tempio di Gerusalemme nel 70 e.v. rappresenta un momento cruciale nell’evoluzione storica e teologica della religione giudaica. Prima della catastrofe, l’intero sistema cultuale si fondava sulle ritualità sacrificali, che si concentravano esclusivamente nel santuario gerosolimitano. Con la caduta di quest’ultimo e il venir meno delle sue prassi, il giudaismo dovette ripensare totalmente la propria religiosità, la quale andò gradualmente a imperniarsi sulla preghiera e su atti di devozione non cruenti, in una prospettiva più aperta, mobile e orizzontale. Pertanto, questa ricerca si pone lo scopo di analizzare, in una prospettiva fortemente votata all’antropologia, alla storia e alla sociologia della religione, il senso profondo di tale trasformazione. A questo fine, è stato studiato il culto sacrificale e liturgico giudaico precedente e successivo al 70 e.v., indagando in particolare alcuni aspetti specifici, quali la spazialità sacra, la gestualità rituale e l’uso della musica. In questo modo, è stato possibile delineare alcune logiche fondamentali che costituiscono la struttura dell’intero sistema religioso. Confrontando quelle del periodo del Secondo Tempio con quelle posteriori a esso, è dunque emersa una certa linearità, ma anche una forte discontinuità nella percezione del sacro e dei suoi rituali, fornendo così una nuova interpretazione del significato di una trasformazione di così vasta portata.