Comments 22
спасибо!
Как мне кажется, утверждение о счетности множества допустимых программ и постоянные переходы «число ↔ алогоритм» все только запутали.
Я ничего не понял, но было интересно.
Если вам интересно, то можете сказать, с какого места вам стало непонятно, и я попробую пересказать тот момент подробнее.
Лично мне стало не понятно после того, как в блоке «лирическое отступление» было сказано, что приведённая в качестве примера не является вычислимой.
Согласно вашему же определению, вычислимой называется функция из натуральных в натуральные числа, которую можно запрограммировать. Скажите мне, пожалуйста, почему не является вычислимой следующая запрограммированная функция:
Согласно вашему же определению, вычислимой называется функция из натуральных в натуральные числа, которую можно запрограммировать. Скажите мне, пожалуйста, почему не является вычислимой следующая запрограммированная функция:
int isTheFunCalculable (int input) { if (input == 5) return 7; return 5; }
Вы имеете на входе не число, а программу. Программы, которая определяет, возвращает ли данная программа число 5 или «hello world», не существует.
Я перестал вообще что-либо понимать. Где в приведённом мной примере идёт противоречие данному выше определению вычислимой функции? Если отвлечься от формулировки самой теоремы №1 и просто рассмотреть один лишь мой пример.
Функция задана над натуральными числами? Да.
Возвращает натуральные числа? Да.
Её можно запрограммирвать? Да!
А что касается самой формулировки теоремы №1, то мне вообще не понятно, зачем там упомянута функция f. Ведь если все валидные алгоритмы неким образом занумерованы и теорема утверждает что алгоритмы за номерами n и f(n) выдают одинаковый выход на одинаковом входе для любой вычислимой функции f, то это эквивалентно тому, что просто существует бесконечное количество пар чисел ni и mi, для которых алгоритмы за номерами ni и mi «вычисляют одну и ту же функцию».
Функция задана над натуральными числами? Да.
Возвращает натуральные числа? Да.
Её можно запрограммирвать? Да!
А что касается самой формулировки теоремы №1, то мне вообще не понятно, зачем там упомянута функция f. Ведь если все валидные алгоритмы неким образом занумерованы и теорема утверждает что алгоритмы за номерами n и f(n) выдают одинаковый выход на одинаковом входе для любой вычислимой функции f, то это эквивалентно тому, что просто существует бесконечное количество пар чисел ni и mi, для которых алгоритмы за номерами ni и mi «вычисляют одну и ту же функцию».
Функция, которую вы привели в пример, конечно же вычислима. И у нее есть неподвижная точка. Для вашего примера, это значит, что в любой нумерации есть алгоритм под каким-то большим номером, делающий то же самое, что алгоритм под номером 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)
Дело в том, что функция применяется к номеру алгоритма. Представьте себе, что мы занумеровали все возможные алгоритмы натуральными числами (это возможно, т.к. множество алгоритмов счетно). Каждый алгоритм вычисляет функцию (или зацикливается), то есть, все алгоритмы можно записать как. Так вот, данная теорема о неподвижной точке говорит о том, что для любой вычислимой g существует такое n, что .
То есть, на самом деле, g не имеет никакого отношения к тому, что случается с выходом программы — она действует только на n, давая нам другую какую-то программу. Утверждение говорит лишь о том, что существует такое n, что программы под номерами n и g(n) делают одно и то же.
Конечно, вы можете сконструировать такую функцию g, что она, действуя на программу под номером n и зная, что эта программа выдает, всегда будет выдавать такой номер m, которому соответствует программа, делающая что-то другое. Это можно сделать с помощью оракула, но такая функция окажется невычислимой.
Например, эта функция может выглядеть следующим образом. Представьте, что у нас есть функция , которая возвращает текст программы под номером n и оракул , который возвращает true, если программы s1 и s2 вычисляют одинаковые функции и false в противном случае (это явно оракул согласно теореме Райса). Тогда мы можем написать такую программу:
Но функция, описываемая такой программой невычислима, так как использует обращение к оракулу. Конечно, это не доказательство, но, надеюсь, достаточно наглядно, для того, чтобы прояснить этот момент.
То есть, на самом деле, 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
Но функция, описываемая такой программой невычислима, так как использует обращение к оракулу. Конечно, это не доказательство, но, надеюсь, достаточно наглядно, для того, чтобы прояснить этот момент.
<Шутка>Со слов «Здравствуйте, хабралюди.»</Шутка>
Пытаюсь разобраться :). Пока не до конца преуспел.
Вот, нашёл по теме, очень неплохо объясняют — inter-vuz.tuit.uz/Elib_baza/INTUIT.ru/html/department/calculate/basecalfun/index.html
Вот, нашёл по теме, очень неплохо объясняют — inter-vuz.tuit.uz/Elib_baza/INTUIT.ru/html/department/calculate/basecalfun/index.html
Я уже хотел было возразить, что язык G (ну который LabVIEW) тоже является полным по тьюрингу, однако реализовать на нём квайн нетривиально. Однако же вот, нашёл вам в копилку квайнов:
Там, конечно, небольшой хак в том, что используется копирование и вставка, но формально этот код использует только нативные конструкции и воспроизводит сам себя, так что всё в общем-то честно.
Там, конечно, небольшой хак в том, что используется копирование и вставка, но формально этот код использует только нативные конструкции и воспроизводит сам себя, так что всё в общем-то честно.
Единственная причина, по которой на G нетривиально реализовать квайн — это потому, что он ужасен. При этом еще возникает вопрос, что считать кодом. Если код — это то, что находится в файле .vi, то никаких сложностей в этом нет. А то, что вы привели, квайном не является.
Если есть программа, получающая на вход исходный код и возвращающая исходный код, то можно подобрать такой исходник, который по смыслу не изменится после данного преобразования
Ничего не понял. Вот у меня есть программа: if (s==«main;') {return s else return „main(){return -1}“}
Какой исходник, кроме „main;“ тут можно подобрать, чтобы не изменился смысл?
Например «main;»
Если я конечно правильно понял ваш код, там со скобками что-то не то.
Если я конечно правильно понял ваш код, там со скобками что-то не то.
Вот это преобразователь:
Получается, для программы «main;» нельзя подобрать такую программу, чтобы после преобразования (в этом преобразователе) смысл не поменялся.
if (s=="main;") {
return s;
} else {
return "main(){return -1}";
}
Получается, для программы «main;» нельзя подобрать такую программу, чтобы после преобразования (в этом преобразователе) смысл не поменялся.
Или я вообще не понял смысла с этими преобразователями?
Sign up to leave a comment.
Теорема Клини о неподвижной точке: квайны