Диагональ Кантора: программ меньше, чем задач

Если ты объяснишь, что значит «счётное множество», занумеруешь все строки и все пары чисел, проведёшь диагональный приём и выведешь из него, что нераспознаваемые языки существуют, - листай до «Теперь сам».

Как думаешь, хватит ли программ на все задачи

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

Ответь себе до чтения: можно ли каждой задаче сопоставить свою программу, если задач и программ поровну - бесконечно? Нельзя, потому что их не поровну. У бесконечных множеств есть размеры: одно больше другого, если элементам второго хватает разных элементов первого, а наоборот - не хватает. Множество всех языков строго больше множества всех программ. Это не вопрос изобретательности: даже если каждая программа решает какую-то задачу, почти все задачи останутся без программы.

На что это похоже

Анкета из бесконечного числа вопросов с ответами «да» и «нет». Гостей бесконечно много, у каждого свой номер и своя заполненная анкета. Утверждение: найдётся способ заполнить анкету, которым не воспользовался никто.

Вот он. На первый вопрос ответь не так, как первый гость. На второй - не так, как второй. На сотый - не так, как сотый. Получившаяся анкета отличается от анкеты гостя номер n в вопросе номер n - от каждого хоть в чём-то. Сколько бы гостей ни было, если у них есть номера, непохожая анкета найдётся.

Механизм: что можно занумеровать и что нельзя

Множество называется счётным, если его элементы можно расположить в список - первый, второй, третий, … - так, что каждый элемент стоит на каком-то конечном месте. Список бесконечен, но до любого элемента можно дойти.

Счётны многие множества, которые кажутся большими.

целые числа   0, 1, −1, 2, −2, 3, −3, …
пары чисел    по диагоналям: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), …
все строки    по длине, одной длины - по алфавиту:
              пустая, 0, 1, 00, 01, 10, 11, 000, …

Программа - строка, машина Тьюринга задаётся строкой. Значит, программ счётное число: их список - это список строк, из которого вычеркнуто всё, что программой не является.

Диагональный приём. Пусть кто-то утверждает, что выписал в список все бесконечные последовательности нулей и единиц:

номер 0:    [0] 1  0  1  1  0 …
номер 1:     1 [1] 0  0  1  1 …
номер 2:     0  0 [0] 1  0  1 …
номер 3:     1  0  1 [1] 1  0 …
             …
новая:       1  0  1  0 …      каждый знак диагонали заменён
                               на противоположный

Берём знаки, стоящие на диагонали, - знак номер n у последовательности номер n - и заменяем каждый на противоположный. Новая последовательность отличается от последовательности номер n в знаке номер n. Значит, она не совпадает ни с одной из списка, и список не полон. Рассуждение не зависит от того, каким был список, поэтому полного списка не существует: множество бесконечных двоичных последовательностей несчётно.

От последовательностей к языкам. Занумеруем все строки: строка 0, строка 1, строка 2, … Язык - это множество строк, то есть для каждой строки ответ «входит» или «не входит». Запишем ответы подряд: получим бесконечную последовательность нулей и единиц. Разным языкам соответствуют разные последовательности, и наоборот. Значит, языков столько же, сколько последовательностей, - несчётно много.

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

Правило

Множество счётно, если его элементы можно занумеровать числами 0, 1, 2, … Строки, пары чисел и программы счётны. Бесконечные двоичные последовательности несчётны: по любому их списку диагональный приём строит последовательность, которой в списке нет. Языки соответствуют таким последовательностям, поэтому языков больше, чем машин, и нераспознаваемые языки существуют.

Разбор: диагональ на таблице восемь на восемь

Приём работает и на конечной таблице: строка длины n, построенная по диагонали, отличается от каждой из n строк таблицы. Функция diagonal её строит. Потом недостающую строку дописывают в таблицу - и все строки удлиняют на один знак, чтобы таблица осталась квадратной, - и повторяют.

def diagonal(tablica):
    novaya = ""
    for i in range(len(tablica)):
        if tablica[i][i] == "0":
            novaya = novaya + "1"
        else:
            novaya = novaya + "0"
    return novaya

tablica = ["00000000", "11111111", "01010101", "00110011"]
tablica = tablica + ["00001111", "10010010", "11100111", "01101001"]
d = diagonal(tablica)
print(d, d in tablica)
otlichiya = []
for i in range(len(tablica)):
    otlichiya.append(tablica[i][i] != d[i])
print(otlichiya)
for povtor in range(3):
    for i in range(len(tablica)):
        tablica[i] = tablica[i] + "0"
    tablica.append(d + "0")
    d = diagonal(tablica)
    print(len(tablica), d, d in tablica)

10100100 False
[True, True, True, True, True, True, True, True]
9 101001001 False
10 1010010011 False
11 10100100111 False

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

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

Для конечной таблицы это неудивительно: строк длины 8 всего 256, а в таблице восемь. Содержательным приём становится на бесконечности, где подсчёт «256 больше восьми» не работает, а диагональ работает.

Разбор: строки и пары всё-таки нумеруются

Чтобы утверждение «программ счётное число» не висело в воздухе, занумеруем строки явно. Функция stroka_po_nomeru выдаёт строку по номеру, nomer_stroki - номер по строке. Третья функция нумерует пары чисел, обходя таблицу пар по диагоналям: сначала пары с суммой 0, потом с суммой 1 и так далее.

def stroka_po_nomeru(n):
    n = n + 1
    cifry = ""
    while n > 1:
        cifry = str(n % 2) + cifry
        n = n // 2
    return cifry

def nomer_stroki(s):
    n = 1
    for simvol in s:
        n = n * 2 + int(simvol)
    return n - 1

def para_po_nomeru(n):
    summa = 0
    while n > summa:
        n = n - summa - 1
        summa = summa + 1
    return [n, summa - n]

perechen = []
for n in range(10):
    perechen.append(stroka_po_nomeru(n))
print(perechen)
print(nomer_stroki("101"), stroka_po_nomeru(nomer_stroki("101")),
      nomer_stroki("0000000000"))
pary = []
for n in range(10):
    pary.append(para_po_nomeru(n))
print(pary[:5])
print(pary[5:])

['', '0', '1', '00', '01', '10', '11', '000', '001', '010']
12 101 1023
[[0, 0], [0, 1], [1, 0], [0, 2], [1, 1]]
[[2, 0], [0, 3], [1, 2], [2, 1], [3, 0]]

Приём для строк: приписать к строке слева единицу и прочитать как двоичное число, потом вычесть один. Без единицы строки 0, 00 и 000 слились бы в одно число ноль; вычитание нужно, чтобы пустая строка получила номер 0. Строка 101 получает номер 12, и по номеру 12 восстанавливается она же. Строка из десяти нулей - номер 1023. У каждой строки есть номер, у каждого номера - строка.

С парами хитрее: если идти по первой строке таблицы пар - (0,0), (0,1), (0,2), … - до второй строки не дойти никогда. Обход по диагоналям решает это: каждая диагональ конечна, и до любой пары очередь дойдёт. На диагонали с суммой s лежит s + 1 пара, и функция para_po_nomeru пропускает диагонали целиком, пока номер не попадёт внутрь очередной. Так же нумеруются тройки (тройка - это пара из пары и числа), дроби, конечные наборы чисел.

Почему этот обход не нумерует бесконечные последовательности? Он перечисляет объекты, каждый из которых задаётся конечным числом знаков. Бесконечная последовательность конечным числом знаков не задаётся - если только у неё нет конечного описания, например программы, которая её печатает. Но таких последовательностей как раз счётное число, по числу программ. По той же причине диагональ не опровергает счётность строк: диагональ списка всех конечных строк (дополним каждую нулями до бесконечной) - бесконечная последовательность, а не строка.

Что ломается без этого

«Бесконечность - она и есть бесконечность». Счётная и несчётная бесконечности различаются, и на этом различии стоит всё дальнейшее: программ меньше, чем задач.

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

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

Из существования делают пример. Подсчёт говорит, что нераспознаваемые языки есть и их большинство, но ни одного не предъявляет. Конкретный язык, и притом важный, появится в следующем уроке.

Зачем это в работе

Один приём - много теорем. Диагональю доказываются неразрешимость проблемы останова (следующий урок), теоремы об иерархииРазбирается в разделе 21, глава «Память как ресурс - PSPACE, L, NL и иерархии»: Иерархии и карта классов: что доказано, а что нет в главе о памяти (с большим запасом времени решается строго больше задач) и теоремы Гёделя о неполноте: в непротиворечивой системе аксиом, которую можно перечислить алгоритмом и которая способна описать арифметику, есть утверждение, которое нельзя ни доказать, ни опровергнуть. Теоремы Гёделя в курс не входят, но, узнав приём здесь, ты узнаешь его и в них.

Доводы подсчётом без диагонали. «Объектов больше, чем описаний» работает и на конечных множествах. Файлов длины n бит ровно 2ⁿ, а более коротких описаний - 2ⁿ − 1: строк длины k ровно 2ᵏ, и 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1. Программа сжатия обязана давать разным файлам разные описания, иначе файл не восстановить; поэтому сжатых файлов не больше, чем коротких описаний, и программа, уменьшающая любой файл, невозможна. Сжать хотя бы на байт удаётся меньше чем один файл из ста: описаний длиной не больше n − 8 бит по той же сумме 2ⁿ⁻⁷ − 1, то есть меньше 1/128 от числа файлов. Тот же подсчёт даёт нижние границы на размер структур данных.

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

Теперь сам

1. Таблица: 010, 110, 001. Построй диагональную строку.
2. Какой номер у строки 11 в нумерации из второго разбора и какая строка имеет номер 20?
3. Какая пара идёт следующей после (3, 0) при обходе по диагоналям?
4. Счётно ли множество всех конечных списков натуральных чисел?
5. Почему из того, что программ счётное число, а языков несчётное, следует существование нераспознаваемого языка?