On Reasonable Space and Time Cost Models for the λ-Calculus

Slot and van Emde Boas Invariance Thesis states that a time (respectively, space) cost model is reasonable for a computational model C if there are mutual simulations between Turing machines and C such that the overhead is polynomial in time (respectively, linear in space). The rationale is that under the Invariance Thesis, complexity classes such as LOGSPACE, P, PSPACE, become robust, i.e. machine independent. In this dissertation, we want to find out if it possible to define a reasonable space cost model for the lambda-calculus, the paradigmatic model for functional programming languages. We start by considering an unusual evaluation mechanism for the lambda-calculus, based on Girard's Geometry of Interaction, that was conjectured to be the key ingredient to obtain a space reasonable cost model. By a fine complexity analysis of this schema, based on new variants of non-idempotent intersection types, we disprove this conjecture. Then, we change the target of our analysis. We consider a variant over Krivine's abstract machine, a standard evaluation mechanism for the call-by-name lambda-calculus, optimized for space complexity, and implemented without any pointer. A fine analysis of the execution of (a refined version of) the encoding of Turing machines into the lambda-calculus allows us to conclude that the space consumed by this machine is indeed a reasonable space cost model. In particular, for the first time we are able to measure also sub-linear space complexities. Moreover, we transfer this result to the call-by-value case. Finally, we provide also an intersection type system that characterizes compositionally this new reasonable space measure. This is done through a minimal, yet non trivial, modification of the original de Carvalho type system.

Transizioni di fase nell'allenamento delle Macchine di Boltzmann Ristrette

In this thesis, we dealt with Restricted Boltzmann Machines with binary priors as models of unsupervised learning, analyzing the role of the number of hidden neurons on the amount of examples needed for a successful training. We simulated a teacher-student scenario and calculated the efficiency of the machine under the assumption of replica symmetry to study the location of the critical threshold beyond which learning begins. Our results confirm the conjecture that, in the absence of correlation between the weights of the data-generating machine, the critical threshold does not depend on the number of hidden units (as long as it is finite) and thus on the complexity of the data. Instead, the presence of correlation significantly reduces the amount of examples needed for training. We have shown that this effect becomes more pronounced as the number of hidden units increases. The entire analysis is supported by numerical simulations that corroborate the results.