Московское математическое общество, Московский центр непрерывного математического образования, Малый мехмат МГУ

Серия "Библиотека «Математическое просвещение»"

А. Л. Семенов Математика текстов


3.  Программы

Некоторые тексты, в частности, тексты на русском языке, являются программами, или алгоритмами, — предписаниями, которые можно выполнить. То, к чему применяется программа, тоже текст. Например, алгоритм сложения двух натуральных чисел «столбиком» — это следующий текст на русском языке:

  1. Запиши два числа друг под другом «столбиком».
  2. Если числа различаются по длине, дополни короткое слева нулями, чтобы их длины сравнялись.
  3. Запомни 0 в уме.
  4. Рассмотри самую правую пару цифр (по вертикали), которая ещё не была рассмотрена. Сложи эти две цифры и добавь то, что в уме. Если сумма меньше 10, напиши её под взятой парой, запомни в уме 0; если сумма больше или равна 10, запиши под взятой парой последнюю цифру суммы и запомни в уме 1.
  5. Если все цифры слагаемых рассмотрены и в уме 0, то результат уже получен в нижней строке; если все цифры слагаемых рассмотрены и в уме 1, допиши справа 1 к нижней строке, и это — результат; если не все цифры слагаемых рассмотрены, перейди к пункту 4.

Применяется эта программа к тексту, который представляет собой два числа, записанные в десятичной системе счисления и разделённые запятой и пробелом, например к такому:

4850493897329785961,    29785565428497

Бывают программы, распознающие некоторое свойство. Такие программы на любом тексте2 дают ответ либо «да», либо «нет». Например, можно себе представить программу, которая определяет, просто ли данное число.

Ещё один пример программы:

  1. К данному тексту припиши в конце букву «А».

Это очень простая программа, она заканчивает работу на любом тексте всего за один шаг. Бывают программы, которые не заканчивают работу, как, например, такая:

  1. К данному тексту припиши в конце букву «А».
  2. Перейди к пункту 1.

Она припишет к тексту букву «А» в конце, потом ещё раз припишет букву «А», потом ещё раз припишет букву «А» и т. д.

Встречаются и более сложные случаи, когда программа на одних текстах заканчивает работу, а на других — нет. Если программа П на тексте Т не заканчивает работу, будем это обозначать так: П(Т) = Ґ. Если же программа П заканчивает работу на тексте Т будем писать: П(Т) = !.

3.1.  Самоприменимые программы

Поскольку каждая программа представляет собой текст, то мы можем запустить её на самой себе, на собственном тексте. Программа П называется самоприменимой , если П(П) = !. А можно ли по программе П узнать, является ли она самоприменимой?

Если просто запустить программу П на тексте П, то со временем может выясниться, что она закончила работу. Но ни в какой конечный момент времени, если программа всё ещё работает, мы не можем быть уверены, что она никогда не закончит работать. Ведь может случиться так, что программа работает несколько суток, решая какую-нибудь сложную задачу, и это не означает, что она собирается работать бесконечно долго; может быть, она закончит работу через месяц, или через миллион лет.

Но может быть, есть какой-то другой способ читая текст программы понять, что она не кончает работать на самой себе?

Допустим, что существует программа S, которая, получая текст программы П, распознаёт, является ли П самоприменимой, и даёт ответ либо «да», либо «нет»3. Тогда мы можем построить программу 
~
S
 
,
которая, получив на входе программу П, запускает программу S и, если S(П) = д а, работает бесконечно долго (выполняет какую-нибудь бесконечную процедуру, например, бесконечное число раз умножает 0 на 0), а если S(П) = «нет», тоже говорит «нет», т. е. заканчивает работу. Таким образом, программа
~
S
 
не оканчивает работу на самоприменимых программах и заканчивает — на несамоприменимых.

Заметим, что конструкция здесь тоже «диагональная», как и в случае таблицы с закрашенными клетками. Только сейчас мы рассматриваем таблицу, в которой и по горизонтали, и по вертикали выписаны все программы (точнее все конечные последовательности символов того языка, на котором мы решили записывать программы (рис. 3), при этом, если текст не является программой, мы можем считать, что он просто ничего не делает с исходными данными). В клетки таблицы мы записываем результат работы программы (стоящей в заголовке столбца) на исходном тексте (стоящем в заголовке строки).

АБАААББАББВВАБ...
ААБ«да»А)р?ҐАА 
Б!,7«да»БГёҐББ 
ААу,«нет»ААЖ»ҐАААА 
АБ3,ҐАБ,—«ҐАБАБ 
БАЫы«да»БАҐҐҐБАБА 
ББ1 1«нет»ББ2ы3фщҐББББ 
ВЙ«нет»В(1(ч)!ҐВВ 
ВАБТ«нет»ВАБ2Ц1б00:ҐВАБВАБ 
...         

Рис. 3

Если программа S существует, то существует и программа
~
S
 
.
Предположим, что
~
S
 
(
~
S
 
) = !,
т. е.
~
S
 
кончает работу. Но тогда
S(
~
S
 
) = «нет»
по определению
~
S,
 
следовательно,
~
S
 
несамоприменима. И наоборот, если
~
S
 
(
~
S
 
) = Ґ,
то 
S(
~
S
 
) = «да»
и 
~
S
 
самоприменима. Противоречие.

Итак, мы установили следующий

Факт. Не существует программы, которая распознавала бы самоприменимые программы.

Это один из фундаментальных фактов теории алгоритмов, а конструкция, на которой основано его доказательство, — одна из важнейших в этой теории.

Конечно, вопрос о самоприменимости программ кажется довольно экзотическим: не так уж часто мы применяем программу к самой себе. А вот применение программы к другой программе — обычное дело: операционная система всякого реального компьютера (а она, конечно, является программой) выполняет другие программы, заданные человеком, т. е. применяется к ним.

Заметим, что и примеры, приводимые ранее, когда не удавалось определить истинность простого на вид утверждения, выглядят «далёкими от жизни», и неясно, стоит ли им придавать серьёзное значение. Попробуем объяснить, почему дело обстоит серьёзно. Первая причина состоит в том, что один контрпример — в математике уже опровержение общей теории или метода. Вторая причина в том, что как-то отделить «диагональные» случаи от « недиагональных» не удаётся, и это может быть доказано после соответствующего уточнения понятий. Однако во многих случаях и математики спрашивают друг друга: «А есть ли „естественный“ недиагональный пример?».

3.2.  Универсальная программа

Иногда возникает необходимость в программах, которые применяются к парам текстов. Каким образом можно из пары текстов сделать один? Записать два текста рядом, один за другим? К сожалению, после этого уже невозможно будет определить, где кончается первый текст и начинается второй. Чередовать буквы первого и второго текста? Но, если тексты разной длины, снова не удастся разделить полученный текст на два исходных4.

Попробуем теперь применить более сложный приём. Запишем первый текст, удваивая каждую его букву. Например, текст

Универсальная_программа

(знак _ обозначает пробел) запишется так:

УУннииввееррссааллььннааяя__ппррооггррааммммаа

После первого текста запишем разделитель «аб». Потом запишем второй текст без изменений. Допустим, что второй текст выглядит так:

Сложность_текста
Тогда окончательный результат будет таким:
УУннииввееррссааллььннааяя__ппррооггррааммммааабСложность_текста

Покажем, что по такой записи можно однозначно восстановить оба текста. Будем читать из полученной строки по два символа. Если прочитанные символы совпадают, то они представляют один символ первого текста (рис. 4). Если в некоторый момент мы натолкнёмся на два различных символа, то это означает, что мы дошли до разделителя «аб», который при восстановлении текстов нужно выбросить. После разделителя прочитаем по одному символу второй текст.

Рис. 4

Оказывается, существуют способы кодировать пару текстов одним текстом, причём делать это экономно, добавляя не слишком много новых букв, так чтобы длина кода была довольно близка к сумме длин исходных текстов.

Задача.(см. решение) Насколько длина кода пары текстов может быть близкой к сумме их длин?

Будем считать, что мы уже научились из двух текстов делать один. После этого можно построить программу U, которая применяется к паре текстов П и X, а результатом её работы будет П(X). Это тоже один из важнейших фактов теории алгоритмов.

Факт. Существует универсальная программа, которая, получая на вход программу П и текст X, применяет П к X.

Это утверждение не кажется очень сложным, хотя полные формальные доказательства его довольно громоздки.


2 Математики говорят о работе «программы на тексте» вместо более длинного выражения «программы в применении к тексту».

3 Можно рассмотреть и более сложную программу, которая получает два текста: программу П и произвольный текст X — и определяет, заканчивает ли П работу на X. Но о программах, которые применяются к парам текстов — чуть позже.

4 Вспомним, когда в алгоритме сложения «столбиком» мы из пары чисел делали один текст для работы программы на нём, мы использовали разделитель «,_» — запятую и пробел, но это было возможно, поскольку в записи самих чисел эти два символа встречаться не могли.

Следующий раздел

На головную страницу