2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Натуральное число с заданной сложностью описания
Сообщение10.08.2010, 16:12 
Скажите , можно ли явно выписать натуральное число которое никак нельзя представить (алгоритмически описать ) меньше чем N байтами информации ?

 
 
 
 Re: Вопросик по теории информации
Сообщение10.08.2010, 16:57 
Аватара пользователя
Можно, но оно зависит от конкретного способа "алгоритмического описания".
Например, для машины Тьюринга над двухсимвольным алфавитом - это известная проблема Busy Beaver:
http://mathworld.wolfram.com/BusyBeaver.html
http://en.wikipedia.org/wiki/Busy_beaver
A028444

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group