0000000001151753

AUTHOR

Freivalds

showing 2 related works from this author

Hartmanis-Stearns Conjecture on Real Time and Transcendence

2012

Hartmanis-Stearns conjecture asserts that any number whose decimal expansion can be computed by a multitape Turing machine is either rational or transcendental. After half a century of active research by computer scientists and mathematicians the problem is still open but much more interesting than in 1965.

AlgebraTuring machinesymbols.namesakeRational numberConjectureIrrational numbersymbolsMultitape Turing machineDecimal representationTranscendental numberAlgebraic numberMathematics
researchProduct

Frequency Prediction of Functions

2012

Prediction of functions is one of processes considered in inductive inference. There is a "black box" with a given total function f in it. The result of the inductive inference machine F( ) is expected to be f(n+1). Deterministic and probabilistic prediction of functions has been widely studied. Frequency computation is a mechanism used to combine features of deterministic and probabilistic algorithms. Frequency computation has been used for several types of inductive inference, especially, for learning via queries. We study frequency prediction of functions and show that that there exists an interesting hierarchy of predictable classes of functions.

Hierarchy (mathematics)ComputationExistential quantificationBlack boxProbabilistic logicProbabilistic analysis of algorithmsInductive reasoningAlgorithmMathematicsRandomized algorithm
researchProduct