Сообщение Проблема Остановки от 21.06.2023 14:07
Изменено 21.06.2023 14:08 graniar
Проблема Остановки
Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.
Типа доказано, что нет.
Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".
Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и то анализируемую машину.
Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))
Имхо получается просто бессмысленная синтаксическая конструкция, как с Теоремой Гёделя о неполноте.
Помнится, лет 15 назад, когда впервые услышал о проблеме остановки, натыкался на какое-то более сложное доказательство, не вникал, но там запомнился побочный вывод о существовании верхней границы Колмогоровской сложности.
Типа доказано, что нет.
Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".
Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и то анализируемую машину.
Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))
Имхо получается просто бессмысленная синтаксическая конструкция, как с Теоремой Гёделя о неполноте.
Помнится, лет 15 назад, когда впервые услышал о проблеме остановки, натыкался на какое-то более сложное доказательство, не вникал, но там запомнился побочный вывод о существовании верхней границы Колмогоровской сложности.
Проблема Остановки
Есть такая классическая проблема о том, возможно ли в принципе проанализировать любую программу и предсказать, зависнет она или нет.
Типа доказано, что нет.
Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".
Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и анализируемую машину.
Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))
Имхо получается просто бессмысленная синтаксическая конструкция, как с Теоремой Гёделя о неполноте.
Помнится, лет 15 назад, когда впервые услышал о проблеме остановки, натыкался на какое-то более сложное доказательство, не вникал, но там запомнился побочный вывод о существовании верхней границы Колмогоровской сложности.
Типа доказано, что нет.
Только это доказательство какое-то совсем неубедительное. Слишком оно абстрактное, не поддающееся "приземлению".
Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
Но! Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и анализируемую машину.
Что такое программа-анализатор, которой скормили ее саму? Получается рекурсия. Машина которая содержит анализатор и (машину, которая содержит анализатор и (машину,...))
Имхо получается просто бессмысленная синтаксическая конструкция, как с Теоремой Гёделя о неполноте.
Помнится, лет 15 назад, когда впервые услышал о проблеме остановки, натыкался на какое-то более сложное доказательство, не вникал, но там запомнился побочный вывод о существовании верхней границы Колмогоровской сложности.