Probabilistic Recursion Theory and Implicit Computational Complexity

In this thesis we provide a characterization of probabilistic computation in itself, from a recursion-theoretical perspective, without reducing it to deterministic computation. More specifically, we show that probabilistic computable functions, i.e., those functions which are computed by Probabilistic Turing Machines (PTM), can be characterized by a natural generalization of Kleene's partial recursive functions which includes, among initial functions, one that returns identity or successor with probability 1/2. We then prove the equi-expressivity of the obtained algebra and the class of functions computed by PTMs. In the the second part of the thesis we investigate the relations existing between our recursion-theoretical framework and sub-recursive classes, in the spirit of Implicit Computational Complexity. More precisely, endowing predicative recurrence with a random base function is proved to lead to a characterization of polynomial-time computable probabilistic functions.

Molecular basis of Osteoarthritis and aspects of cellular senescence in disease

The aim of this study is to investigate on some molecular mechanisms contributing to the pathogenesis of osteoarthritis (OA) and in particular to the senescence of articular chondrocytes. It is focused on understanding molecular events downstream GSK3β inactivation or dependent on the activity of IKKα, a kinase that does not belong to the phenotype of healthy articular chondrocytes. Moreover, the potential of some nutraceuticals on scavenging ROS thus reducing oxidative stress, DNA damage, and chondrocyte senescence has been evaluated in vitro. The in vitro LiCl-mediated GSK3β inactivation resulted in increased mitochondrial ROS production, that impacted on cellular proliferation, with S-phase transient arrest, increased SA-β gal and PAS staining, cell size and granularity. ROS are also responsible for the of increased expression of two major oxidative lesions, i.e. 1) double strand breaks, tagged by γH2AX, that associates with activation of GADD45β and p21, and 2) 8-oxo-dG adducts, that associate with increased IKKα and MMP-10 expression. The pattern observed in vitro was confirmed on cartilage from OA patients. IKKa dramatically affects the intensity of the DNA damage response induced by oxidative stress (H2O2 exposure) in chondrocytes, as evidenced by silencing strategies. At early time point an higher percentage of γH2AX positive cells and more foci in IKKa-KD cells are observed, but IKKa KD cells proved to almost completely recover after 24 hours respect to their controls. Telomere attrition is also reduced in IKKaKD. Finally MSH6 and MLH1 genes are up-regulated in IKKαKD cells but not in control cells. Hydroxytyrosol and Spermidine have a great ROS scavenging capacity in vitro. Both treatments revert the H2O2 dependent increase of cell death and γH2AX-foci formation and senescence, suggesting the ability of increasing cell homeostasis. These data indicate that nutraceuticals represent a great challenge in OA management, for both therapeutical and preventive purposes.