Пока телепортировался при помощи автобуса с места на место, тут всё и расписали, о чём я дорогой думал.
Тогда, насколько я понимаю, вопрос сводится к возможности нумерации множества всех слов некоторого счетного (и уже пронумерованного) алфавита
Вот. Берём и нумеруем все слова в счётном алфавите, в том числе и абракадабру. Например так. Берём расширяющийся алфавит
и нумеруем последовательно слова длины 1 в алфавите
, затем слова длины 2 в алфавите
и т.д., смиряясь с неизбежными повторами, но ни один из арифметических предикатов пропущен не будет.
Неочевидна, как это ни странно, возможность нумерации подмножества слов, являющихся одноместными арифметическими предикатами.
А оно нам надо? Главное не пропустить, а повторы слов с разными номерами - пусть будут.
"Философия" заключается в том, что либо аналитическая грамматика, распознающая в строке формулу одноместного арифметического предиката, либо процедура проверки того, что ни один из таких предикатов "не пропущен", могут не иметь точек останова.
Первая проблема решена, остаётся проблема остановки. А это тоже не проблема, так как для конечного слова это задача конечного перебора
Будучи языком контекстно свободной грамматики, множество всех предикатов разрешимо во множестве всех слов, т.е. существует алгоритм, принимающий на входе слова и возвращающий 1 для предикатов (bot: арифметических) и 0 для остальных слов. Встроив этот алгоритм в алгоритм нумерации слов, легко построить алгоритм нумерации предикатов.
Если очень хочется, то сюда же или ещё раньше можно встроить алгоритм устранения повторов.
bot в сообщении #154732 писал(а):
А и в самом деле, всех одноместных предикатов континууум,
Откуда континуум? Предикат — конечная последовательность символов из конечного алфавита. Таких последовательностей не более чем счетное количество.
Речь шла о множестве всех предикатов, в том числе и не арифметических, но я погорячился (на манер небезызвестного здесь ниспровергателя Кантора) к множеству всех предикатов ещё и бесконечноместные предикаты.
Эт врядли.
Так что угадали.