Search results for "Kolmogorov complexity"
showing 6 items of 16 documents
Effects of Kolmogorov complexity present in inductive inference as well
1997
For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.
Cognitive meta-learning of syntactically inferred concepts
2011
This paper outlines a proposal for a two-level cognitive architecture reproducing the process of abstract thinking in human beings. The key idea is the use of a level devoted to the extraction of compact representation for basic concepts, with additional syntactic inference carried on at a meta-level, in order to provide generalization. Higher-level concepts are inferred according to a principle of simplicity, consistent with Kolmogorov complexity, and merged back into the lower level in order to widen the underlying knowledge base.
On Fuzziness, Its Homeland and Its Neighbour
2013
It has been frequently remembered (also in the invitation letter to contribute to the present volume) that in his 1962 paper [27] which is a sort of proto-manifesto of fuzzy sets [28], Zadeh among the possible names that could denote the new notion he was trying to introduce, basides fuzzy, mentioned the term cloudy. If he had chosen this last one as the name of the theory, today we had contributed to a volume On Cloudiness.
On the impact of forgetting on learning machines
1995
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For technical reasons, it was necessary to consider two types of memory : long and sh…
Algorithmics for the Life Sciences
2013
The life sciences, in particular molecular biology and medicine, have wit- nessed fundamental progress since the discovery of the “the Double Helix”. A rele- vant part of such an incredible advancement in knowledge has been possible thanks to synergies with the mathematical sciences, on the one hand, and computer science, on the other. Here we review some of the most relevant aspects of this cooperation focusing on contributions given by the design, analysis and engineering of fast al- gorithms for the life sciences.
Multiple Usage of Random Bits in Finite Automata
2012
Finite automata with random bits written on a separate 2-way readable tape can recognize languages not recognizable by probabilistic finite automata. This shows that repeated reading of random bits by finite automata can have big advantages over one-time reading of random bits.