Каковы практические рекомендации по оценке полноты Тьюринга языка?

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

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

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

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

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

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

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

Еще несколько вопиющих примеров предметно-ориентированных языков Turing Complete - это TeX и sendmail.cf,. В последнем случае есть известный пример использования sendmail.cf для реализовать универсальный симулятор машины Тьюринга.

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

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

for i=1 to N {...}

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

while bool_expr {...}

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

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

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

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

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

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

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

1. Способ записи в переменную
2. Способ чтения переменной
3. Форма условного перехода (оператор if, цикл while и т. Д.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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