о невычислимых функциях
Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля".
Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.
Поскольку мы будем говорить об алгоритмах, нам потребуется зафиксировать некоторый язык программирования. Я предлагаю взять за основу упрощённый вариант языка типа Паскаль. При этом в нём нет ограничений на величину используемых чисел, а также мы игнорируем технические моменты типа описания переменных и их типов.
Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.
Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:
print(1);
for i:=1 to 1000000 do print(0)
Такая программа напечатает то, что мы хотим, и символов в ней не миллион, а меньше пятидесяти.
Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.
( Collapse )
Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.
Поскольку мы будем говорить об алгоритмах, нам потребуется зафиксировать некоторый язык программирования. Я предлагаю взять за основу упрощённый вариант языка типа Паскаль. При этом в нём нет ограничений на величину используемых чисел, а также мы игнорируем технические моменты типа описания переменных и их типов.
Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.
Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:
print(1);
for i:=1 to 1000000 do print(0)
Такая программа напечатает то, что мы хотим, и символов в ней не миллион, а меньше пятидесяти.
Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.
( Collapse )
