Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же время?
49
Есть ли связь между машиной Тьюринга и лямбда-исчислением - или они просто возникли примерно в одно и то же время?
Ответы:
Лямбда-исчисление старше, чем машинная модель Тьюринга, по-видимому, датируемая периодом 1928-1929 гг. (Seldin 2006), и было изобретено, чтобы заключить в себе понятие схематической функции, в которой нуждался Черч для основополагающей логики, которую он разработал. Он не был изобретен, чтобы охватить общее понятие вычислимой функции, и действительно, более слабая типизированная версия лучше послужила бы его целям.
Похоже, что это случайно, что изобретенное Церковью исчисление оказалось завершенным по Тьюрингу, хотя позднее Черч использовал исчисление лямбда-выражений в качестве основы для того, что он назвал эффективно вычислимыми функциями (1936), к которым Тьюринг обращался в своей статье. ,
Простая теория типов Черча (1940) предлагает более умеренную типизированную теорию функций, которая достаточна для выражения синтаксиса логики высшего порядка, но не выражает все рекурсивные функции. Эта теория может рассматриваться как более созвучная первоначальной мотивации Церкви.
Рекомендации
Примечание. Этот ответ существенно пересмотрен из-за возражений Каве и Сашо. Я рекомендую хронологию из Википедии, предложенную Каве, тезис «История Церкви - Тьюринга» , в котором есть некоторые цитаты из оригинальных статей.
источник
Я просто хотел бы отметить, что, хотя лямбда-исчисление и машины Тьюринга оба вычисляют один и тот же класс теоретико-числовых функций, они не являются абсолютно эквивалентными во всех возможных представлениях. Например, в теории реализуемости есть утверждения, которые могут быть реализованы машиной Тьюринга, но не лямбда-исчислением. Одним из таких утверждений является формальный тезис Церкви, который гласит:
источник
Они связаны как математически, так и исторически.
Лямбда-исчисление было разработано в 1928 - 1929 годах Алонзо Черчем (опубликовано в 1932 году).
Машина Тьюринга была разработана в 1935 - 1937 годах Аланом Тьюрингом (опубликована в 1937 году).
Алан Тьюринг был доктором философии Алонзо Черча. студент в Принстоне с 1936 по 1938 год.
Машины Тьюринга и лямбда-исчисление эквивалентны вычислительной мощности: каждая может эффективно моделировать другую.
источник
Entscheidungsproblem является одной из известных 23 задач, предложенных математиком Дэвидом Гильбертом.
Таким образом, лямбда-исчисление и машины Тьюринга не просто тесно связаны, но они являются эквивалентными моделями вычислений .
Возможно, вам также понравится читать «Аннотированный Тьюринг: экскурсия с гидом» по исторической статье Алана Тьюринга о вычислимости и машине Тьюринга Чарльза Петцольда . Эта книга содержит интересную информацию по теме.
источник
Машины Тьюринга и Лямбда-исчисление - две модели, которые отражают понятие алгоритма (механические вычисления). Лямбда-исчисление было изобретено Церковью для выполнения вычислений с функциями. Это основа функциональных языков программирования. По сути, любая задача, вычислимая (разрешимая) машинами Тьюринга, также вычисляется с использованием лямбда-исчисления. Таким образом, они представляют собой две эквивалентные модели вычислений (с точностью до полиномиальных факторов), и обе пытаются уловить силу любого механического вычисления.
источник