IRIS Università degli Studi di Bolognahttps://cris.unibo.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Wed, 12 May 2021 14:48:00 GMT2021-05-12T14:48:00Z10291Interpolation in singular geometric theorieshttp://hdl.handle.net/11585/704717Titolo: Interpolation in singular geometric theories
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11585/7047172019-01-01T00:00:00ZEffective choice and boundedness principles in computable analysishttp://hdl.handle.net/11585/104323Titolo: Effective choice and boundedness principles in computable analysis
Abstract: In this paper we study a new approach to classify mathematical theorems ac-
cording to their computational content. Basically, we are asking the question which theorems
can be continuously or computably transferred into each other? For this purpose theorems
are considered via their realizers which are operations with certain input and output data.
The technical tool to express continuous or computable relations between such operations
is Weihrauch reducibility and the partially ordered degree structure induced by it. We have
identified certain choice principles such as co-finite choice, discrete choice, interval choice,
compact choice and closed choice, which are cornerstones among Weihrauch degrees and it
turns out that certain core theorems in analysis can be classified naturally in this structure.
In particular, we study theorems such as the Intermediate Value Theorem, the Baire Cate-
gory Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the
Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn–
Banach Theorem and Weak König’s Lemma fit into this picture. Well-known omniscience
principles from constructive mathematics such as LPO and LLPO can also naturally be con-
sidered as Weihrauch degrees and they play an important role in our classification. Based on
thiswe compare the results of our classificationwith existing classifications in constructive and
reverse mathematics and we claim that in a certain sense our classification is finer and sheds
some new light on the computational content of the respective theorems. Our classification
scheme does not require any particular logical framework or axiomatic setting, but it can be
carried out in the framework of classical mathematics using tools of topology, computability
theory and computable analysis. We develop a number of separation techniques based on a
new parallelization principle, on certain invariance properties of Weihrauch reducibility, on
the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem.
Finally, we present a number of metatheorems that allow to derive upper bounds for the
classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed
Point Theorem as an example.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11585/1043232011-01-01T00:00:00ZEffective Borel degrees of some topological functionshttp://hdl.handle.net/11585/104201Titolo: Effective Borel degrees of some topological functions
Abstract: The focus of this paper is the incomputability of some topological functions (with respect to certain representations)
using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze
some basic topological functions on closed subsets of Rn, like closure, border, intersection, and derivative,
and we prove for such functions results of Sigma02-completeness and Sigma03-completeness in the effective Borel hierarchy.
Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and
Urysohn-Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas
define Sigma02-computable functions which in some cases are even Sigma02-complete.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11585/1042012006-01-01T00:00:00ZHow incomputable is the separable Hahn-Banach Theorem?http://hdl.handle.net/11585/104322Titolo: How incomputable is the separable Hahn-Banach Theorem?
Abstract: We determine the computational complexity of the Hahn-Banach Extension
Theorem. To do so, we investigate some basic connections between reverse
mathematics and computable analysis. In particular, we use Weak König’s
Lemma within the framework of computable analysis to classify incomputable
functions of low complexity. By defining the multivalued function Sep and a
natural notion of reducibility for multivalued functions, we obtain a computational
counterpart of the subsystem of second-order arithmetic WKL0. We study
analogies and differences between WKL0 and the class of Sep-computable multivalued
functions. Extending work of Brattka, we show that a natural multivalued
function associated with the Hahn-Banach Extension Theorem is Sep-complete.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11585/1043222009-01-01T00:00:00ZCompletion of choicehttp://hdl.handle.net/11585/779798.2Titolo: Completion of choice
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11585/779798.22020-01-01T00:00:00ZTeoremi dell'analisi e gradi di incomputabilitàhttp://hdl.handle.net/11585/104334Titolo: Teoremi dell'analisi e gradi di incomputabilità
Abstract: Vengono presentati e discussi i principali risultati concernenti la determinazione del livello di complessità computazionale dei teoremi dell'analisi mediante l'utilizzo dei gradi di Weihrauch.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11585/1043342011-01-01T00:00:00ZLas Vegas computability and algorithmic randomnesshttp://hdl.handle.net/11585/521811Titolo: Las Vegas computability and algorithmic randomness
Abstract: In this article we try to formalize the question “What can be computed with access to randomness?”
We propose the very fine-grained Weihrauch lattice as an approach to differentiate
between different types of computation with access to randomness. In particular, we show that a
natural concept of Las Vegas computability on infinite objects is more powerful than mere oracle
access to a Martin-Löf random object. As a concrete problem that is Las Vegas computable but
not computable with access to a Martin-Löf random oracle we study the problem of finding Nash
equilibria.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11585/5218112015-01-01T00:00:00ZWeihrauch goes Brouwerianhttp://hdl.handle.net/11585/779819.1Titolo: Weihrauch goes Brouwerian
Abstract: We prove that the Weihrauch lattice can be transformed into a
Brouwer algebra by the consecutive application of two closure operators in
the appropriate order: rst completion and then parallelization. The closure
operator of completion is a new closure operator that we introduce. It transforms
any problem into a total problem on the completion of the respective
types, where we allow any value outside of the original domain of the problem.
This closure operator is of interest by itself, as it generates a total version
of Weihrauch reducibility that is dened like the usual version of Weihrauch
reducibility, but in terms of total realizers. From a logical perspective completion
can be seen as a way to make problems independent of their premises.
Alongside with the completion operator and total Weihrauch reducibility we
need to study precomplete representations that are required to describe these
concepts. In order to show that the parallelized total Weihrauch lattice forms
a Brouwer algebra, we introduce a new multiplicative version of an implication.
While the parallelized total Weihrauch lattice forms a Brouwer algebra with
this implication, the total Weihrauch lattice fails to be a model of intuitionistic
linear logic in two dierent ways. In order to pinpoint the algebraic reasons
for this failure, we introduce the concept of a Weihrauch algebra that allows
us to formulate the failure in precise and neat terms. Finally, we show that
the Medvedev Brouwer algebra can be embedded into our Brouwer algebra,
which also implies that the theory of our Brouwer algebra is Jankov logic.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11585/779819.12020-01-01T00:00:00ZComputability and incomputability of differential equationshttp://hdl.handle.net/11585/104333Titolo: Computability and incomputability of differential equations
Abstract: The paper analyzes the fundamental results about the computational properties of differential equations, in particular about the apparent incomputability of the wave equation system.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11585/1043332008-01-01T00:00:00ZParadigmi di computazione per i numeri realihttp://hdl.handle.net/11585/104202Titolo: Paradigmi di computazione per i numeri reali
Abstract: In questo articolo analizziamo e compariamo i diversi modelli di computazione per i numeri reali presentati in letteratura.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11585/1042022008-01-01T00:00:00Z