Каждый согласится, что слово 0101….01 сложнее слова 00….0, а слово, где 0 и 1 выбираются из эксперимента – бросания монеты (где 0-герб,1 –решка), сложнее обоих предыдущих.
Любому сообщению можно приписать количественную характеристику, отражающую сложность (размер) программы, которая позволяет ее произвести.
Так как имеется много разных вычислительных машин и разных языков программирования (разных способов задания алгоритма), то для определенности задаются некоторой конкретной вычислительной машиной, например машиной Тьюринга.
Сложность слова (сообщения) определяется как минимальное число внутренних состояний машины Тьюринга, требующиеся для его воспроизведения.