Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Prefix-like Complexities and Computability in the Limit

Speaker: Alexey Chernov
Author(s): Alexey Chernov and Juergen Schmidhuber
Presentation: cie.pdf
Slot: Mon, 10:50-11:10, Faraday J (col. 5)

Abstract

Computability in the limit represents the non-plus-ultra of constructive describability. It is well known that the limit computable functions on naturals are exactly those computable with the oracle for the halting problem. However, prefix (Kolmogorov) complexities defined with respect to these two models may differ. We introduce and compare several natural variations of prefix complexity definitions based on generalized Turing machines embodying the idea of limit computability, as well as complexities based on oracle machines, for both finite and infinite sequences.


websites: Arnold Beckmann 2006-04-21 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net