Article ID Journal Published Year Pages File Type
6875797 Theoretical Computer Science 2017 11 Pages PDF
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
, , ,