Почему функциональные языки Тьюринга завершены?

22

Возможно, мое ограниченное понимание предмета неверно, но это то, что я понимаю до сих пор:

  • Функциональное программирование основано на лямбда-исчислении, сформулированном Алонзо Черчем.

  • Императивное программирование основано на модели машины Тьюринга, созданной Аланом Тьюрингом, учеником Черча.

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

Если функциональное программирование основано на Lambda Calculus, а не на машине Тьюринга, то почему некоторые (или все) из них описаны как полные по Тьюрингу, а не как Lambda или что-то в этом роде? Является ли термин «полнота Тьюринга» каким-либо образом особенным для машин Тьюринга или это просто слово?

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

Если это так, то что было бы эквивалентно машине лямбда-исчисления?

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

Абдул
источник
6
Не ответ, но вы упомянули, что не все версии лямбда-исчисления являются Turing Complete. Простое типизированное лямбда-исчисление и более сильные версии Coq и Agda, основанные на проверке завершения, не являются завершенными по Тьюрингу (поскольку они имеют разрешимые проблемы остановки). Языки со строгой типизацией, такие как Haskell и SML, позволяют обойти это, разрешая произвольную рекурсию с помощью комбинатора с фиксированной точкой, термина с типом (a -> a) -> a.
Jmite
Это просто так неправильно говорить «определено, чтобы быть полным по Тьюрингу». Можем ли мы изменить название?
Андрей Бауэр
@AndrejBauer Спасибо за редактирование заголовка, но мне любопытно, почему это ( определено как выполнение завершено ) неправильно? Это потому что это прилагательное? Будет ли описание лучше, чем определение?
Абдул
1
@Abdul Ну, проблема в слове "определено". Если вы говорите, что «функциональные языки определены как полные по Тьюрингу», вы говорите, что либо в определении «функционального языка», либо в определении «полных по Тьюрингу» указывается, что функциональные языки являются полными по Тьюрингу. Фактически, ни одно определение не говорит это.
Таннер Светт

Ответы:

20

В двух словах :

Что характеризует императивные языки программирования как близкие к машинам Тьюринга и обычным компьютерам, таким как ПК (сами по себе ближе к машинам с произвольным доступом (ОЗУ), а не к машине Тьюринга), так это концепция явной памяти, которую можно модифицировать для хранения (промежуточные результаты ). Это автоматическое представление вычислений с концепцией состояния (включающего в себя как управление конечным состоянием, так и содержимое памяти), которое может меняться по мере выполнения вычислений.

Большинство других моделей более абстрактны. Хотя они могут выражать вычисления как последовательность шагов преобразования исходной структуры, эти преобразования применяются в некой межпространственной вселенной математических значений. Это может сохранить свойства, такие как ссылочная прозрачность, которые могут упростить математический анализ. Но он более далек от естественных физических моделей, которые полагаются на особенности памяти.

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

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

Дополнительные соображения :

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

Все они отражают некоторые аспекты различных методов, используемых математиками для выражения или проведения вычислений. Большинство из них до некоторой степени использовались в качестве основы для разработки некоторых языков программирования (например, Snobol для систем переписывания, APL для комбинаторов, Lisp / Scheme для лямбда-исчисления) и часто могут комбинироваться различными способами в современных языках программирования.

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

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

В то время, когда Алан Тьюринг создал свое вычислительное устройство, на столе находились другие предложения, которые могли бы служить формальным определением вычислимости, критической проблемой для основ математики (см. Entscheidungsproblem ). Эксперты того времени рассматривали предложение Тьюринга как наиболее убедительно охватывающее известную работу о том, какой должна быть вычислимость (см. Вычислимость и рекурсия , Р. И. Соаре, 1996, см. Раздел 3.2). Различные предложения оказались эквивалентными, но предложение Тьюринга было более убедительным. [из комментариев Ювала Фильмуса]

Следует отметить, что с аппаратной точки зрения наши компьютеры - это не машины Тьюринга, а то, что называется машинами произвольного доступа (ОЗУ) , которые также являются полными по Тьюрингу.

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

Это быстро привело к разработке моделей вычислений более высокого уровня, которые начали смешивать с ним различные вычислительные методы, такие как вызовы подпрограмм и функций, наименование места в памяти, определение области имен, количественное определение и фиктивные переменные, уже используемые в некоторой форме. в математике и логике и даже в очень абстрактных понятиях, таких как рефлексия ( Lisp 1958).

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

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

Теперь вы никогда не должны смотреть на свой компьютер как на сырое оборудование. Он содержит логическую схему, которая выполняет очень элементарную обработку. Но во многом это связано с микропрограммами внутри компьютера, о которых вы никогда не узнаете. Тогда у вас есть операционная система, которая делает вашу машину даже отличной от того, что делает аппаратное обеспечение. Кроме того, у вас может быть виртуальная машина, которая выполняет байт-код, а затем язык высокого уровня, такой как Pyva и Jathon или Haskell. или OCaml, который может быть скомпилирован в байт-код.

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

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

О специализированных машинных архитектурах

Фактически, дополняя ответ Питера Тейлора и развивая аппаратное и программное обеспечение, были созданы специализированные машины, которые лучше адаптированы к конкретной парадигме, и их базовое программное обеспечение было написано на языке программирования, основанном на этой парадигме.

Они включают

  • Burroughs B5000 и его преемники (1960 - е), которые были адаптированы для эффективной реализации рекурсии, представленной в свое время на языке Алгол 60 .

  • Western Digital WD / 9000 Pascal микродвигатель , а машина , основанная на микропрограммный байткод specialied для Паскаля языка программирования, в начале 1980 - х лет.

  • Несколько брендов Lisp Machines в 1980-х.

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

На самом деле, аппаратное обеспечение, специализирующееся на конкретных парадигмах, похоже, никогда не было успешным в долгосрочной перспективе. Причина в том, что технология компиляции для реализации любой парадигмы на ванильном оборудовании становилась все более и более эффективной, так что специализированное оборудование было не так уж и нужно. Кроме того, производительность аппаратного обеспечения быстро улучшалась, но стоимость улучшения (включая развитие базового программного обеспечения) легче амортизировалась на аппаратном обеспечении vanilla, чем на специализированном оборудовании. Специализированное оборудование не может конкурировать в долгосрочной перспективе.

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

Babou
источник
Выбор машины Тьюринга в качестве эталона в той степени, в которой он фактически сделан, мотивирован в основном исторически: Тьюринг был первым, кто предложил удовлетворительное определение вычислимости.
Ювал Фильмус
@YuvalFilmus И почему это было скорее «удовлетворительное определение вычислимости»?
Бабу
Это то, что подумал Гедель. У Боба Соаре есть несколько слов по этому поводу: cs.uchicago.edu/~soare/Publications/compute.ps .
Ювал Фильмус
@YuvalFilmus Это 46 страниц. Я имею в виду, я привожу некоторые причины, почему это должно быть более удовлетворительным. Они могут быть наивными. Если есть более убедительные, которые объясняют успех, стоит упомянуть явно.
Бабу
Посмотрите на раздел 3.2. Существовали предыдущие определения вычислимости, но они не были убедительными. Тьюринг был первым, который был убедительным, по крайней мере, для некоторых ключевых людей.
Ювал Фильмус
21

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

Императивные языки не основаны на машинах Тьюринга. Они основаны на ОЗУ машин. Ваш компьютер является машиной ОЗУ. Машины Тьюринга - хорошая теоретическая модель, но они не очень хорошая модель реальных компьютеров.

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

Юваль Фильмус
источник
«Машины Тьюринга - хорошая теоретическая модель, но они не очень хорошая модель реальных компьютеров». За исключением отсутствия бесконечной памяти, каковы другие причины того, что это не очень хорошая модель для реальных компьютеров? Кроме того, правильно ли я думал, что функциональные языки основаны на лямбда-исчислении?
Абдул
5
λ
11
Императивные языки , как правило, позволяют доступы массива в постоянная время, в C A[x]. Машины Тьюринга не могут делать это в постоянное время. Вот почему даже в теоретической информатике время выполнения алгоритмов анализируется на модели машины ОЗУ, а не на модели машины Тьюринга.
Ювал Фильмус
14
На самом деле, машины Тьюринга - это хороший компьютер… за исключением того, что когда Тьюринг написал свою статью, «компьютер» был описанием работы человека, работающего с ручкой и бумагой. Головка для чтения / записи представляет собой модель ручки, лента представляет собой модель бесконечной стопки листов бумаги (просто нарежьте их на маленькие полоски и склейте их вместе), алфавит - это модель нашего алфавита. и конечные переходы - это модель ограниченного количества правил, которые можно держать в голове.
Йорг Миттаг
3
Это было лучшее понимание того, почему ад Тьюринг выбрал машину Тьюринга. Мне всегда было интересно, «почему он выбрал такую ​​дурацкую модель вычислений». Я всегда думал, что если бы мне пришлось изобретать теорию вычислений (да поможет нам Бог; мы бы не очень далеко продвинулись), я бы, вероятно, все же выбрал бы лучшую модель вычислений. Теперь я понимаю, откуда он идет, и это имеет гораздо больше смысла.
Джейк
10

Потому что «полный по Тьюрингу» означает «он может вычислить все, что может вычислить машина Тьюринга».

Дэвид Ричерби
источник
Полное по Тьюрингу также можно назвать в честь Тьюринга (человека), который придумал первое философское определение вычислимости; или его можно назвать в честь статьи Тьюринга, в которой он описывает эту концепцию.
Юваль Фильмус
1
@YuvalFilmus: его можно назвать по имени мамы Алана Тьюринга, но здесь утверждается, что это не так ;-)
Стив Джессоп,
@YuvalFilmus Может быть (хотя, насколько я знаю, нет). Но откуда взялся этот термин, имеет второстепенное значение. Здесь важно то, что означает этот термин .
Дэвид Ричерби
2
Это коротко и мило, но, может быть, слишком коротко. Что делает машина Тьюринга? Хорошо среди того, что они «делают» - это читать и записывать ленты, а лямбда-выражения этого не делают. Лучше было бы: «Модели вычисления, полные по Тьюрингу, позволяют вычислять все вычисляемые функции».
Теодор Норвелл
@TheodoreNorvell Я думаю, что ваш комментарий похож на то, что я думал. Я знал, что лямбда-исчисление и машина Тьюринга эквивалентны по мощности, но различаются по механизму (и теперь я узнал, что есть другие), но мне было интересно, был ли термин «полнота Тьюринга» каким-либо образом особенным для машины Тьюринга, или если бы это было просто имя.
Абдул
6

На один из ваших вопросов, похоже, еще не ответили:

Если это так, то что было бы эквивалентно машине лямбда-исчисления?

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

Питер Тейлор
источник
0

Изобретенные Церковью функциональные языки в форме лямбда-исчисления были доказаны Тьюрингом завершенными. Это фактическое математическое доказательство, которое можно найти в опубликованных научных работах, «сводя» лямбда-исчисление к операциям / вычислениям на машинах Тьюринга. во времена газеты Турингса 1936 года и позже были предложены / распространены различные «комплексные» модели вычислений. это не было сразу понято, что все были эквивалентны. доказательство (я), что они были эквивалентны, были опубликованы примерно в конце 1930-х и 1940-х годов после газеты Турингс.

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

ВЗН
источник
другими словами, можно сказать, что Тьюринг был первым, кто идентифицировал / «признал» значение феномена завершенности Тьюринга, и, в свою очередь, К.С. «признает» его за это монументальное достижение с помощью использования этого термина.
vzn
Икс