- #1

- 7

- 0

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 [itex]\langle\cdot, \cdot\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}[/itex] by interpreting [itex]\langle p, q \rangle[/itex] as meaning [itex]p/q.[/itex]

Following a paper by 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 [itex]f : \mathbb{Q} \to \mathbb{R}[/itex] is said to be lower semicomputable if there exists a partial recursive function [itex]\phi : \mathbb{Q} \times \mathbb{N} \to \mathbb{Q}[/itex] such that for all [itex]x,[/itex] [itex]\phi(x, k) \le \phi(x, k + 1)[/itex] and [itex]\lim_{k \to \infty} \phi(x, k) = f(x).[/itex]

Following this, [itex]f[/itex] is said to be upper semicomputable if [itex]-f[/itex] is lower semicomputable and

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 [itex]\langle\cdot, \cdot\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}[/itex] by interpreting [itex]\langle p, q \rangle[/itex] as meaning [itex]p/q.[/itex]

Following a paper by 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 [itex]f : \mathbb{Q} \to \mathbb{R}[/itex] is said to be lower semicomputable if there exists a partial recursive function [itex]\phi : \mathbb{Q} \times \mathbb{N} \to \mathbb{Q}[/itex] such that for all [itex]x,[/itex] [itex]\phi(x, k) \le \phi(x, k + 1)[/itex] and [itex]\lim_{k \to \infty} \phi(x, k) = f(x).[/itex]

Following this, [itex]f[/itex] is said to be upper semicomputable if [itex]-f[/itex] 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?

Last edited by a moderator: