Formalizing Real-Valued Computable Functions

  • Thread starter kanima
  • Start date
  • #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 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:

Answers and Replies

Related Threads on Formalizing Real-Valued Computable Functions

Replies
40
Views
2K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
2
Replies
25
Views
4K
  • Last Post
Replies
10
Views
4K
Replies
1
Views
803
Replies
2
Views
371
Top