Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875797 | Theoretical Computer Science | 2017 | 11 Pages |
Abstract
Bennett's concept of logic depth [3] seeks to capture the idea that a language has a lot of useful information. Thus we would expect that neither sufficiently random nor sufficiently computationally trivial sequences are deep. A question of Moser and Stephan [11] explores the boundary of this assertion, asking if there is a low computably enumerable (Bennett) deep language. We answer this question affirmatively by constructing a superlow computably enumerable Bennett deep language.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rod Downey, Michael McInerney, Keng Meng Ng,