Prefix-like Complexities of Finite and Infinite Sequences on Generalized Turing Machines.
Chernov, Alexey, Jürgen Schmidhuber · 2005
Generalized Turing machines (GTMs) are a variant of non-halting Turing machines, by computational power similar to machines with the oracle for the halting problem. GTMs allow a definition of a kind of descriptive (Kolmogorov) complexity that is uniform for finite and infinite sequences. There are several natural modifications of the definition (as there are several monotone complexities). This paper studies these definitions and compares complexities defined with the help of GTMs and complexities defined with the help of oracle machines.