В 1936 году Алан Тьюринг опубликовал статью1. Он решал задачу Гильберта — «проблему разрешения»: существует ли алгоритм который определяет истинность любого математического утверждения?

Чтобы ответить на вопрос об алгоритмах — Тьюринг сначала определил что такое алгоритм. Придумал абстрактную машину. Лента с символами. Головка читает и пишет. Набор правил что делать в каждом состоянии.

Машина Тьюринга — это не устройство. Это математическое определение вычисления. Всё что можно вычислить — можно вычислить на машине Тьюринга. Это тезис Чёрча-Тьюринга. Гипотеза. Но ни разу не опровергнутая.

Ответ на вопрос Гильберта: нет. Не существует алгоритма который решает задачу остановки2 — определяет завершится ли данная программа или будет работать вечно. Тьюринг доказал это диагонализацией — как Кантор.

1939–1945. Блетчли-Парк. Тьюринг работал на британскую разведку. Немецкая «Энигма» — шифровальная машина. Тьюринг создал «Бомбу» — электромеханическое устройство которое перебирало ключи шифрования. По оценкам историков — взлом Энигмы сократил войну на 2-4 года. Спасены миллионы жизней.

После войны — первые настоящие компьютеры. Тьюринг участвовал в разработке ACE — одного из первых. В 1950 году написал статью «Вычислительные машины и разум»3. Ввёл «имитационную игру» — позже названную тестом Тьюринга. Вопрос: может ли машина мыслить? Тест: если человек не может отличить машину от человека в диалоге — машина мыслит.

«Мы можем видеть лишь немного вперёд, но можем видеть что впереди ещё много что нужно сделать.» — Алан Тьюринг · «Вычислительные машины и разум» · 1950

В 1952 году Тьюринг сообщил полиции о краже. Выяснилось что у него были отношения с мужчиной. В Великобритании 1952 года это было уголовным преступлением. Тьюринг осуждён. Выбор: тюрьма или химическая кастрация. Он выбрал второе.

В 1954 году найден мёртвым. Надкушенное яблоко рядом. Цианид. Официально — самоубийство. Семья всегда считала — несчастный случай.

В 2013 году Тьюринг посмертно помилован королевой4. В 2021 году его портрет появился на банкноте в 50 фунтов. Поздно. Но всё же.

Каждый раз когда вы запускаете программу — вы используете концепцию которую придумал Тьюринг за 13 лет до появления первого коммерческого компьютера.