The Experts below are selected from a list of 888 Experts worldwide ranked by ideXlab platform
S. A. Badaev - One of the best experts on this subject based on the ideXlab platform.
-
Isomorphism types of Rogers semilattices for families from different levels of the Arithmetical Hierarchy 1
2015Co-Authors: S. A. Badaev, S. S. Goncharov, A. SorbiAbstract:We investigate differences in the isomorphism types of Rogers semilat-tices of computable numberings of families of sets lying in different levels of the Arithmetical Hierarchy. Among the many possible applications of generalized computable number-ings, introduced in [10], a particularly interesting and popular one is the study of Arithmetical numberings, i.e. numberings of families of Arithmetical sets. When considering a family A of Σ0n – sets, generalized computable numberings can be characterized as follows: a numbering α of A is generalized computable if and only if the set {〈x, i 〉 : x ∈ α(i)} is Σ0n. Such a numbering α will be simply called in the following Σ0n – computable. We recall that if α and β are numberings of the same family of objects, then one says that α is reducible to β (in symbols: α ≤ β) if there exists a computable function f such that α = β ◦ f. We write α ≡ β if α ≤ β and β ≤ α. Since ≤ is a preordering relation, it follows that ≡ is an equivalence relation. If A is a family of Σ0n – sets, then ≡ partitions th
-
Isomorphism types of Rogers semilattices for families from different levels of the Arithmetical Hierarchy
Algebra and Logic, 2006Co-Authors: S. A. Badaev, S. S. Goncharov, A. SorbiAbstract:We investigate differences in isomorphism types for Rogers semilattices of computable numberings of families of sets lying in different levels of the Arithmetical Hierarchy.
-
On rogers semilattices
Lecture Notes in Computer Science, 2006Co-Authors: S. A. BadaevAbstract:Rogers semilattices of computable numberings for the families in the Hierarchy of Ershov are compared with those for the families in the Arithmetical Hierarchy.
-
TAMC - On rogers semilattices
Lecture Notes in Computer Science, 2006Co-Authors: S. A. BadaevAbstract:Rogers semilattices of computable numberings for the families in the Hierarchy of Ershov are compared with those for the families in the Arithmetical Hierarchy.
-
Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings
Computability and Models, 2003Co-Authors: S. A. Badaev, Sergey Goncharov, A. SorbiAbstract:We investigate differences in isomorphism types and elementary theories of Rogers semilattices of Arithmetical numberings, depending on different levels of the Arithmetical Hierarchy. It is proved that new types of isomorphism ap pear as the Arithmetical level increases. It is also proved the incompleteness of the theory of the class of all Rogers semi lattices of any fixed level. Finally, no Rogers semi lattice of any infinite family at Arithmetical level n 2: 2 is weakly distributive, whereas Rogers semi lattices of finite families are always distributive.
Marcus Hutter - One of the best experts on this subject based on the ideXlab platform.
-
On the computability of Solomonoff induction and AIXI
Theoretical Computer Science, 2018Co-Authors: Jan Leike, Marcus HutterAbstract:Abstract How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. We quantify this using the Arithmetical Hierarchy, and prove upper and in most cases corresponding lower bounds for incomputability. Moreover, we show that AIXI is not limit computable, thus it cannot be approximated using finite computation. However there are limit computable e -optimal approximations to AIXI. We also derive computability bounds for knowledge-seeking agents, and give a limit computable weakly asymptotically optimal reinforcement learning agent.
-
On the Computability of AIXI
2016Co-Authors: Marcus HutterAbstract:How could we solve the machine learning and the artificial intelligence problem if we had in-finite computation? Solomonoff induction and the reinforcement learning agent AIXI are pro-posed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the Arithmetical Hierarchy, and prove upper and corresponding lower bounds for in-computability. We show that AIXI is not limit computable, thus it cannot be approximated us-ing finite computation. Our main result is a limit-computable ε-optimal version of AIXI with infi-nite horizon that maximizes expected rewards
-
ALT - On the Computability of Solomonoff Induction and Knowledge-Seeking
Lecture Notes in Computer Science, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the Arithmetical Hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.
-
On the Computability of AIXI
arXiv: Artificial Intelligence, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the Arithmetical Hierarchy, and prove upper and corresponding lower bounds for incomputability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable {\epsilon}-optimal version of AIXI with infinite horizon that maximizes expected rewards.
-
On the Computability of Solomonoff Induction and Knowledge-Seeking
arXiv: Artificial Intelligence, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the Arithmetical Hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.
Oded Maler - One of the best experts on this subject based on the ideXlab platform.
-
Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy
Journal of Computer and System Sciences, 1998Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every setPof integers in the Arithmetical Hierarchy a dynamical system H with piecewise-constant derivatives such that deciding membership inPcan be reduced to solving the reachability problem between two rational points for H. The ability of such apparently simple dynamical systems, whose definition involves onlyrationalparameters, to “solve” highly unsolvable problems is closely related to Zeno's paradox, namely the ability to pack infinitely many discrete steps in a bounded interval of time.
-
achilles and the tortoise climbing up the Arithmetical Hierarchy
Foundations of Software Technology and Theoretical Computer Science, 1995Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every set R of integers in the Arithmetical Hierarchy a dynamical system \(\mathcal{H}\)with piecewise-constant derivatives (PCD) such that deciding membership in R can be reduced to solving the reachability problem between two rational points for \(\mathcal{H}\). The ability of such simple dynamical systems to “simulate” highly undecidable problems is closely related to Zeno's paradox dealing with the ability to pack infinitely many discrete steps in a bounded interval of time.
-
FSTTCS - Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy
Lecture Notes in Computer Science, 1995Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every set R of integers in the Arithmetical Hierarchy a dynamical system \(\mathcal{H}\)with piecewise-constant derivatives (PCD) such that deciding membership in R can be reduced to solving the reachability problem between two rational points for \(\mathcal{H}\). The ability of such simple dynamical systems to “simulate” highly undecidable problems is closely related to Zeno's paradox dealing with the ability to pack infinitely many discrete steps in a bounded interval of time.
Jan Leike - One of the best experts on this subject based on the ideXlab platform.
-
On the computability of Solomonoff induction and AIXI
Theoretical Computer Science, 2018Co-Authors: Jan Leike, Marcus HutterAbstract:Abstract How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. We quantify this using the Arithmetical Hierarchy, and prove upper and in most cases corresponding lower bounds for incomputability. Moreover, we show that AIXI is not limit computable, thus it cannot be approximated using finite computation. However there are limit computable e -optimal approximations to AIXI. We also derive computability bounds for knowledge-seeking agents, and give a limit computable weakly asymptotically optimal reinforcement learning agent.
-
ALT - On the Computability of Solomonoff Induction and Knowledge-Seeking
Lecture Notes in Computer Science, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the Arithmetical Hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.
-
On the Computability of AIXI
arXiv: Artificial Intelligence, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the Arithmetical Hierarchy, and prove upper and corresponding lower bounds for incomputability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable {\epsilon}-optimal version of AIXI with infinite horizon that maximizes expected rewards.
-
On the Computability of Solomonoff Induction and Knowledge-Seeking
arXiv: Artificial Intelligence, 2015Co-Authors: Jan Leike, Marcus HutterAbstract:Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the Arithmetical Hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.
-
UAI - On the computability of AIXI
2015Co-Authors: Jan Leike, Marcus HutterAbstract:How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are proposed answers to this question. Both are known to be incomputable. In this paper, we quantify this using the Arithmetical Hierarchy, and prove upper and corresponding lower bounds for in-computability. We show that AIXI is not limit computable, thus it cannot be approximated using finite computation. Our main result is a limit-computable e-optimal version of AIXI with infinite horizon that maximizes expected rewards.
Eugene Asarin - One of the best experts on this subject based on the ideXlab platform.
-
Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy
Journal of Computer and System Sciences, 1998Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every setPof integers in the Arithmetical Hierarchy a dynamical system H with piecewise-constant derivatives such that deciding membership inPcan be reduced to solving the reachability problem between two rational points for H. The ability of such apparently simple dynamical systems, whose definition involves onlyrationalparameters, to “solve” highly unsolvable problems is closely related to Zeno's paradox, namely the ability to pack infinitely many discrete steps in a bounded interval of time.
-
achilles and the tortoise climbing up the Arithmetical Hierarchy
Foundations of Software Technology and Theoretical Computer Science, 1995Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every set R of integers in the Arithmetical Hierarchy a dynamical system \(\mathcal{H}\)with piecewise-constant derivatives (PCD) such that deciding membership in R can be reduced to solving the reachability problem between two rational points for \(\mathcal{H}\). The ability of such simple dynamical systems to “simulate” highly undecidable problems is closely related to Zeno's paradox dealing with the ability to pack infinitely many discrete steps in a bounded interval of time.
-
FSTTCS - Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy
Lecture Notes in Computer Science, 1995Co-Authors: Eugene Asarin, Oded MalerAbstract:In this paper we show how to construct for every set R of integers in the Arithmetical Hierarchy a dynamical system \(\mathcal{H}\)with piecewise-constant derivatives (PCD) such that deciding membership in R can be reduced to solving the reachability problem between two rational points for \(\mathcal{H}\). The ability of such simple dynamical systems to “simulate” highly undecidable problems is closely related to Zeno's paradox dealing with the ability to pack infinitely many discrete steps in a bounded interval of time.