UTM

gatoazul — 21.05.2020 Сегодня для разнообразия будет научпоп.



Видите вот этого мокрого молодого человека? Мы разберем, что же на самом деле он придумал. Не в этот момент, который запечатлен на фотографии, а года через четыре, но тоже в неформальной обстановке, когда валялся на мягкой траве, растущей на лугах вокруг Кембриджа.

Вся история началась, впрочем, гораздо раньше, с математиков-теоретиков. Их смущало, что правильность дифференциального и интегрального исчисления никем не доказана. Практиков этого не волновало - результаты расчетов отлично сходились с измерениями. Его и придумал-то практик Ньютон для решения задач физики, и смело оперировал бесконечно малыми.

Но теоретики были перфекционистами. Какие еще бесконечно малые? Вы там берете величины, которые чему-то равны, смело их складывате и умножаете, а потом, когда надо, выкидываете из расчетов, дескать, они все равно малые и равны нулю. Так не пойдет. Или это числа, или нули.

Поэтому математики расчехлили чернильницы и в конце концов соорудили теорию пределов, которой и обосновали высшую математику.


Если кому интересно, как они выкрутились. Согласно новым установкам, бесконечно малые - это не величины, это переменные, которые в ходе некоего процесса, называемого предельным переходом, становятся все ближе и ближе к нулю.

Установки эти, хотя и доказуемые, и успешно обосновывающие что надо, имеют один недостаток. Они довольно неестественны для обычного мышления и чтобы в них врубиться, надо долго и настойчиво их учить. Поэтому уже в наше время придумали нестандартный анализ - в котором бесконечно малые имеют как раз интуитивный вид маленьких-премаленьких чисел. Ничего нового он, в принципе, не говорит, все его теоремы можно переформулировать на языке пределов, но учить его и правда проще. Математический мейнстрим его не принял и считает неким курьезом.

Результат понравился и возникла естественная мысль: не замахнуться ли нам вообще на Вильяма нашего Шекспира? В смысле, а не обосновать ли вообще всю математику, начиная с арифметики? Тем более, примерно в это время изобрели математическую логику - булевы переменные, И, ИЛИ и все-такое.

И образец был, освященный временем. Геометрия, которую древнегреческий Евклид сформулировал очень любопытным методом: определил несколько недоказуемых аксиом, а все остальное логически вывел из них.


Правда, и тут не все было гладко. Пятая аксиома Евклида (о параллельных прямых) выглядела как-то сомнительно. Ее много лет пытались доказать - безуспешно. В конце концов выяснилось, что если взять другой ее вариант, то получится другая геометрия. А если третий - то третья.

В-общем, Евклид правильно сделал ее аксиомой, но осадочек все равно остался.


В результате скрещения этих трех идей: аксиоматического метода, идеи доказать основания математики и создания математической логики получилась такая программа:

А давайте правильно подберем логические аксиомы и из них выведем всю остальную математику, причем чисто механически, манипуляцией с символами, не вникая в их смысл!

Она получила название формализма, каковым и являлась. Видным ее представителем был Давид Гильберт.

С формализмом были согласны, разумеется, не все, но многие восприняли эти планы с энтузиазмом.

Нужно было только подобрать аксиомы и еще уточнить на языке математики, что значит "механически" - это ведь не математическое понятие.

Снова заскрипели перья и поначалу все шло хорошо. Нашлись удобные аксиомы арифметики (система Пеано), были разработаны методы самой логики и Рассел с Уайтхедом через два тома, набитых формулами, начав с булевых операций, доказали в результате,что 1+1=2.

А потом все пошло не так. В 1931 году Курт Гёдель доказал, что если добавить к предикатной логике аксиомы арифметики, то получившаяся система окажется неполной. В ней будут такие теоремы, которые в рамках этой системы недоказуемы.

То есть, мечта Гильберта недостижима в принципе. Арифметику невозможно аксиоматизировать так, чтобы пользуясь системой аксиом, можно было доказать все верные теоремы - как в геометрии.

А еще через несколько лет тот самый парень, что на снимке, принес еще худшую новость: в этой системе есть теоремы, котоыре даже вывести из исходной системы нельзя. Не то, что доказать, правильные они или нет, а даже вывести - то есть, сказать, относятся ли они вообще к этой системе аксиом или нет.

Как вы догадались, он был математиком.

Да, я же не сказал еще, как его звали. Алан Тьюринг.

Буквально через несколько месяцев тот же результат другим способом получил Чёрч. Но это уже не так интересно, потому что в работе Тьюринга, если вы не математик и не логик, основной интерес представляет не столько результат, сколько сам метод.

Тьюринг был одиночкой не только в жизни, но в математике. И поэтому его подход был очень необычным для того времени - хотя нам он кажется вполне естетственным. Но это только потому, что мы до сих пор едем по дороге, которую проложил Тьюринг.

Что такое механическое исчисление? Как его формализовать? Тьюринг представил процесс буквально: вот есть некоторая машина, которая может посчитать какое-нибудь число.

Еще раз повторюсь: это было очень странно. В то время математикой и даже счетом занимались исключительно люди, машины вокруг были самые примитивные, в основном механические, самые сложные - пожалуй, паровоз и линотип, и сама мысль, что машина может что-то посчитать без участия человека, отдавала ересью.

Итак, есть очень странная машина. Она состоит из очень-очень длинной ленты, поделенной на клеточки; головки чтения/записи, которая в данный момент смотрит на одну из клеточек, и может стереть из нее символ, или написать другой, и некоторого состояния. Это математическая машина, чисто воображаемая, лента у нее бесконечная, а работать она может, сколько хочет - хоть сто миллионов лет.

Дальше Тьюринг показывает, как на такой машине можно, допустим, выполнять сложение; как посчитать, чему равно 1/3; или еще сложнее - как считать квадратный корень из двух.

А еще он доказывает, что любая машина такого рода не может посчитать произвольное действительное число - а лишь некоторые числа, которые он называет вычислимыми.

Как Тьюринг пришел к идее подобной машины? В ретроспекции это кажется несложным. Она просто имитирует человека, проводящего расчеты на бумаге, только сильно упрощает ситуацию, чтобы ее можно было рассмотреть математически. Вместо листка бумаги - бесконечная лента, по которой можно ездить взад и вперед; вместо пера - печатающая головка; ограниченность человеческой памяти заменяется одной-единственной текущей клеточкой; возможность делать промежуточные заметки сводится ко всей той же ленте, только другим символам на ней; а неопределенные "состояния ума" имитируются простыми состояниями машины, которые можно свести к длинным таблицам "в состоянии А, если видишь символ точки, сдвинься на клетку вправо, нарисуй там крестик и перейди в состояние Б".

Кроме того, мысль, что люди - это всего лишь очень сложные машины, и машины рано или поздно смогут делать то же, что люди, похоже, занимала Тьюринга постоянно. И последняя его работа была на все ту же тему: "Может ли машина мыслить". Именно в ней он предложил знаменитый тест - можете ли вы отличить машину от человека, просто задавая ей вопросы. Если не можете - то никакой разницы нет.

Если честно, попытка представить вычисления в виде действий некой машины была хоть и оригинальной, но не очень сложной. Например, до Тьюринга к тому же независимо пришел другой математик - Эмиль Пост, предложивший свою версию машины.

Но Тьюринг сделал следующий шаг, и это был шаг действительно гения. Он понял, что можно разработать (в математическом смысле, конечно) такую машину, которая может имитировать работу любой другой - и той, что считает, сколько будет 1/3, и той, что считает корень из двух, и той, что из системы аксиом может вывести все теоремы (такая машина тоже описана в его работе).

Этот хитрый девайс и называется Универсальной машиной Тьюринга.

Он, кстати, не только понял, что универсальная машина существует, но и придумал, как она должна быть устроена, то есть, по какой программе она должна работать - читать программу простой машины и имитировать каждый ее шаг.

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

Компьютер, по-современному. Все современные компьютеры и есть такие универсальные машины. Более того, ни один из них не круче Универсальной машины Тьюринг: что могут вычислить они, в принципе, может и она - только гораздо дольше.

А еще математик походя доказал,что невозможно, взяв программу для машины, определить с помощью другой машины, что эта программа в принципе рабочая - что она не зависнет, говоря по-современному, и вычислит именно то, что нужно.

Увы, так устроен наш мир, поэтому если ваш компьютер глючит, не колотите его кулаком и не поминайте маму Билла Гейтса. Ошибки в программе можно узнать, только запустив ее. Заранее - нельзя.

Додумался ли бы кто-то до идеи компьютера без Тьюринга? Да, конечно. Примерно в это же время немецкий инженер Конрад Цузе, далекий от математических высот, строил цифровую машину прямо у себя дома. И вряд ли он был один. Когда приходит время идеи, эта идея приходит в голову сразу многим людям.

Но это ничуть не умаляет заслуг Тьюринга. Он был одним из первых, в том числе в мире нового раздела математики - теории вычислимости.

Тьюринг, кстати, после войны, строил уже и настоящие компьютеры, из реле и катушек, и даже сам наматывал для них провода.

А что касается той идеи Гильберта, с которой все началось, то нам, живущим в информационном мире, теперь очень легко понять, что она была нерабочей.

Грубо говорят, Гильберт хотел взять горстку информации (несколько аксиом + программа для логического вывода) и получить из нее бесконечное количество информации (всю математику).

Так не бывает.

Оставить комментарий

Популярные посты:

• Ранее
• Архив