Проблема остановки
Вопрос: закончит ли данная программа работу на данном входе или будет работать вечно. Алан Тьюринг доказал, что нет программы, которая отвечает на него верно для любой программы и любого входа. Из этого выводится теорема Райса: проверка любого смыслового правила для любой программы тоже невозможна.
Судья получает программу и её вход и должен сказать, закончит ли она работу или будет крутиться вечно. Для отдельных программ ответ найти можно. Тьюринг доказал, что нет судьи, который отвечает верно для всех программ сразу.
Почему такого судьи нет. Допустим, он есть. Напишем программу-спорщика: она спрашивает судью о самой себе и поступает наоборот. Судья сказал «остановится» — спорщик крутится вечно; сказал «не остановится» — спорщик сразу останавливается. Судья ошибается в любом случае, значит, его не бывает. Это тот же приём, что в парадоксе брадобрея, который бреет всех, кто не бреет себя сам.
Источник: Википедия: проблема остановки
Подробнее: Где ставить проверку работы ИИ-агента
Где встречается · 2
- Где ставить проверку работы ИИ-агента · Спеки и контекст
- Теорема Райса простыми словами · Спеки и контекст