Busy Beavers and Kolmogorov Complexity

Автор: Andreev Mikhail
Сборник: Pursuit of the Universal: 12th Conference on Computability in Europe, CiE 2016, Paris, France, June 27 - July 1, 2016, Proceedings
Серия: Lecture Notes in Computer Science
Том: 9709
Год издания: 2016
Место издания: Springer Cham
Первая страница: 195
Последняя страница: 204
DOI: 10.1007/978-3-319-40189-8_20
Аннотация: The idea to find the “maximal number that can be named” can be traced back to Archimedes (see his Psammit [1]). From the viewpoint of computation theory the natural question is “which number can be described by at most n bits”? This question led to the definition of the so-called “busy beaver” numbers (introduced by T. Rado). In this note we consider different versions of the busy beaver-like notions defined in terms of Kolmogorov complexity. We show that these versions differ depending on the version of complexity used (plain, prefix, or a priori complexities) and find out how these notions are related, providing matching lower and upper bounds.
Добавил в систему: Андреев Михаил Александрович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ЦЭМИ РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА