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

Не совсем. Все гномики определят принадлежность к классу абсолютно одинаково, поскольку каждый не видит лишь конечное число колпаков, что никак не мешает ему определить верный класс текущей последовательности. Затем все абсолютно одинаково выберут представителя класса (о том, как это сделать, они договариваются заранее). Теперь текущая последовательность и выбраный гномиками представитель, по причине принадлежности одному классу, различаются лишь конечным числом колпаков. Пусть они считают, что представитель и есть текущая последовательность (хоть и видят, что это не так). Ошибется лишь конечное число гномов. Сколь угодно большое, но конечное.

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

Только один из концов есть. Каждый гномик видит бесконечно много других гномиков, а не видит — конечное число других.

Я подумал над вашей идеей. Продлить ее на бесконечность, к сожалению, не выходит.

Честно говоря, я не понял про рассматривание очереди с другой стороны. Она бесконечная, у нее нет начала.

Замечание вам по терминологии: структура данных и абстрактный тип данных это не одно и то же. Например, есть абстрактный тип данных стек. В STL C++ он реализован как структура данных deque по умолчанию, но можно реализовать и на списке. Или например есть абстрактный тип данных очередь с приоритетом, а реализовать ее можно на структуре данных… да на любой.

Отсутствие следствия, на которое вы указали, само собой имеет место быть. Однако мой комментарий лишь выражал несогласие с вашим утверждением «хелловорлд в πfs лежит так далеко, что не хватит диска для записи оффсета». Если бы это утверждение (назовем его А) было истинным, то есть выводимым, то по правилу обобщения логики первого порядка, истинным было бы так же «для любого языка программирования А».
И то же про квайн. Я не увтреждаю, что он всегда близко в пи. Я спорю с вашем утверждением, что он всегда далеко в пи.

«Эта фраза не автограмма».

Хм, я не совсем понимаю, что значит для программы «main;». Вы привели пример преобразователя. У него есть как минимум две неподвижные точки:
«main;»
«main(){return -1}»
Если дать ему любую из этих двух строк, он выдаст мало того, что по смыслу, но и в точности то же самое.

Например «main;»
Если я конечно правильно понял ваш код, там со скобками что-то не то.

Уточню: номера присваиваются алгоритмам, а не функциям. У любой функции (в том числе у той, которая на любом входе возвращает «Hello world»), бесконечно много алгоритмов, реализующих ее.

Функция, которую вы привели в пример, конечно же вычислима. И у нее есть неподвижная точка. Для вашего примера, это значит, что в любой нумерации есть алгоритм под каким-то большим номером, делающий то же самое, что алгоритм под номером 5.

Возможно, вам показалось, что преобразователь из лирического отсупления сверивает код поступившей ему на вход программы с каноническим кодом, например,

int main() {std::cout << "Hello, world!";}

Такую программу (у вас соответствующую номеру 5), конечно, можно найти. Но возвращая на все остальные входы именно ее, рано или воздно алгоритм наткнется на вход:

int main() {std::cout << "Hello, " << "world!";}

Скажем, эта программа будет иметь номер N, и N будет неподвижной точкой преобразователя, поскольку обе программы с номерами 5 и N эквивалентны.

А вот написать такой код:

int isTheFunCalculable (int input) {
    if (prints_hello_world(input)) return 7;
    return 5;
}

у вас не получится, поскольку невозможно реализовать функцию bool prints_hello_world(source)

Да, возможно, неплохо. Но, как я говорил, там все рассуждения в терминах младших арифметических множеств, универсальных функций, и так далее. Давать здесь доказательство существования главной нумерации и объяснять, в чем ее смысл, не хотелось, так как чересчур.

Если вам интересно, то можете сказать, с какого места вам стало непонятно, и я попробую пересказать тот момент подробнее.

Наверное, вы правы, и без чисел было бы лучше. Однако получилось бы, что я не доказал основную формулировку теоремы Клини.

Или вон Мотидзуки запостил себе на сайт доказательство ABC и не парится.

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

Это еще ничего, я когда-то видел неполное описание машины Тьюринга на языке арифметики: &&, ||, !, forall, exists, +, *, =, 0, 1. Только там вычисление функции f(N)=M выглядело как формула, примененная к кортежу (N, M), имеет результат true.