Search results for "recursive"

Theory of Computation, Fuzziness and a physics of the immaterial

2013

In this paper we advance three clear-cut proposals as a contribution to the discussion on the role of notions of Computation and Fuzziness as a bridge between Hard and Soft Sciences. We suggest that an important difference between the two great fami- lies of science lies in their subject or research having a grounding in nature or not, and that Theory of Computation is a glaring exception to this classifi- cation, being a textbook hard science but dealing with the immaterial. We further advance that such unicity is strongly connected with Church-Turing thesis, and discuss about the role of Computation and Fuzziness as pillars of immaterial sciences

Error detecting in inductive inference

1995

Several well-known inductive inference strategies change the actual hypothesis only when they discover that it “provably misclassifies” an example seen so far. This notion is made mathematically precise and its general power is characterized. In spite of its strength it is shown that this approach is not of universal power. Consequently, then hypotheses are considered which “unprovably misclassify” examples and the properties of this approach are studied. Among others it turns out that this type is of the same power as monotonic identification. Then it is shown that universal power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is allowed. Fi…

Co-learning of total recursive functions

1994

On the duality between mechanistic learners and what it is they learn

1993

All previous work in inductive inference and theoretical machine learning has taken the perspective of looking for a learning algorithm that successfully learns a collection of functions. In this work, we consider the perspective of starting with a set of functions, and considering the collection of learning algorithms that are successful at learning the given functions. Some strong dualities are revealed.

Vertical Representation of C∞-words

2015

International audience; We present a new framework for dealing with C∞-words, based on their left and right frontiers. Thisallows us to give a compact representation of them, and to describe the set of C∞-words throughan infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers ofC∞-words. We show that this map can be defined recursively and with no explicit reference toC∞-words. We then show that some important conjectures on C∞-words follow from analogousstatements on the structure of the graph G.

Investigating the Heartbeat-evoked cortical responses through parametric Time-Varying Information Measures

2022

Recent studies showed that the information coming from the heart is constantly processed by the brain. One index to study this process is the heartbeat-evoked potential (HEP), represented by an event-related potential component related to the cortical processing of the heartbeat. In this study we propose an approach to investigate the heartbeat-evoked EEG responses, based on quantifying the changes induced by the heartbeat on the predictability of the brain dynamics. The regularity of EEG signals is assessed through the Information Storage (IS) computed with a time-varying approach able to derive the temporal profile of the measure for each time point. Results show a modulation in the regul…

Ultrametric Finite Automata and Turing Machines

2013

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

Random Tanglegram Partitions (Random TaPas): An Alexandrian Approach to the Cophylogenetic Gordian Knot

2018

Abstract Symbiosis is a key driver of evolutionary novelty and ecological diversity, but our understanding of how macroevolutionary processes originate extant symbiotic associations is still very incomplete. Cophylogenetic tools are used to assess the congruence between the phylogenies of two groups of organisms related by extant associations. If phylogenetic congruence is higher than expected by chance, we conclude that there is cophylogenetic signal in the system under study. However, how to quantify cophylogenetic signal is still an open issue. We present a novel approach, Random Tanglegram Partitions (Random TaPas) that applies a given global-fit method to random partial tanglegrams of …

External sustainability in Spanish economy: bubbles and crises, 1970–2020

2023

We address the issue of the sustainability Spain’s exter-nal debt, using data for the period 1970–2020. To detect episodes of potentially explosive behavior of the Spanish net foreign assets over GDP ratio and the current account balance over GDP ratio, as well as episodes of external adjustments over this long period, we employ a recursive unit root test approach. Our empirical analysis leads us to conclude that there is some evidence of bubbles in the ratio between Spanish net foreign assets and the GDP. In contrast, the evidence that the ratio between the Spanish current account balance and the GDP had explosive subperiods is very weak. The episode of explosive behavior identified in the…

Inductive inference of recursive functions: Complexity bounds

2005

This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference ma…