Arrow Research search

Author name cluster

Giuseppe Longo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

I&C Journal 2009 Journal Article

From exact sciences to life phenomena: Following Schrödinger and Turing on Programs, Life and Causality

  • Giuseppe Longo

This text presents a survey and a conceptual analysis of a path which goes from Programming to Physics and Biology. Schrödinger’s early reflections on coding and the genome will be a starting point: by his (and Turing’s) remarks, a link is explicitly made between the notion of program and the analysis of causality and determination in Physics. In particular, Turing’s work in Computing and in Morphogenesis (his 1952 paper on continuous dynamics) will be seen as part of a scientific path which goes from Laplace’s understanding of deterministic predictability to the developments of Poincaré’s analysis of unpredictability in non-linear systems, at the core of Turing’s 1952 work. The relevance of planetary “resonance”, in Poincaré’s Three Body Theorem, and its analogies and differences with logical circularities will then be discussed. On these grounds, some recent technical results will be mentioned relating algorithmic randomness, a strong form of logical undecidability, and physical (deterministic) unpredictability. This will be a way to approach the issue of resonances and circularities in System Biology, where these notions have a deeply different nature, in spite of some confusion which is often made. Finally, three aspects of the author’s (and his collaborators’) recent work in System Biology will be surveyed. They concern an approach to biological structural stability, as “extended criticality”, the structure of time and of biological rhythms and the role of a proper biological observable, “organization”. This is described in terms of “anti-entropy”, a new notion inspired by a remark by Schrödinger.

TCS Journal 2008 Journal Article

Computability and the morphological complexity of some dynamics on continuous domains

  • Mathieu Hoyrup
  • Arda Kolçak
  • Giuseppe Longo

The partially ordered set of compact intervals provides a convenient embedding space for the analysis of some Dynamical Systems. Crucial dynamical properties are transferred to it, while allowing an investigation of stability and chaoticity, in terms of computability, in particular in the presence of singularities. We will survey some results which display the connections between the geometric complexity of the dynamics and computability issues, as well as new relations between dynamic predictability and effective decidability.

TCS Journal 1993 Journal Article

The genericity theorem and parametricity in the polymorphic λ-calculus

  • Giuseppe Longo
  • Kathleen Milsted
  • Sergei Soloviev

This paper focuses on how terms of the polymorphic λ-calculus, which may take types as inputs, depend on types. These terms are generally understood, in all models, to have an “essentially” constant meaning on input types. We show the proof theory of polymorphic λ-calculus suggests a clear syntactic description of this phenomenon. Namely, under a reasonable condition, we show that if two polymorphic functions agree on a single type, then they agree on all types (equivalently, types are generic inputs).

TCS Journal 1990 Journal Article

A category-theoretic characterization of functional completeness

  • Giuseppe Longo
  • Eugenio Moggi

Functional languages are based on the notion of application: programs may be applied to data or programs. By application one may define algebraic functions; and a programming language is functionally complete when any algebraic function f(x 1, …, xn ) is representable (i. e. there is a constant a such that f(x 1, …, xn ) = (a·x 1, …, xn ). Combinatory logic is the simplest type-free language which is functionally complete. In a sound category-theoretic framework the constant a may be considered as an “abstract Gödel-number” for f, when Gödel-numberings are generalized to “principal morphisms”, in suitable categories. By this, models of combinatory logic are categorically characterized and their relation is given to lambda-calculus models within cartesian closed categories. Finally, the partial recursive functionals in any finite higher type are shown to yield models of combinatory logic.

MFCS Conference 1984 Conference Paper

Gödel Numberings, Principal Morphisms, Combinatory Algebras: A Category-theoretic Characterization of Functional Completeness

  • Giuseppe Longo
  • Eugenio Moggi

Abstract Functional languages are based on the notion of application: programs may be applied to data or programs. By application one may define algebraic functions and a programming language is functionally complete when any algebraic function f(x 1, .. ., x n ) is representable (i. e. there is a constant a such that f(x 1, .. ., x n ) = ax 1 ·. .. ·x n ). Combinatory Logic (C. L.) is the simplest type-free language which is functionally complete. In a sound category-theoretic framework the constant a above may be considered an "abstract gödel-number" for f, as gödel-numberings are generalized to "principal morphisms". By this, models of C. L. are categorically characterized and their relation is given to λ-calculus models within Cartesian Closed Categories. Finally, the partial recursive functionals in any finite higher type are shown to yield models of C. L. .

v2026.09.13