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

Question

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

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

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

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

---

EDIT:

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

То, на что я надеялся, было набором руководящих принципов, таких как: «если он может делать X, Y и Z, он может , вероятно, сделать что-нибудь».

Answer 1

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

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

for i=1 to N {...}

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

while <i>bool_expr</i> {...}

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

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

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

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

Answer 10

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