2
$\begingroup$

I was reading a paper on the computability of AIXI [1] and came across the notion of $\Sigma^0_n$-computability for real-valued functions in section 2.3.

I'd like to read about this in more detail. Unfortunately I couldn't find this definition anywhere else in the literature. I already checked the references given at the end of the paper.

Could somebody point me to some book/article I can take a look at?


  1. On the Computability of AIXI by J. Leike and M. Hutter (2015)
$\endgroup$
  • $\begingroup$ Can you pinpoint your difficulty? According to the paper, a function $f\colon \{0,1\}^* \to \mathbb{R}$ is in some class $C$ if the predicate $P(x,a,b) = [f(x) > a/b]$ is in the class $C$, where $x,a,b \in \{0,1\}^*$ and $a,b$ are interpreted as integers (and $b \neq 0$). $\endgroup$ – Yuval Filmus Sep 8 '16 at 18:43
2
$\begingroup$

Section 2.1 of that paper defines such computability for sets of natural numbers, and Section 2.3 of that paper then extends the notion to real-valued functions.

$\endgroup$
  • $\begingroup$ thanks for the answer but I'm actually looking for other references! $\endgroup$ – Manlio Sep 7 '16 at 23:55
  • $\begingroup$ @Saphrosit, well, that's not what you asked -- it's important to explain in the question what you already know and what your question is, so we don't waste our time giving you answers you already know. In this case, those sections also give you some search terms where you can find more information about those topics (e.g., arithmetical hierarchy, Post's theorem, lower semicomputable). So, I suggest you be resourceful and search for more on those topics. If after doing that you're still confused about something, you can ask another question about some specific aspect you're not clear on. $\endgroup$ – D.W. Sep 8 '16 at 17:10
1
$\begingroup$

The key term for finding references is "arithmetical hierarchy of real numbers". In particular, the original article by Zheng and Weihrauch (correctly) defines those notions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.