Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Formalizing Real-Valued Computable Functions

  1. Jun 16, 2011 #1
    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: Apr 26, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?