Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал
https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля
(
Read more... )
Существует такое конечное N, что для любого числа, существует программа короче N, способная напечатать это число.
И при этом f(n) длиннее N
Reply
Reply
Возьмём, скажем, короткую программу
для каждого n от 0 до 1000
сгенерировать каждую возможную программу длиной n
запустить её
С одной стороны, она короче 1000 единиц, с другой стороны, делает всё, что делают программы длиной вплоть до 1000 единиц.
Reply
это не процедура на нашем языке программирования
Reply
Reply
Reply
Reply
Reply
Конечно, она тоже может быть рассмотрена, но как мы её трактуем? Можно учитывать те числа, которые будут напечатаны какой-либо из запущенных программ, с последующей её остановкой. Множество таких чисел конечно, поэтому существует наименьшее число, которое в ходе работы этой процедуры не будет напечатано. При этом никакого противоречия, конечно, не возникает, а значение этого числа мы не знаем.
Reply
Reply
Leave a comment