Publicēti raksti (MII) / Published Articles
Permanent URI for this collection
LU Matemātikas un informātikas institūta personāla publicēti raksti.
Browse
Browsing Publicēti raksti (MII) / Published Articles by Author "Podnieks, Karlis"
Now showing 1 - 16 of 16
Results Per Page
Sort Options
- ItemComparing various concepts of function prediction. Part 1.(Latvia State University, 1974) Podnieks, KarlisPrediction: f(m+1) is guessed from given f(0), ..., f(m). Program synthesis: a program computing f is guessed from given f(0), ..., f(m). The hypotheses are required to be correct for all sufficiently large m, or with some positive frequency. These approaches yield a hierarchy of function prediction and program synthesis concepts. The comparison problem of the concepts is solved.
- ItemComparing various concepts of function prediction. Part 2.(Latvia State University, 1975) Podnieks, KarlisPrediction: f(m+1) is guessed from given f(0), ..., f(m). Program synthesis: a program computing f is guessed from given f(0), ..., f(m). The hypotheses are required to be correct for all sufficiently large m, or with some positive frequency. These approaches yield a hierarchy of function prediction and program synthesis concepts. The comparison problem of the concepts is solved.
- ItemComparing various types of limiting synthesis and prediction of functions(Latvia State University, 1974) Podnieks, Karlis
- ItemComputational complexity of prediction strategies(Latvia State University, 1977) Podnieks, KarlisThe value f(m+1) is predicted from given f(1), ..., f(m). For every enumeration T(n, x) there is a strategy that predicts the n-th function of T making no more than log2(n) errors (Barzdins-Freivalds). It is proved in the paper that such "optimal" strategies require 2^2^cm time to compute the m-th prediction (^ stands for expoentiation).
- ItemThe double-incompleteness theorem(Stiinca, Kishinev, 1976) Podnieks, KarlisLet T be a strong enough theory, and M - its metatheory, both are consistent. Then there is a closed arithmetical formula H that is undecidable in T, but one cannot prove in M neither that H is T-unprovable, nor that H is T-unrefutable. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
- ItemThe double-incompleteness theorem(Latvia State University, 1975) Podnieks, KarlisLet T be a theory, Q - a metatheory of T. Under certain conditions there exist T-undecidable sentences for which this undecidability cannot be proved in Q. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
- ItemInductive inference of recursive functions: complexity bounds(Springer Verlag, 1991) Freivalds, Rusins; Barzdins, Janis; Podnieks, KarlisThis 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 may vary between log n+o(log2n ) and an arbitrarily slow recursive function. If the result of the inference is an index in the numbering of the recursively enumerable class, then the complexity may go up to const-n. Additionally, effects previously found in the Kolmogorov complexity theory are discovered in the complexity of inductive inference as well.
- ItemMDA: correctness of model transformations. Which models are schemas?(IOS Press, 2005) Podnieks, KarlisHow to determine, is a proposed model transformation correct, or not? In general, the answer may depend on the model semantics. Of course, a model transformation is “correct”, if we can extend it to a “correct” instance data transformation. Where should model semantics be defined? Assume, model syntax and semantics are defined in the same meta-model. Then, how to separate syntax from semantics? The answer could be the definition of model schemas proposed in the paper.
- ItemOn computation in the limit by non-deterministic Turing machines(Latvia State University, 1974) Freivalds, Rusins; Podnieks, Karlis
- ItemOn computation in the limit by non-deterministic Turing machines(Scientific Proceedings of Latvia State University, 1974) Freivalds, Rūsiņš; Podnieks, Karlis
- ItemOn speeding up synthesis and prediction of functions(Latvia State University, 1974) Barzdins, Janis; Kinber, Efim; Podnieks, Karlis
- ItemOn the reducibility of function classes(Latvia State University, 1972) Podnieks, KarlisN – the set of all natural numbers, F – the set of all total functions N→N, A, B<=F. We say that A is m-reducible to B (A<=m B), iff there is a recursive operator M such that f in A, iff M(f) in B for all f in F. Similarly, 1-reducibility, tt-, btt-, 1tt- and Turing reducibility can be introduced. Table of contents. 1. Introduction. 2. Definitions of reducibilities and their simplest properties. 3. m-reducibility and the arithmetical hierarchy. 4. m-reducibility on SIGMA_1^fn. 5. Special classes. 6. Comparing various reducibilities on SIGMA_1^fn. 7. Notes on reducibilities of classes of sets.
- ItemPlatonism, intuition and the nature of mathematics(Bulgarian Academy of Sciences, Sofia, 1988) Podnieks, KarlisPlatonism is an essential aspect of mathematical method. Mathematicians are learned ability " t o l i v e " in the "world" of mathematical concepts. Here we have the main source of the creative power of mathematics, and of its surprising efficiency in natural sciences and technique. In this way, "living" (sometimes - for many years) in the "world"of their concepts and models, mathematicians are learned to draw a maximum of conclusions from a minimum of premises. Fixed system of basic principles is the distinguishing property of every mathematical theory. Mathematical model of some natural process or technical device is essentially a f i x e d m o d e l which can be investigated independently of its "original".
- ItemPrediction of the next value of a function(1981) Podnieks, KarlisThe following model of inductive inference is considered. Arbitrary set tau = {tau_1, tau_2, ..., tau_n} of n total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the set tau. Processing these values by some algorithm (a strategy) we try to predict f(m+1) from f(0), f(1), ..., f(m). Upper and lower bounds for average error numbers are obtained for prediction by using deterministic and probabilistic strategies.
- ItemProbabilistic program synthesis(Latvia State University, 1977) Podnieks, KarlisThe following model of inductive inference is considered. Arbitrary numbering tau = {tau_0, tau_1, tau_2, ... } of total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the numbering tau. Processing these values by some algorithm (a strategy) F we try to identify a tau-index of f (i.e. a number n such that f = tau_n). Strategy F outputs hypotheses h_0, h_1, ..., h_m, ... If lim h_m = n and tau_n = f, we say that F identifies in the limit tau-index of f. The complexity of identification is measured by the number of mindchanges, i.e. by F_tau(f) = card{m | h_m <> h_{m+1} }. One can verify easily that for any numbering tau there exists a deterministic strategy F such that F_tau(tau_n) <= n for all n. This estimate is exact. In the current paper the corresponding exact estimate ln n + o(log n) is proved for probabilistic strategies.
- ItemTowards a theory of inductive inference(1973) Barzdins, Janis; Podnieks, Karlis