Натуральное число с заданной сложностью описания

[quex]

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

[maxal]

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