В 1982 году нобелевский лауреат в области физики Ричард Фейнман (1918-1988) выдвинул захватывающую задачу, к которой мы обратимся в последней главе. После обнаружения ограничений в вычислительных способностях машин Тьюринга, помимо известной проблемы остановки (поговорим о ней в следующем параграфе), Фейнман предсказал существование вопросов, которые никогда не смогут быть обработаны компьютером. Он предположил, что и машины Тьюринга, и компьютеры не могут применяться для моделирования явлений квантовой природы, наблюдаемых на уровне атомов и не соответствующих классической физике. Ученый хотел сказать, что квантовые явления относятся к неразрешимым задачам, следовательно, они не могут быть обработаны обычным компьютером: машина Тьюринга, помимо прочих особенностей, должна для этого находиться одновременно в разных состояниях или одновременно считывать данные из разных ячеек. Компьютер для обработки квантовых явлений должен быть способным воспринимать не только состояния 0 и 1, но и возможные средние значения между 0 и 1 и одновременно использовать разные регистры оперативной памяти. После этого, в 1985 году, другой английский физик израильского происхождения, Дэвид Дойч (р. 1953), разработал новый класс машины Тьюринга, в котором эти ограничения были преодолены, — квантовую машину Тьюринга. Квантовые компьютеры способны моделировать неразрешимые задачи, такие как квантовые феномены, и, естественно, их ждет широкое применение.
Кроме оригинальной машины, предложенной Тьюрингом, и ее квантового варианта, предлагались и другие разработки. Например, можно построить полицефальную машину Тьюринга, то есть машину с двумя и более головками, которые считывают и записывают информацию на одну ленту, что увеличивает эффективность вычислений.
Курт Гёдель (1906-1978), создатель теоремы о неполноте, пошатнувшей основы математики.
Деталь машины Тьюринга, построенной из деталей конструктора LEGO.
Алан Тьюринг участвует в забеге на длинную дистанцию в Доркинге (Англия) в 1946 году. В этом забеге он занял второе место.
