Теорема Клини о неподвижной точке: квайны

[hack2root]

спасибо!

[mayorovp]

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

[Sayonji]

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

[pro100tak]

Я ничего не понял, но было интересно.

[Sayonji]

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

[Semisonic]

Лично мне стало не понятно после того, как в блоке «лирическое отступление» было сказано, что приведённая в качестве примера не является вычислимой.

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

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

[DmitriyN]

Вы имеете на входе не число, а программу. Программы, которая определяет, возвращает ли данная программа число 5 или «hello world», не существует.

[Semisonic]

Я перестал вообще что-либо понимать. Где в приведённом мной примере идёт противоречие данному выше определению вычислимой функции? Если отвлечься от формулировки самой теоремы №1 и просто рассмотреть один лишь мой пример.

Функция задана над натуральными числами? Да.
Возвращает натуральные числа? Да.
Её можно запрограммирвать? Да!

А что касается самой формулировки теоремы №1, то мне вообще не понятно, зачем там упомянута функция f. Ведь если все валидные алгоритмы неким образом занумерованы и теорема утверждает что алгоритмы за номерами n и f(n) выдают одинаковый выход на одинаковом входе для любой вычислимой функции f, то это эквивалентно тому, что просто существует бесконечное количество пар чисел n_i и m_i, для которых алгоритмы за номерами n_i и m_i «вычисляют одну и ту же функцию».

[Sayonji]

Функция, которую вы привели в пример, конечно же вычислима. И у нее есть неподвижная точка. Для вашего примера, это значит, что в любой нумерации есть алгоритм под каким-то большим номером, делающий то же самое, что алгоритм под номером 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)

[Sayonji]

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

[DmitriyN]

Дело в том, что функция применяется к номеру алгоритма. Представьте себе, что мы занумеровали все возможные алгоритмы натуральными числами (это возможно, т.к. множество алгоритмов счетно). Каждый алгоритм вычисляет функцию (или зацикливается), то есть, все алгоритмы можно записать как. Так вот, данная теорема о неподвижной точке говорит о том, что для любой вычислимой g существует такое n, что .

То есть, на самом деле, g не имеет никакого отношения к тому, что случается с выходом программы — она действует только на n, давая нам другую какую-то программу. Утверждение говорит лишь о том, что существует такое n, что программы под номерами n и g(n) делают одно и то же.

Конечно, вы можете сконструировать такую функцию g, что она, действуя на программу под номером n и зная, что эта программа выдает, всегда будет выдавать такой номер m, которому соответствует программа, делающая что-то другое. Это можно сделать с помощью оракула, но такая функция окажется невычислимой.

Например, эта функция может выглядеть следующим образом. Представьте, что у нас есть функция , которая возвращает текст программы под номером n и оракул , который возвращает true, если программы s1 и s2 вычисляют одинаковые функции и false в противном случае (это явно оракул согласно теореме Райса). Тогда мы можем написать такую программу:

function m = g(n)

   m = 1;
   while O(A(n), A(m)) == true
       m = m + 1;
   end
end

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

[VYBGSS]

<Шутка>Со слов «Здравствуйте, хабралюди.»</Шутка>

[gromozeka1980]

Пытаюсь разобраться :). Пока не до конца преуспел.
Вот, нашёл по теме, очень неплохо объясняют — inter-vuz.tuit.uz/Elib_baza/INTUIT.ru/html/department/calculate/basecalfun/index.html

[Sayonji]

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

[AndreyDmitriev]

Я уже хотел было возразить, что язык G (ну который LabVIEW) тоже является полным по тьюрингу, однако реализовать на нём квайн нетривиально. Однако же вот, нашёл вам в копилку квайнов:

Там, конечно, небольшой хак в том, что используется копирование и вставка, но формально этот код использует только нативные конструкции и воспроизводит сам себя, так что всё в общем-то честно.

[DmitriyN]

Единственная причина, по которой на G нетривиально реализовать квайн — это потому, что он ужасен. При этом еще возникает вопрос, что считать кодом. Если код — это то, что находится в файле .vi, то никаких сложностей в этом нет. А то, что вы привели, квайном не является.

[mayorovp]

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

<?php=file_get_contents(__FILE__)?>

[relgames]

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

Ничего не понял. Вот у меня есть программа: if (s==«main;') {return s else return „main(){return -1}“}
Какой исходник, кроме „main;“ тут можно подобрать, чтобы не изменился смысл?

[Sayonji]

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

[relgames]

Вот это преобразователь:

if (s=="main;") {
    return s;
} else {
    return "main(){return -1}";
}

Получается, для программы «main;» нельзя подобрать такую программу, чтобы после преобразования (в этом преобразователе) смысл не поменялся.

[Sayonji]

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

[relgames]

Или я вообще не понял смысла с этими преобразователями?