Напомним, что областью применимости алгоритма

называется множество таких

, что

останавливается. Область применимости алгоритма совпадает с областью определения функции, которую он вычисляет. Например, алгоритм, вычисляющий функцию

, при

не останавливается.
Назовем
алфавитом конечное множество, для которого определен алгоритм проверки элементов на равенство.
Словом алфавита

назовем конечный упорядоченный набор его элементов. Множество всех слов алфавита

обозначим

.
В книге В. А. Успенского "Теорема Геделя о неполноте" М.: Наука, 1982 на с. 35 вводится т.н. "аксиома протокола":
Для каждого алгоритма

существует алфавит

("алфавит протоколов"), разрешимое подмножество

(“множество протоколов”) и определенные на

вычислимые функции

и

такие, что

если и только если найдется такое

из

, что

,

.
Из этого утверждения делаются сильные выводы – о перечислимости области применимости и области возможных результатов каждого алгоритма (перечисление соответственно функциями

,

), о перечислимости графика любой вычислимой функции.
Успенский «аксиому протокола» не доказывает, а постулирует (что не означает, что она недоказуема – просто у него не учебник теории алгоритмов). А меня вот до крайности смущает требование разрешимости множества протоколов. Я не могу себе представить, на что должен быть похож протокол, чтобы оно выполнялось.
Возьмем алгоритм

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

и множество протоколов

так, чтобы

было разрешимо в

, т.е. существовал алгоритм

такой, что

если

и

в противном случае.
Пусть, например, алфавит протоколов имеет вид

. Единица будет служить для записи натуральных чисел в унарной системе счисления. Обозначим
![$[x]$ $[x]$](https://dxdy-04.korotkov.co.uk/f/7/e/1/7e1c4a3a07c941625c2f20c594cb9f7c82.png)
запись числа

в унарной системе. Например,
![$[3] = 111$ $[3] = 111$](https://dxdy-01.korotkov.co.uk/f/4/9/7/4976760a5bed6d1f3035d04a83b9f6bb82.png)
. Пусть протокол, отвечающий переработке числа
![$[x]$ $[x]$](https://dxdy-04.korotkov.co.uk/f/7/e/1/7e1c4a3a07c941625c2f20c594cb9f7c82.png)
в число
![$[y]$ $[y]$](https://dxdy-04.korotkov.co.uk/f/b/2/1/b21513fd44f19f610ad31275e08f2cc382.png)
, имеет вид
![$begin [x] \to [y] end$ $begin [x] \to [y] end$](https://dxdy-04.korotkov.co.uk/f/f/2/b/f2b82a05e27bdf8482da517376b6482582.png)
. Например, протокол, отвечающий переработке числа

в число

, имеет вид

.
Попытаемся создать алгоритм, выделяющий протоколы из всех остальных слов алфавита, то есть разрешающий

в

.
Написать алгоритм, выделяющий форму
![$begin [x] \to [y] end$ $begin [x] \to [y] end$](https://dxdy-04.korotkov.co.uk/f/f/2/b/f2b82a05e27bdf8482da517376b6482582.png)
из всех остальных слов, несложно. Но чтобы она была протоколом алгоритма

, этого мало. Нужно, чтобы алгоритм
действительно перерабатывал

именно в

. Например, если

- алгоритм вычисления функции

, то

не является его протоколом.
Итак, алгоритм

выделения протоколов из всех остальных слов языка должен решать следующие задачи:
1) распознавать форму
![$begin [x] \to [y] end$ $begin [x] \to [y] end$](https://dxdy-04.korotkov.co.uk/f/f/2/b/f2b82a05e27bdf8482da517376b6482582.png)
2) распознав эту форму, проверить, действительно ли

.
Для выполнения второй задачи требуется запустить сам алгоритм

. Но если

не лежит в области применимости

(а мы не зря оговорились, что это не весь натуральный ряд), то

не остановится и, значит, не остановится (и не сможет выдать ни

, ни

) и

!
Быть может, пометить протоколы определенным значком? Например, пусть алгоритм перерабатывает

в

. Тогда

будет его протоколом, а

- нет. Снабдим протоколы дополнительным значком

(

) и по этому значку будем распознавать их. Увы, это не работает. Нам нужно распознать протокол среди множества
всех слов алфавита

, то есть всех конечных упорядоченных наборов его букв. Наряду с

там будут и

, и

, то есть задача сводится к предыдущей.
Тогда, быть может, придумать алфавит

так, чтобы в нем можно было записать числа только из области применимости

и нельзя – другие числа? Увы, и это невозможно. Потому что множество всех записей чисел должно быть разрешимо в

, иначе алгоритм выделения протоколов

споткнется уже на этапе распознавания числа. А множество

эффективно счетно и, следовательно, эффективно счетно множество всех записей чисел как его разрешимое подмножество. Тогда «аксиому протокола» можно будет сформулировать только для алгоритма, область применимости которого эффективно счетна. А это не для всех алгоритмов так. Например, область применимости алгоритма

, где

- алгоритм с геделевским номером

, не является эффективно счетной. А для алгоритмов с эффективно счетной областью применимости и изобретать ничего не надо, достаточно использовать в качестве протокола эффективные номера точек из области применимости.
Так на что может быть похож протокол, какие есть версии?
И, кстати, нельзя ли доказать перечислимость области применимости любого алгоритма как-нибудь иначе?