- Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.
- Проблемы, касающиеся абстрактных машин:
- проблема остановки (невозможно написать программу для машины Тьюринга, которая по тексту любой программы Р и её входным данным X определяет, завершается ли программа Р при входе X за конечное число шагов или зацикливается);
- проблема самоприменимости (свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма);
- проблема эквивалентности алгоритмов (по двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных).
Информатика • 11 класс
380
Алгоритмически неразрешимые задачи
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках