Каковы практические руководящие принципы для оценки «полноты» языка?

StackOverflow https://stackoverflow.com/questions/449014

Вопрос

я прочел "Что есть-заполнить" и страница в Википедии, но меня меньше заинтересованы в формальном доказательстве, чем практическими последствиями для завершения Тьюринга.

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

Есть ли минимальный набор функций, без которых невозможна полнота Тьюринга? Есть ли набор функций, которые практически гарантируют полноту?

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

РЕДАКТИРОВАТЬ:

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

Я надеялся, что набор руководящих принципов, таких как: «Если он может сделать x, y и z, это может вероятно Делать что-нибудь".

Это было полезно?

Решение

Вам нужна какая -то форма динамического конструкции распределения (malloc или жеnew или же cons сделает) и либо рекурсивные функции, либо какой -либо другой способ написания бесконечной циклы. Если у вас их есть, и вы можете сделать что-нибудь вообще интересного, вы почти наверняка заполняете.

Исчисление Lambda эквивалентно власти для машины Тьюринга, и если вы реализуете исчисление Lambda, на самом деле довольно весело писать программы Lambda Callus. Путь Более веселая программа для написания машины Тьюринга!

Единственное практическое значение, о которой я знаю,-это то, что вы можете писать программы, которые не прекращаются. Я использовал пару языков специального назначения, которые гарантируют прекращение и, следовательно, нет Тьюринг-полное. Иногда полезно отказаться от дополнительной выразительной власти в обмен на гарантированное прекращение.

Другие советы

'Turing overse' описывает свойство способности выразить любые произвольные алгоритмические вычисления, что было точкой Машина Тьюринга в первую очередь. Язык или логическая система может быть описана как «Turing Complete», если у него есть это свойство. С практической точки зрения все языки программирования общего назначения - и удивительно большое количество специальных целей - могут сделать это для соответствующего свободного определения (см. Ниже).

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

Примером широко распространенной системы, которая не является завершением, является реляционная алгебра, теоретическая основа SQL, как описано в статье CODD Реляционная модель для крупных общих банков данных. Реляционная алгебра обладает собственностью Горель Полнота, что означает, что он может выразить любые вычисления, которые могут быть определены в терминах Предикат первого порядка (т.е. обычные логические выражения). Тем не менее, он не является полным, поскольку он не может выразить произвольное алгоритмическое вычисление.

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

Некоторые более вопиющие примеры полных языков, специфичных для домена, Текс а также sendmail.cf,. Анкет В последнем случае на самом деле есть знаменитый пример того, как кто-то использует sendmail.cf to Реализуйте универсальный симулятор машины Тьюринга.

Если вы можете написать Brainf $ &# Интерпретатор на вашем языке, это заполняет Тьюринг. LOLCODE оказался, что он был заполнен именно таким образом.

Примеры языков, которые не являются заполненными, часто ограниченные петли, как:

for i=1 to N {...}

но не хватает неограничен петли, которые проверяют более общее состояние, например:

while bool_expr {...}

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

Также обратите внимание, что прибивает все возможным Перепечь конструкции может быть трудным; Например, я уверен, что шаблоны C ++ не были предназначены для того, чтобы быть полными ...

Я не уверен, есть ли «минимальный набор функций», но чтобы доказать, что язык завершен, вам нужно доказать, что он может подражать еще одной полной системе Тьюринга (не обязательно машина Тьюринга), до тех пор, пока Другая система, как известно, является полной. http://en.wikipedia.org/wiki/turing_complete#examples Имеет целый список полных систем Тьюринга. Некоторые из них проще, чем машины Тьюринга.

Я хотел бы добавить одну оговорку к тому, что сказал Норман Рэмси: машина Тьюринга имеет бесконечную память, и, следовательно, языки программирования, которые считаются завершенными, только в предположении, что память также бесконечна.

Brainfuck завершается и имеет только структуры петли и увеличение/уменьшение памяти, так что этого достаточно.

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

Скорее всего, вы программируете, хотя не имеют ничего общего с исчислением Lambda, поэтому для практического ответа минимум должен быть

  1. Способ написать переменную
  2. Способ прочитать переменную
  3. Форма условного Гото (если утверждение, в то время как петля и т. Д.)

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

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

Некоторые признаки:

  • Вы можете проверить память и манипулировать ее на основе текущего значения, а также использовать ее для управления потоком программ.
  • Эта память может быть выделена памятью, строки, к которым вы можете добавить, стек, на который вы можете выделить память через рекурсию и т. Д.
  • Программа может быть посредством итерации или посредством рекурсии на основе отбора.

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

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

Настоящий вопрос: «Что хорошего?» Если ваш язык будет использоваться в определенном домене для решения конкретных проблем, может быть лучше найти способ выразить решения на языке, который не завершен, и, следовательно, гарантированно дать ответ.

Вы всегда можете добавить полноту, написав: «Делай это, или что-то в этом роде; но сделай это с результатом, предоставленным Х» на любом другом полном языке Тьюринга, где X обеспечивается полным языком, не связанным с туристом.

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

Вы можете попробовать подражать Оис (Один компьютер на установленных инструкциях). Если вы можете эмулировать одну из инструкций там, то, поскольку эти отдельные инструкции могут использоваться для составления полной машины Turing, вы доказали, что ваш язык также должен быть полным.

Есть ли минимальный набор функций, без которых невозможна полнота Тьюринга? Есть ли набор функций, которые практически гарантируют полноту?

Да, вам необходимо иметь поток контроля условного по данным: то, что часто выражается как if. Анкет Например +-*/ Карманный калькулятор не является полным, так как нет способа выразить условные условия.

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

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

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

... чем в практических последствиях того, чтобы быть полным.

Я сомневаюсь, что есть какие -либо практические последствия для того, чтобы быть завершенным.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top