kanima
Jun16-11, 09:20 PM
Hi there, I'm currently reading Li and Vitanyi's book on Kolmogorov complexity. Unfortunately, I don't have a good background in computability/recursive function theory.
I have a question about their definition of a computable real-valued function. The authors first define recursive functions from the natural numbers to the natural numbers as those functions which are computable by a Turing machine. This definition is extended to rational domains and ranges by way of a recursive bijection \langle\cdot, \cdot\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N} by interpreting \langle p, q \rangle as meaning p/q.
Following a paper by Zvonkin and Levin (http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5428&option_lang=eng), the authors define a lower semicomputable function as being a real-valued function which is recursively approximable from below.
More formally, a function f : \mathbb{Q} \to \mathbb{R} is said to be lower semicomputable if there exists a partial recursive function \phi : \mathbb{Q} \times \mathbb{N} \to \mathbb{Q} such that for all x, \phi(x, k) \le \phi(x, k + 1) and \lim_{k \to \infty} \phi(x, k) = f(x).
Following this, f is said to be upper semicomputable if -f is lower semicomputable and computable if it is both upper and lower semicomputable (so it can be approximated to any desired degree of accuracy).
I'm just wondering how this definition compares to other formalizations of computability for real-valued functions. Is this a standard approach to defining computability?
I have a question about their definition of a computable real-valued function. The authors first define recursive functions from the natural numbers to the natural numbers as those functions which are computable by a Turing machine. This definition is extended to rational domains and ranges by way of a recursive bijection \langle\cdot, \cdot\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N} by interpreting \langle p, q \rangle as meaning p/q.
Following a paper by Zvonkin and Levin (http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5428&option_lang=eng), the authors define a lower semicomputable function as being a real-valued function which is recursively approximable from below.
More formally, a function f : \mathbb{Q} \to \mathbb{R} is said to be lower semicomputable if there exists a partial recursive function \phi : \mathbb{Q} \times \mathbb{N} \to \mathbb{Q} such that for all x, \phi(x, k) \le \phi(x, k + 1) and \lim_{k \to \infty} \phi(x, k) = f(x).
Following this, f is said to be upper semicomputable if -f is lower semicomputable and computable if it is both upper and lower semicomputable (so it can be approximated to any desired degree of accuracy).
I'm just wondering how this definition compares to other formalizations of computability for real-valued functions. Is this a standard approach to defining computability?