Кем был Алан Тьюринг?
Алан Тьюринг был блестящим британским математиком, сыгравшим ведущую роль в взломе нацистских шифров во время Второй мировой войны. В своей основополагающей статье 1936 года он доказал, что не может существовать универсального алгоритмического метода определения истины в математике и что математика всегда будет содержать неразрешимые утверждения. Его работа широко известна как фундаментальное исследование в области информатики и искусственного интеллекта.
"Алан Тьюринг родился в семье, принадлежавшей к захудалому британскому аристократическому роду, и получил суровое воспитание. Его предку в 1638 году был дарован титул баронета, который унаследовал один из его племянников и его потомки. Но младшим сыновьям, которыми были его отец и дед, не досталось никакой земли и мало богатства. Большинство представителей этой ветви рода становились либо священниками, как дедушка Алана, либо шли в колониальную гражданскую службу, как его отец, бывший мелким администратором в отдаленных районах Индии. Алан был зачат в Чхатрапуре, в Индии, а родился 23 июня 1912 года в Лондоне, где его родители проводили отпуск. Вскоре родители уехали обратно в Индию на несколько лет и передали его и его старшего брата на воспитание в семью отставного армейского полковника и его жены, живших в приморском городке на южном побережье Англии" У. Айзексон "Инноваторы"
Когда его мать вернулась в Англию, они с Аланом прожили вместе несколько лет, а затем в тринадцать лет он был отправлен в школу-интернат. Он поехал туда один на велосипеде, и ему потребовалось два дня, чтобы преодолеть более ста километров, отделявшие дом от школы, – его тяга к одиночеству проявилась в любви к длинным пробежкам и езде на велосипеде. Кроме того, в его характере имелась черта, роднившая его со многими другими инноваторами, которая так хорошо была описана его биографом Эндрю Ходжесом: “Алан с трудом учился чувствовать тонкую грань, отделявшую инициативность от неповиновения”.
В своих воспоминаниях его мать так описала обожаемого ею сына:
"Алан был ширококостным, крепкого телосложения и высокого роста, с квадратной, четко очерченной челюстью и непослушными каштановыми волосами. Его наиболее примечательной особенностью были глубоко посаженные, ясные, голубые глаза. Короткий, слегка вздернутый нос и линия рта, указывающая на чувство юмора, придавали ему юный, а иногда даже детский вид. Настолько, что, когда ему было сильно за тридцать, его временами по ошибке принимали за студента. Он был достаточно неряшлив, что проявлялось в его одежде и привычках. Он обычно носил слишком длинные волосы, на лоб падала челка, которую он откидывал обратно взмахом головы… Он мог быть отрешенным и мечтательным, погруженным в свои мысли, так что иногда казался нелюдимым. Временами его застенчивость приводила его к крайней бестактности. Он считал, что на самом деле ему очень бы подошла уединенная жизнь в средневековом монастыре."
В последний год обучения в Шерборне Тьюринг получил стипендию для учебы в Королевском колледже Кембриджа, куда он поступил в 1931 году и стал там изучать математику. Одной из трех книг, которые он купил на деньги от какой-то премии, была книга “Математические основы квантовой механики” Джона фон Неймана – гениального математика венгерского происхождения, который первым разработал архитектуру современного компьютера.
Тьюринг особенно заинтересовался аппаратом математической статистики, с помощью которой описываются события в квантовой физике на субатомном уровне и согласно которой они являются вероятностными, а не определяются соответствующими детерминистскими законами. Он считал (по крайней мере, пока был молод), что эта же неопределенность и неоднозначность на субатомном уровне, вероятно, позволяет человеку иметь свободу воли, которая, если это так, отличает его от машин. Другими словами, поскольку события на субатомном уровне не предопределены, не предопределены наши мысли и действия.
Всю остальную жизнь Тьюринга мучил вопрос, есть ли принципиальное отличие в работе человеческого разума и детерминированной машины, и постепенно он пришел к выводу, что различие не такое отчетливое, как он думал.
Еще ему интуитивно казалось, что подобно неопределенности, царящей в субатомном мире, существуют также математические задачи, которые не могут быть механически решены, и им суждено оставаться неразрешенными. В то время математики интенсивно работали над вопросами полноты и непротиворечивости логических систем, отчасти под влиянием Давида Гильберта – геттингенского гения, который, помимо многих других своих достижений, одновременно с Эйнштейном сформулировал общую теорию относительности в математической форме.
На конференции 1928 года Гильберт поставил три фундаментальных вопроса, касающихся любой формальной системы математики:
1. Полон ли набор правил в этой системе, в том смысле, что любое утверждение может быть доказано (или опровергнуто) с помощью правил только одной этой системы?
2. Является ли этот набор непротиворечивым (и значит, никакое утверждение не может быть признано одновременно и верным и ложным)?
3. Существует ли какая-то процедура, с помощью которой можно определить, является ли данное конкретное утверждение доказуемым, или остается возможность того, что некоторым утверждениям (к таким, например, относятся математические загадки, такие как последняя теорема Ферма, гипотеза Гольдбаха или гипотеза Коллатца) суждено оставаться неразрешенными?
Гильберт думал, что ответы на первые два вопроса должны быть положительными, а третий считал схоластическим. Он сформулировал это просто: “Нет такого понятия, как неразрешимая задача”.
В течение трех лет математик-логик австрийского происхождения Курт Гёдель (тогда ему было 25 лет, и он жил с матерью в Вене) получил на первые два из этих вопросов неожиданные ответы: “нет” и “нет”. В своей “теореме о неполноте” он доказал, что существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты. Приводя в качестве примера утверждения, которые не могут быть ни доказаны, ни опровергнуты, Гёдель показал, что любая формальная система, достаточно мощная, чтобы выражать обычную математику, неполна. Он также сформулировал сопутствующую теорему, которая с определенностью дала отрицательный ответ на второй вопрос Гильберта.
Оставался третий вопрос Гильберта – вопрос о разрешимости, или, как Гильберт назвал его, Entscheidungsproblem, “проблема разрешения”. Несмотря на то, что Гёдель привел утверждения, которые не могут быть ни доказаны, ни опровергнуты, возможно, этот странный класс утверждений можно было бы как-то определить и изолировать, оставив остальную часть системы полной и непротиворечивой. Когда великий профессор из Кембриджа математик Макс Ньюман читал Тьюрингу лекцию, в которой рассказывал о вопросах Гильберта, он сформулировал проблему Entscheidungsproblem в следующем виде:
“Существует ли «механический процесс», который можно было бы использовать для определения доказуемости данного логического утверждения? ”
Тьюрингу понравилась концепция “механического процесса”. “Логическая вычислительная машина”, которую он придумал (как мысленный эксперимент), была на первый взгляд довольно проста, но теоретически могла выполнять любые математические вычисления. Она состояла из бумажной ленты неограниченной длины, на которой внутри квадратиков содержались символы, в простейшем двоичном примере этими символами могли быть просто единица и пробел. Машина могла бы читать символы на ленте и выполнять определенные действия согласно заданной ей таблице команд. Таблица команд должна указать машине, что делать при любой конфигурации, в которой она оказалась,
Как может эта воображаемая машина ответить на третий вопрос Гильберта, то есть на проблему разрешения? Тьюринг подошел к проблеме, уточнив концепцию “вычислимых чисел”. Любое действительное число, которое определено с помощью математического правила, можно найти с помощью логической вычислительной машины. Даже иррациональное число, напримерр, можно вычислять с бесконечной точностью, используя конечную таблицу команд. Таким же образом можно рассчитать логарифм 7, квадратный корень из 2, или последовательность чисел Бернулли, или любое другое число или ряд, независимо от того, насколько сложно их вычислять, лишь бы эти вычисления задавались конечным числом правил. Все они были в терминологии Тьюринга “вычислимыми числами”.
Тьюринг продвинулся дальше и показал, что невычислимые числа также существуют. Это было связано с проблемой, которую он назвал “проблемой остановки”. Как он показал, никаким методом заранее нельзя определить, приведет ли любая заданная таблица инструкций в сочетании с любым заданным набором исходных данных к тому, что машина найдет ответ, или же она войдет в вычисление некоторых циклов и будет продолжать пыхтеть бесконечно долго, так и не получив ответа. Неразрешимость проблемы остановки, как он показал, означает, что нет решения и у Entscheidungsproblem – проблемы разрешения Гильберта. Несмотря на надежды Гильберта, оказалось, что никакая механическая процедура не может определить доказуемость каждого математического утверждения. Теория Гёделя о неполноте, неопределенность квантовой механики и ответ Тьюринга на третий вопрос Гильберта – все они наносили удары по механической, детерминистской и предсказуемой Вселенной.
Статья Тьюринга была опубликована в 1937 году под не очень выразительным названием “О вычислимых числах и их приложении к Entscheidungsproblem”. Его ответ на третий вопрос Гильберта оказался полезным для развития теории математики. Но гораздо более важным стал “побочный продукт” доказательства Тьюринга – его концепция логической вычислительной машины, которая вскоре стала известна как “машина Тьюринга”. В статье он утверждал: “Можно изобрести единую машину, которую можно использовать для вычисления любого вычислимого ряда”. Такая машина была бы способна выполнить команды, данные любой другой машине, и решить любые задачи, которые та машина может решить.
"В сентябре 1936 года, в ожидании опубликования своей статьи, двадцатичетырехлетний докторант плыл в Америку в каюте для пассажиров третьего класса на борту старенького океанского лайнера RMS Berengaria, прихватив с собой ценный латунный секстант. Его кабинет в Принстоне находился в здании математического факультета, который и тогда размещался в Институте перспективных исследований, где царили великие Эйнштейн, Гёдель и фон Нейман. Любящий новые знакомства и очень общительный фон Нейман особенно заинтересовался работой Тьюринга, хотя в человеческом плане они были очень разными." Уолтер Айзексон "Инноваторы"
Спасибо за внимание!
Все фото взяты с Яндекса в свободном доступе