Several results in program size complexity
type: Item
instance of: scholarly article
title: Several results in program size complexity
zbMATH Open document ID: 0459.68014
DOI: 10.1016/0304-3975(81)90083-9
author: Howard P. Katseff
author: Michael Sipser
published in: Theoretical Computer Science
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3720352
zbMATH Keywords: binary string
zbMATH Keywords: Kolmogorov's complexity measure
MaRDI profile type: Publication
full work available at URL: 0304-3975(81)90083-9
OpenAlex ID: W2018262087
cites work: On the size of machines
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Information-theoretic characterizations of recursive infinite strings
cites work: Program size, oracles, and the jump operation
cites work: Noncomplex sequences: characterizations and examples
cites work: On Kolmogorov's complexity and information
cites work: Complexity dips in random infinite binary sequences
cites work: Q5585020
cites work: A variant of the Kolmogorov concept of complexity
cites work: On Non-Computable Functions
cites work: Q5573961
cites work: On degrees of unsolvability
description: scientific article; zbMATH DE number 3720352