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)
Improve this question
$\endgroup$
1
  • $\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
    Commented Sep 8, 2016 at 18:43

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for the answer but I'm actually looking for other references! $\endgroup$
    – Manlio
    Commented Sep 7, 2016 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. ♦
    Commented Sep 8, 2016 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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