Вклад Алана Тьюринга в информатику

Алан Тьюринг , один из пионеров (теоретической) информатики, внес много полезных научных вкладов в нашу область, включая определение машин Тьюринга, тезис Черча-Тьюринга, неразрешимость и тест Тьюринга. Однако его важные открытия не ограничиваются перечисленными мною.

В честь его 100-летия я подумал, что было бы неплохо попросить более полный список его важных вкладов в информатику, чтобы лучше оценить его работу.

Итак, каков важный / влиятельный вклад Алана Тьюринга в информатику?

Этот вопрос очень похож на вопрос о вкладе Ньютона в физику или Дарвина в биологию! Тем не менее, есть интересный аспект в вопросе, которым уже воспользовались многие комментаторы: а именно, что помимо огромного вклада, который всем известен, существует множество меньших вкладов, о которых большинство людей не знают, а также множество идей что мы считаем более «современным», но что Тьюринг продемонстрировал в различных замечаниях, что он прекрасно понимал. (Между прочим, то же самое верно для Ньютона и Дарвина.)

Несколько примеров, которые мне нравятся (помимо упомянутых ранее):

В «Вычислительная техника и интеллект» Тьюринг включает довольно современное обсуждение преимуществ рандомизированных алгоритмов:

Вероятно, целесообразно включить случайный элемент в обучающую машину. Случайный элемент весьма полезен, когда мы ищем решение какой-то проблемы. Предположим, например, что мы хотим найти число от 50 до 200, равное квадрату суммы его цифр, мы можем начать с 51, затем попробовать 52 и продолжать до тех пор, пока не получим работающее число. В качестве альтернативы мы можем выбирать числа случайным образом, пока не получим хорошее. Преимущество этого метода состоит в том, что нет необходимости отслеживать значения, которые были опробованы, но недостатком является то, что можно попробовать одно и то же дважды, но это не очень важно, если есть несколько решений. Систематический метод имеет недостаток в том, что в регионе может быть огромный блок без каких-либо решений, который должен быть исследован в первую очередь, Теперь учебный процесс можно рассматривать как поиск формы поведения, которая удовлетворит учителя (или какой-то другой критерий). Поскольку, вероятно, существует очень большое количество удовлетворительных решений, случайный метод кажется лучше систематического. Следует отметить, что он используется в аналогичном процессе эволюции.

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

Помимо технических результатов из докторской диссертации Тьюринга 1939 года (упомянутой Львом Рейзиным), этот тезис чрезвычайно примечателен для введения концепций оракулов и релятивизации в теорию вычислимости. (Некоторые люди могут пожелать, чтобы Тьюринг никогда не делал этого, но я не один из них! :-D)

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

Я не знал об этом до недавнего времени.

1) LU-разложение матрицы происходит из-за Тьюринга! Учитывая, насколько фундаментальным является разложение LU, это один вклад, который заслуживает того, чтобы быть выделенным и известным более широко (1948).

2) Тьюринг первым предложил «бумажный алгоритм» для шахмат. На тот момент первые цифровые компьютеры все еще строились (1952).

В шахматном программировании было много людей, связанных с Шенноном, Тьюрингом, Хербом Саймоном, Кеном Томпсоном и т. Д. Последние два получили премию Тьюринга. И Симом, конечно же, выиграл Нобелевскую премию. (Шеннон придумал способ оценить шахматную позицию в 1948 году.)

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

Во время Второй мировой войны Тьюринг использовал идею вычислительных и электромеханических (в отличие от человека) компьютеров, чтобы помочь создать бомбу Тьюринга-Уэлчмана и другие инструменты и формальные методы для криптоанализа. Он начал трансформацию криптологии, формы искусства, криптографии, науки, которую завершил Клод Шеннон. Алан Тьюринг рассматривал криптологию через алгоритмические линзы.

В 1948 году Тьюринг последовал его интерес к мозгу, чтобы создать первую обучающую искусственную нейронную сеть . К сожалению, его рукопись была отклонена директором NPL и не опубликована (до 1967 года). Однако, это предшествовало и обучению Хебби (1949) и персептронам Розенблатта (1957), которые мы обычно ассоциировали с тем, чтобы быть первыми нейронными сетями. Тьюринг предвидел фундамент коннекционизма (все еще огромной парадигмы в когнитивной науке) и вычислительной нейробиологии. Алан Тьюринг смотрел на мозг через алгоритмические линзы.

В 1950 году Тьюринг опубликовал свою знаменитую вычислительную технику и интеллект и создал ИИ. Это оказало преобразующее влияние на психологию и когнитивную науку, которые продолжают рассматривать познание как вычисление внутренних представлений. Алан Тьюринг смотрел на разум через алгоритмические линзы.

Наконец, в 1952 году (как упомянул @vzn) Тьюринг опубликовал «Химическую основу морфогенеза»., Это стало его самой цитируемой работой. В нем он задал (и начал отвечать) вопрос: как сферически-симметричный эмбрион превращается в несферически-симметричный организм под действием сохраняющей симметрию химической диффузии морфогенов? Его подход в этой статье был очень физическим, но некоторые подходы имели вид TCS; Его статья сделала строгие качественные утверждения (действительные для различных констант и параметров) вместо количественных утверждений, основанных на конкретных (в некоторых областях: потенциально невозможно измерить) констант и параметров. Незадолго до своей смерти он продолжил это исследование, работая над основными идеями того, что должно было стать искусственным моделированием жизни, и более дискретным и недифференцированным подходом к биологии. В блогеЯ размышляю о том, как он будет развивать биологию, если у него будет больше времени. Алан Тьюринг начал рассматривать биологию через алгоритмические линзы.

Я думаю, что наибольший (и часто игнорируемый) вклад Тьюринга в информатику показал, что мы можем получить глубокое понимание, рассматривая науку через алгоритмический объектив. Я могу только надеяться, что мы чтим его гения, продолжая его работу.

Смежные вопросы

• Алгоритмический объектив в социальных науках

• Современные методы лечения нейронных сетей типа А Алана Тьюринга

• Влияние подхода Алана Тьюринга к морфогенезу

Одним менее известным вкладом является оценка Гуд-Тьюринга для оценки доли популяции, «еще не замеченной» при взятии образцов. Это используется в биоразнообразии.

Документ Тьюринга « Проверка большой рутины», который был представлен на конференции в Кембридже в 1949 году, опередил формальные рассуждения о программах, разработанных Флойдом и Хоаром, почти на два десятилетия. Статья состоит всего из трех страниц и содержит идею использования инвариантов для доказательства свойств программ и обоснованность для подтверждения завершения.

Как можно проверить рутину, чтобы убедиться, что она правильная?

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

Тьюринг был заинтересован и сделал некоторую основную работу в химических моделях реакции-диффузии. эта область исследований значительно расширилась, так как он начал исследовать это. было показано, что он связан с вычислимостью, например, в некотором смысле «полный по Тьюрингу» [1]. химические реакции могут быть смоделированы с помощью сложных нелинейных дифференциальных уравнений, поэтому в некотором смысле было показано, что нелинейные дифференциальные уравнения с достаточной сложностью могут моделировать машины Тьюринга. вытекает из его работы 1951 года "Химические основы морфогенеза" [4]

[1] химическая кинетика Тьюринга универсальна по Magnasco в PRL 97

[2] Тьюринговые структуры в простых химических реакциях

[3] Паттерны Тьюринга в линейных химических реакционных системах с нелинейной перекрестной диффузией по Францу.

[4] химические основы морфогенеза, википедия

Вот еще один, который я нашел в блоге Скотта Ааронсона (и Q + A взят оттуда):

В своей докторской диссертации В диссертации Тьюринг изучил вопрос ( - теория):$F_α$

При заданной машине Тьюринга которая работает вечно, всегда ли существует порядковый номер α такой, что доказывает, что работает вечно?$M$$F_α$$M$

Тьюринг доказал:

Для любой машины Тьюринга которая работает вечно, существует кодировка ее аксиом ( ), которая доказывает, что работает вечно.$M$$F_{\omega+1}$$M$

К сожалению, определения и технические детали сложнее суммировать, но пост в блоге хорошо объясняет их.

Вот обширный, тщательно изученный / подробный онлайн-опрос 9p / ретроспектива конкретных и более общих / долгосрочных вкладов Тьюринга в «Уведомлениях Американского математического общества» С. Б. Купера к 100-летию « Неисчислимость после Алана Тьюринга» . некоторые другие вклады, упомянутые в этом обзоре:

• Ошибки округления в матричных процессах, бумага, 1948 г., влиятельные в численном анализе и научных вычислениях в теории вычислений

• неопубликованные 1948 Национальная физическая лаборатория доклад Intelligent Machinery описывает раннюю Коннекшионистский модель, похожую и одновременные с известными McCulloch и Pitts нейронных сетей .

• указывает на то, что анализ Тьюринга и теория морфогенеза могут рассматриваться как ранняя интеллектуальная основа массивной (и все еще продолжающейся / активной) более поздней теории самоорганизации и возникающих явлений .

(так далее)