Что означает лямбда в машине тьюринга
Детство, образование, увлечения
Родители Алана жили в индийском городе Чхатрапур. Отец — Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать — Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.
Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.
В детстве Алан и его старший брат Джон довольно редко видели своих родителей — их отец до 1926 года служил в Индии; дети оставались в Англии и жили на попечении в частных домах, получая строгое английское воспитание, соответствующее их положению на социальной лестнице. В рамках такого воспитания изучение основ естественных наук фактически не предусматривалось.
Маленький Алан обладал очень пытливым умом. Самостоятельно научившись читать в возрасте 6 лет, он просил у своих воспитателей разрешения читать научно-популярные книги.
В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но её опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School).
В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.
О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее
Я могу смотреть сквозь пальцы на его сочинения, хотя ничего ужаснее в жизни своей не видывал, я пытаюсь терпеть его непоколебимую небрежность и непристойное прилежание; но вынести потрясающую глупость его высказываний во время вполне здравой дискуссии по Новому Завету я, все же, не могу.
Тем не менее, в областях, интересовавших его, Тьюринг проявлял незаурядные способности.
В 1928 году, в возрасте 16 лет, Тьюринг ознакомился с работой Эйнштейна, в которой ему удалось разобраться до такой степени, что он смог догадаться из текста о сомнениях Эйнштейна относительно выполнимости Законов Ньютона, которые не были высказаны в статье в явном виде.
Университет
Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.
Кембриджский университет, обладавший особыми привилегиями, дарованными английскими монархами, издавна славился либеральными традициями, и в его стенах всегда царил дух свободомыслия. Здесь Тьюринг обретает – пожалуй, впервые – свой настоящий дом, где он смог полностью отдаться науке.
Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.
Во время обучения в колледже Алан Тьюринг изучал основы криптографии – то есть расшифровки данных. Это пригодилось ему во время Второй Мировой войны, когда учёный работал над расшифровкой немецких посланий.
Машина Тьюринга
Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.
В общем, МТ — способ определить некоторый класс алгоритмов:
— некоторые задачи можно решить конечным автоматом;
— для некоторых потребуется конечный автомат со стековой памятью;
— для других достаточно машины Тьюринга;
— для остальных требуется божественное откровение или другие неалгоритмизируемые методы.
С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.
Криптоанализ
Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:
Польский метод основывался на недоработках индикаторной процедуры, которые немцы исправили к маю 1940 года. Подход Тьюринга был более общим и основан на методе перебора последовательностей исходного текста, для которого он разработал начальную функциональную спецификацию Bombe.
Далее машина определяла противоречие, отбрасывала набор параметров и переходила к следующему. Таким образом, бо́льшая часть возможных наборов отсеивалась и для тщательного анализа оставалось всего несколько вариантов.
Первая машина была запущена в эксплуатацию 18 марта 1940 года. Перебор ключей выполнялся за счёт вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов.
Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.
В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.
Послевоенные годы
После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.
Несмотря на то, что постройка ACE была вполне осуществима, секретность, окружавшая Блэтчли-парк, привела к задержкам в начале работ, что разочаровало Тьюринга.
1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.
Franklin ACE 1200
Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.
В мае 1948 года получил предложение занять пост преподавателя и заместителя директора вычислительной лаборатории Манчестерского университета, занявшего к этому времени лидирующие позиции в разработке вычислительной техники в Великобритании.
В 1948 году Алан совместно со своим бывшим коллегой начал писать шахматную программу для компьютера, который ещё не существовал.
В том же году Тьюринг изобрёл метод LU-разложения, который используется для решения систем линейных уравнений, обращения матриц и вычисления определителя.
Тест Тьюринга
В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.
В 1951 году Тьюринг был избран членом Лондонского королевского общества.
Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.
Память
• именем ученого назван один из астероидов;
• ежегодная награда Ассоциации вычислительной техники называется Премией Тьюринга;
• на главной площади университета Суррея (Англия) есть статуя Тьюринга и одно из зданий факультета инженерных и физических наук названо в его честь;
• одна из аудиторий отдела информатики при Университете Лилль в Северной Франции назван в честь Алана М. Тьюринга;
• Манчестерский университет, Открытый университет, Университет Оксфорд Брукс и Университет Орхус (Дания) имеют корпуса имени Тьюринга и другие;
Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же время?
Похоже, что это случайно, что изобретенное Церковью исчисление оказалось завершенным по Тьюрингу, хотя позднее Черч использовал исчисление лямбда-выражений в качестве основы для того, что он назвал эффективно вычислимыми функциями (1936), к которым Тьюринг обращался в своей статье. ,
Простая теория типов Черча (1940) предлагает более умеренную типизированную теорию функций, которая достаточна для выражения синтаксиса логики высшего порядка, но не выражает все рекурсивные функции. Эта теория может рассматриваться как более созвучная первоначальной мотивации Церкви.
Рекомендации
Чёрч заявил, что лямбда-исчисление фиксирует интуитивную нотацию вычислимой функции до статьи Тьюринга, поэтому она называется тезисом Чёрча. Идея захвата общего понятия вычислимых функций идет еще дальше (например, общие рекурсивные функции Годеля), и Черч пытался ее уловить.
@Kaveh: Согласно Seldin (2006) логика Черча и Карри , цели и синтаксис лямбда-исчисления были разработаны в период с 1928 по 1929 годы, задолго до того, как Черч узнал об общем понятии рекурсивной функции. Мой ответ выиграл бы от графика времени, но у меня нет времени, чтобы собрать это прямо сейчас.
@Charles: Церковь была в Геттингене 1927-1928. Он наверняка знал, что происходит в теории рекурсивных функций и программе Гильберта. Результат Аккермана о непримитивной рекурсивной функции того же года. Церковь пыталась построить фундамент для математики. Все это произошло до статьи Тьюринга. Смотрите это . Клини доказал эквивалентность общих рекурсивных функций и -определимых функции перед работой Тьюринга. Ваш последний абзац вводит в заблуждение, поскольку он дает ощущение, что они были λ
@ Чарльз, как я уже писал, я согласен с тем, что первоначальной мотивацией Черча было создание основы (что-то вроде системы Фреге) (AFAIK), но он также рассматривал ее как вычислительную модель до работы Тьюринга. Я не думаю, что ответ должен быть удален, пересмотр второго параграфа должен сделать это хорошо. (Причина, по которой я это прокомментировал, заключается в том, что я чувствую, что в последнее время люди недооценивают работу Церкви по сравнению с вычислимостью.)
Я просто хотел бы отметить, что, хотя лямбда-исчисление и машины Тьюринга оба вычисляют один и тот же класс теоретико-числовых функций, они не являются абсолютно эквивалентными во всех возможных представлениях. Например, в теории реализуемости есть утверждения, которые могут быть реализованы машиной Тьюринга, но не лямбда-исчислением. Одним из таких утверждений является формальный тезис Церкви, который гласит:
T с е е е е с с е , Это невозможно сделать (я могу объяснить почему, если вы зададите это как отдельный вопрос).
У меня есть три связанных подвопроса, которые выделены пунктами ниже (нет, их нельзя разделить, если вам интересно). Андрей Бауэр писал здесь , что некоторые функции реализуются через машину Тьюринга, но не через лямбда-исчисление. Ключевой шаг его рассуждений:
Однако, если мы используем лямбда-исчисление, то [программа] c должна вычислять число, представляющее машину Тьюринга, из лямбда-члена, представляющего функцию f. Это невозможно сделать (я могу объяснить почему, если вы зададите это как отдельный вопрос).
- Я хотел бы видеть объяснение / неофициальное доказательство.
- Более того, если проблема заключается в самоанализе лямбда-члена, я думаю, что передача кодировки Лямбды-члена Гёделя также была бы приемлемой, не так ли?
С одной стороны, учитывая, что его пример включает вычисление в лямбда-исчислении числа шагов, необходимых машине Тьюринга для выполнения данной задачи, я не очень удивлен.
- Но поскольку здесь лямбда-исчисление не может решить проблему, связанную с машиной Тьюринга, мне интересно, можно ли определить аналогичную проблему для лямбда-исчисления и доказать, что она не разрешима для машин Тьюринга, или на самом деле существует разница в мощности в пользу Машины Тьюринга (что бы меня удивило).
Чтобы полностью определить модель вычисления более высокого типа, нам нужно указать соглашение о вызовах для функций, чтобы позволить одной функции вызывать другую функцию, которую она получает в качестве аргумента. В лямбда-исчислении стандартное соглашение о вызовах состоит в том, что мы представляем функции лямбда-терминами, и единственное, что вы можете сделать с лямбда-выражением в лямбда-исчислении, - это применить его. В типичных кодировках на машинах Тьюринга мы передаем функции в качестве аргументов, исправляя определенную кодировку Гёделя, а затем строки, представляющие индекс машины, которую вы хотите передать в качестве аргумента.
Стоит отметить, что для более высоких типов, если язык менее выразителен в одном порядке, он более выразителен на один порядок вверх, потому что функции контравариантны. Точно так же есть функции, которые вы можете написать в LC, что вы не можете с кодировкой в стиле ТМ (потому что они основаны на том факте, что вы можете передавать функциональные аргументы и знать, что получатель не может заглянуть внутрь функции, которую вы ему даете) ,
РЕДАКТИРОВАТЬ: Вот пример функции, определяемой в PCF, но не в кодировках TM + Goedel. Я объявлю isAlwaysTrue функцию
который должен возвращать true, если его аргумент игнорирует свой аргумент и всегда возвращает true, должен возвращать false, если его аргумент возвращает false на любых входах, и входит в цикл, если его аргумент входит в цикл на любых входах. Мы можем довольно легко определить эту функцию следующим образом:
где ⊥ вычисление цикла, а ∧ также оператор and для логических значений. Это работает, потому что unit → bool в PCF всего три жителя , и поэтому мы можем их полностью перечислить. Однако в модели стилей кодирования ТМ + Геделя p можно было бы проверить, сколько времени потребуется его аргументу, чтобы вернуть ответ, и на основании этого вернуть разные ответы. Таким образом, реализация isAlwaysTrue с ТМ не будет соответствовать спецификации.
Trying to wrap my head around lambda calculus but am really clueless right now.
First of all, I'm really confused WHAT it's actually supposed to be. I've found these definitions:
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. [Wikipedia]
The λ calculus can be called the smallest universal programming language of the world. The λ calculus consists of a single transformation rule (variable substitution) and a single function definition scheme. It was introduced in the 1930s by Alonzo Church as a way of formalizing the concept of effective computability. The λ calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to Turing machines. [UT Dallas]
So depending on who you ask, it's either a mathematical theorem, a turing complete programming language, or an abstract model of computation. I've settled on "useless symbol manipulation game beyond my comprehension", but maybe this will change after I've read the answers to this question.
I think I might be able to understand the basic syntax. A function that would normally look like this.
. look like this in λ-notation:
To now do something with the function in lambda calculus you just write the value behind the expression. Like this:
The variable then get's "bound" (whatever that means) to the variable in the expression in a process named α-conversion. Like this:
And then the output is produced in a process called β-reduction.
This is the output: y.
So far on the abstraction side of things, but what any of that actually means, I still don't really get.
Beyond that i don't really understand, how I'm supposed to deal with more complex Lambda terms. All explanations I can find don't go much further then introducing the basic concept, don't provide any further details and don't give any examples. What am I supposed to do when I get hit with stuff like this:
What's the significance of brackets here? What do they do? How do I handle multiple expressions in a row?
A concept that ALL explanations introduce as if it was self-explanatory is currying. Lambda expressions per definition are not allowed to take more then one argument (Why?). So what you do instead is you create an abstraction in the place of an expression and that. then does stuff?
I'm unable to link the mental model that lambda calculus introduces to that of a turing machine. How are they even remotely related?
Начнём мы с традиционного (но краткого) экскурса в историю. В 30-х годах прошлого века перед математиками встала так называемая проблема разрешения (Entscheidungsproblem), сформулированная Давидом Гильбертом. Суть её в том, что вот есть у нас некий формальный язык, на котором можно написать какое-либо утверждение. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность? Ответ был найден двумя великими учёными того времени Алонзо Чёрчем и Аланом Тьюрингом. Они показали (первый — с помощью изобретённого им λ-исчисления, а второй — теории машины Тьюринга), что для арифметики такого алгоритма не существует в принципе, т.е. Entscheidungsproblem в общем случае неразрешима.
Так лямбда-исчисление впервые громко заявило о себе, но ещё пару десятков лет продолжало быть достоянием математической логики. Пока в середине 60-х Питер Ландин не отметил, что сложный язык программирования проще изучать, сформулировав его ядро в виде небольшого базового исчисления, выражающего самые существенные механизмы языка и дополненного набором удобных производных форм, поведение которых можно выразить путем перевода на язык базового исчисления. В качестве такой основы Ландин использовал лямбда-исчисление Чёрча. И всё заверте…
λ-исчисление: основные понятия
Синтаксис
В основе лямбда-исчисления лежит понятие, известное ныне каждому программисту, — анонимная функция. В нём нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. п. — только функции, только хардкор. Потому что лямбда-исчисление — это не язык программирования, а формальный аппарат, способный определить в своих терминах любую языковую конструкцию или алгоритм. В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной.
Мы с вами рассмотрим его наиболее простую форму: чистое нетипизированное лямбда-исчисление, и вот что конкретно будет в нашем распоряжении.
Термы:
| переменная: | x |
| лямбда-абстракция (анонимная функция): | λx.t , где x — аргумент функции, t — её тело. |
| применение функции (аппликация): | f x , где f — функция, x — подставляемое в неё значение аргумента |
- Применение функции левоассоциативно. Т.е. s t u — это тоже самое, что (s t) u
- Аппликация (применение или вызов функции по отношению к заданному значению) забирает себе всё, до чего дотянется. Т.е. λx. λy. x y x означает то же самое, что λx. (λy. ((x y) x))
- Скобки явно указывают группировку действий.
Процесс вычисления
Рассмотрим следующий терм-применение:
Существует несколько стратегий выбора редекса для очередного шага вычисления. Рассматривать их мы будем на примере следующего терма:
который для простоты можно переписать как
(напомним, что id — это функция тождества вида λx.x )
В этом терме содержится три редекса:
Недостатком стратегии вызова по значению является то, что она может зациклиться и не найти существующее нормальное значение терма. Рассмотрим для примера выражение
(λx.λy. x) z ((λx.x x)(λx.x x))
Ещё одна тонкость связана с именованием переменных. Например, терм (λx.λy.x)y после подстановки вычислится в λy.y . Т.е. из-за совпадения имён переменных мы получим функцию тождества там, где её изначально не предполагалось. Действительно, назови мы локальную переменную не y , а z — первоначальный терм имел бы вид (λx.λz.x)y и после редукции выглядел бы как λz.y . Для исключения неоднозначностей такого рода надо чётко отслеживать, чтобы все свободные переменные из начального терма после подстановки оставались свободными. С этой целью используют α-конверсию — переименование переменной в абстракции с целью исключения конфликтов имён.
Так же бывает, что у нас есть абстракция λx.t x , причём x свободных вхождений в тело t не имеет. В этом случае данное выражение будет эквивалентно просто t . Такое преобразование называется η-конверсией.
На этом закончим вводную в лямбда-исчисление. В следующей статье мы займёмся тем, ради чего всё и затевалось: программированием на λ-исчислении.
Читайте также: