Wyniki wyszukiwania - BazTech

1

Universality and Almost Decidability

Calude C. S., Desfontaines D.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

77--84

EN

We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result—namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable—solves an open problem in [9]. We conclude with some open problems.

2

A Multi-Criteria Metric Algorithm for Recommender Systems

Akhtarzada A., Calude C.S., Hosking J.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

1-11

EN

Information overload and an abundance of choices create situations where selecting one option becomes extremely difficult or even worse, a guessing game. Collaborative ranking systems are widely used to alleviate this problem by creating intelligent rankings of items based on an aggregation of user opinions. Current ranking systems can still be improved in a number of areas, including accuracy, transparency and flexibility. This paper presents a multi-criteria ranking algorithm that can be used on a non-rigid set of criteria. The system implementing the algorithm fares well with respect to the above qualities.

3

Automata Recognizing No Words : A Statistical Approach

Calude C.S., Campeanu C., Dumitrescu M.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

1-18

EN

How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for ``certitude'', that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper.

4

Proving as a Computable Procedure

Calude C.S., Rudeanu S.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

43-52

EN

Gödel's incompleteness theorem states that every finitely-presented, consistent, sound theory which is strong enough to include arithmetic is incomplete. In this paper we present elementary proofs for three axiomatic variants of Gödel's incompleteness theorem and we use them (a) to illustrate the idea that there is more than ``complete vs. incomplete", there are degrees of incompleteness, and (b) to discuss the implications of incompleteness and computer-assisted proofs for Hilbert's Programme. We argue that the impossibility of carrying out Hilbert's Programme is a thesis and has a similar status to the Church-Turing thesis.

5

Computable approximations of reals: an information-theoretic analysis

Calude C.S., Hertling P.H.

Fundamenta Informaticae

|

1998

|

Vol. 33, nr 2

105-120

EN

How fast can one approximate a real by a computable sequence of rationales? Rather surprisingly, we show that the answer to this question depends very much on the information content in the finite prefixes of the binary expansion of the real. Computable reals, whose binary expansions have a very low information content, can be approximated ( very fast) with a computable convergence rate. Random reals, whose binary expansions contain very much information in their prefixes, can be approximated only very slowly by computable sequences of rationales (this is the case, for example, for Chaitin's W numbers)if they can be computably approximated at all. We also show that one can computably approximate any computable real very slowly, with a convergence rate slower than any computable function. However, there is still a large gap between computable reals and random reals: any computable sequence of rationals which converges (monotonically) to a random real converges slower than computable sequence of rationals which converges (monotonically) to a computable real.