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

Mar 07, 2021 01:18

Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля ( Read more... )

математика

Leave a comment

dims12 March 6 2021, 23:17:31 UTC
Правильно ли я понимаю, что доказательство не работает, если верно утверждение

Существует такое конечное N, что для любого числа, существует программа короче N, способная напечатать это число.

И при этом f(n) длиннее N

Reply

falcao March 7 2021, 00:01:16 UTC
Так это утверждение заведомо неверно. Какое бы ни взяли конечное N, имеется лишь конечное число программ с таким ограничением на длину. Поэтому они способны напечатать только конечное множество чисел. А их бесконечно много, поэтому не любое будет можно напечатать.

Reply

dims12 March 7 2021, 08:52:55 UTC
Не уверен, ведь тут можно использовать тот же приём.

Возьмём, скажем, короткую программу

для каждого n от 0 до 1000
сгенерировать каждую возможную программу длиной n
запустить её

С одной стороны, она короче 1000 единиц, с другой стороны, делает всё, что делают программы длиной вплоть до 1000 единиц.

Reply

rus4 March 7 2021, 09:29:01 UTC
"сгенерировать каждую возможную программу длиной n"

это не процедура на нашем языке программирования

Reply

falcao March 7 2021, 09:38:01 UTC
Почему? Наш компилятор или интерпретатор содержит полное описание языка. То есть он в состоянии отличить текст корректно составленной программы от текста бессмысленного. Поэтому такое генерирование вполне возможно. Трудность там будет только с проблемой остановки.

Reply

rus4 March 7 2021, 09:56:27 UTC
я не то скопировал, сгенерировать-то можно, "запустить" не процедура --- это получается язык, ссылающийся сам на себя

Reply

falcao March 7 2021, 10:19:49 UTC
Так ведь и это можно сделать - процедура будет пошагово выполнять команды программ, формируя протокол. Интерпретатор языка, написанный на самом этом языке - вещь распространённая. Известно, например, что Марков для своих нормальных алгорифмов вручную написал такой интерпретатор на этом самом языке, проделав достаточно трудоёмкую работу в ещё "домашинный", фактически, период.

Reply

rus4 March 7 2021, 10:37:22 UTC
Но ведь это не то же самое что "запустить все программы". Какие-то из программ могут оказаться не запущены.

Reply

falcao March 7 2021, 09:35:35 UTC
Программы, печатающие числа, у нас устроены так: после печати числа, программа должна остановиться. Об этом сказано в самом начале. Ваша процедура к этому разряду не относится. Она запускает много программ, часть из которых останавливается и что-то печатает. Часть этих программ не остановится никогда. То есть получается не алгоритм (который по определению результативен, то есть за конечное время даёт результат), а более общая алгоритмическая процедура.

Конечно, она тоже может быть рассмотрена, но как мы её трактуем? Можно учитывать те числа, которые будут напечатаны какой-либо из запущенных программ, с последующей её остановкой. Множество таких чисел конечно, поэтому существует наименьшее число, которое в ходе работы этой процедуры не будет напечатано. При этом никакого противоречия, конечно, не возникает, а значение этого числа мы не знаем.

Reply

dims12 March 7 2021, 10:26:42 UTC
Я понимаю. Вопрос как раз и упирается в то, что язык позволяет перебирать программы, среди которых попадаются такие, которые не останавливаются, в том числе, бесконечная рекурсия с вызовом самой себя ( ... )

Reply


Leave a comment

Up