Доказательство, что компьютеры не всемогущи
Акт I: Кое-что компьютеры делают действительно хорошо
Это – вычислительная машина «А».
«А» решает арифметические задачи.
Она получает задачу, напечатанную на листе. И печатает ответ.
Она всегда печатает правильный ответ.
А это другая вычислительная машина, «С». «С» играет в шашки.
Она получает изображение доски И печатает, как должна походить красная шашка
«С» играет в шашки просто замечательно! Она никогда не проигрывает.
«А» и «С» - это машины, которые уже реально созданы.
Компьютеры становятся все более «умными»
Смогут ли они, в конце концов, научиться делать ВСЁ?
Доказательство, что компьютеры не всемогущи
Акт I: Кое-что компьютеры делают действительно хорошо
Это – вычислительная машина «А».
«А» решает арифметические задачи.
Она получает задачу, напечатанную на листе. И печатает ответ.
Она всегда печатает правильный ответ.
А это другая вычислительная машина, «С». «С» играет в шашки.
Она получает изображение доски И печатает, как должна походить красная шашка
«С» играет в шашки просто замечательно! Она никогда не проигрывает.
«А» и «С» - это машины, которые уже реально созданы.
Компьютеры становятся все более «умными»
…А теперь более сложная задача:
Акт II Задача об останове
Давайте загрузим в «А» шашечную доску
«А» не умеет обрабатывать такой тип входных данных.
Пытаясь его обработать, она «зависает».
То же случается и с «С», если загрузить в нее арифметический пример.
Нарисуем чертеж машины «А».
Это очень подробный чертеж, описывающий все логические схемы
Он полностью определяет, как работает «А»
И теперь мы готовы представить вам Удивительную машину «Н»!
«Н» решает так называемую «Проблему останова».
Она может проанализировать чертеж другой машины
И определить, какие входные данные для нее подойдут, а какие - вызовут зависание.
Она получает на вход чертеж машины, Которую нужно проверить,
И одновременно – тестовые входные данные.
Основываясь на чертеже, «Н» моделирует заданную машину на заданных данных
И затем определяет, произойдет зависание или нет.
«Н» решает свою задачу идеально.
Она всегда печатает правильный ответ.
Вот еще два примера работы с чертежом машины «С».
«Н» замечательная машина, Но можем ли мы ее создать в действительности?
И сейчас мы докажем, что само ее существование логически невозможно!
Доказательство, что «Н» не может существовать
Акт III: Теорема об останове
Давайте предположим, Что «Н» все-таки существует.
Мы поставим ее на специальный стенд. Зачем? Скоро станет ясно.
Напоминаю: мы предполагаем, Что «Н» решает проблему останова идеально.
Она должна всегда печатать правильный ответ. Проверим, сможет ли?
Это – копировальная машина. Она просто печатает две копии того, что получила на входе.
Поместим ее позади машины «Н».
А это еще одна простая машина. Мы назовем ее «Отрицатель».
Когда Отрицатель получает слова «Не зависнет», Он зависает.
А когда получает слово «Зависнет», Он не зависает и печатает смайлик.
Мы поставим Отрицателя перед машиной «Н».
А теперь соберем это все в одно устройство, Которое назовем машиной «Х».
У «Х» есть одно устройство ввода и одно – вывода.
Давайте посмотрим на его чертеж.
Как и раньше, этот чертеж полностью определяет машину «Х».
Как вы думаете, что произойдет, Если мы загрузим в «Х» ее собственный чертеж?
Зависнет ли она? Давайте проверим.
Копир "Р" просто удваивает этот ввод.
«Н» получает две копии чертежа «Х»
И должна определить, что машина «Х» сделает со своим чертежом
Давайте предположим, что она скажет «Не зависнет».
Машина «N» отрицает это и – зависает!
Получается, что машина «Х» зависает на своем чертеже.
Но ведь «Н» установила, что зависания не будет!
Попробуем еще раз.
На этот раз предположим, Что «Н» выдаст «Зависнет».
Машина «Х» не зависла, Но ведь «Н» предсказывала зависание.
«Н» снова ошиблась, Но ведь предполагалось, что она не может ошибаться!
Это противоречие и доказывает, Что «Н» не может существовать.
Ч.Т.Д.
Основано на доказательстве Алана Тьюринга