Loading...
Please wait, while we are loading the content...
Similar Documents
Program Size Complexity for Possibly Infinite Computations
| Content Provider | CiteSeerX |
|---|---|
| Author | Figueira, Santiago Picchi, Silvana Becher, Veronica Nies, André |
| Abstract | We define a program size complexity function H # as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in relative to the H # complexity. We prove that the classes of Martin-Lof random sequences and H # -random sequences coincide, and that the H # -trivial sequences are exactly the recursive ones. We also study some properties of H # and compare it with other complexity functions. In particular, H # is di#erent from H , the prefix-free complexity of monotone machines with oracle A. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Recursive One Prefix-free Kolmogorov Complexity Unending Computation Monotone Machine Prefix-free Complexity Program Size Complexity Function Random Sequence Coincide Martin-lof Random Sequence Program Size Complexity Possibly Infinite Computation Complexity Function Trivial Sequence |
| Content Type | Text |
