Каковы практические рекомендации по оценке языковой "полноты Тьюринга"?
Я прочитал "Что такое полная проверка" и страницу Википедии, но меня меньше интересуют формальные доказательства, чем практические последствия того, чтобы быть полной Тьюринга.
На самом деле я пытаюсь решить, можно ли использовать только что разработанный мной игрушечный язык как язык общего назначения. Я знаю, что могу доказать, что смогу написать на ней машину Тьюринга. Но я не хочу проходить это упражнение, пока не буду уверен в успехе.
Существует ли минимальный набор функций, без которых полнота по Тьюрингу невозможна? Есть ли набор функций, который практически гарантирует полноту?
(Я предполагаю, что условное ветвление и читаемое / записываемое хранилище памяти дадут мне большую часть пути туда)
РЕДАКТИРОВАТЬ:
Я думаю, что ушел в тупик, сказав "Тьюринг завершен". Я пытаюсь с достаточной уверенностью предположить, что вновь изобретенный язык с определенным набором функций (или, альтернативно, виртуальная машина с определенным набором команд) сможет вычислить все, что стоит вычислить. Я знаю, что доказать, что вы можете построить машину Тьюринга с ее помощью, это один, но не единственный способ.
То, на что я надеялся, было набором руководящих принципов, таких как: "если он может делать X,Y и Z, он, вероятно, может делать что угодно".
13 ответов
Вам нужна некоторая форма конструкции динамического размещения (malloc или жеnew или же cons будет делать) и либо рекурсивные функции или какой-либо другой способ написания бесконечного цикла. Если у вас есть такие возможности и вы можете сделать что-нибудь интересное, вы почти наверняка готовы к Тьюрингу.
Лямбда-исчисление по мощности эквивалентно машине Тьюринга, и если вы реализуете лямбда-исчисление, на самом деле довольно интересно писать программы для лямбда-исчисления. Намного веселее, чем писать программу для машины Тьюринга!
Единственное практическое следствие полноты по Тьюрингу, о котором я знаю, это то, что вы можете писать программы, которые не завершаются. Я использовал пару языков специального назначения, которые гарантируют завершение и, следовательно, не являются полными по Тьюрингу. Иногда полезно отказаться от дополнительной выразительной силы в обмен на гарантированное завершение.
"Полнота Тьюринга" описывает свойство возможности выражать любые произвольные алгоритмические вычисления, что и было целью машины Тьюринга в первую очередь. Язык или логическая система может быть описана как "Turing Complete", если она обладает этим свойством. С практической точки зрения все языки программирования общего назначения - и удивительно большое количество языков специального назначения - могут сделать это для достаточно свободного определения (см. Ниже).
Однако строгое определение полноты по Тьюрингу подразумевает неограниченную емкость хранилища, что, конечно, физически невозможно. Учитывая это, никакая физическая машина не может быть завершенной по Тьюрингу, но это ограничение обычно смягчается (по крайней мере, неформально) приписывая полноту по Тьюрингу языку программирования. Один из тривиальных тестов на полноту Тьюринга для языка заключается в том, можно ли использовать язык для реализации симулятора Тьюринга.
Примером широко распространенной системы, которая не является полной по Тьюрингу, является реляционная алгебра, теоретическая основа 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 содержит полный список полных систем Тьюринга. Некоторые из них проще, чем машины Тьюринга.
Brainfuck завершен по Тьюрингу и имеет только циклические структуры и увеличение / уменьшение памяти, так что этого достаточно.
С другой стороны, нет никакого способа изменить какое-либо значение в лямбда-исчислении, но оно завершено по Тьюрингу, так что это вполне возможно сделать без изменяемой памяти.
Скорее всего, ваша программа не имеет ничего общего с лямбда-исчислением, поэтому для практического ответа минимум должен быть
- Способ записи в переменную
- Способ чтения переменной
- Форма условного перехода (оператор if, цикл while и т. Д.)
Я хотел бы добавить одно предостережение к тому, что сказал Норман Рэмси: машина Тьюринга имеет бесконечную память, и, следовательно, языки программирования, которые считаются полными по Тьюрингу, находятся только в предположении, что память также бесконечна.
Я не помню, чтобы я видел что-то вроде минимальных возможностей для полноты по Тьюрингу. Однако, если ваш язык поддерживает циклы и условные переходы, шансы на его завершение по Тьюрингу хорошие. Тем не менее, единственный способ доказать это по-прежнему аналогично машине Тьюринга или другому языку Тьюринга.
Вы можете попробовать эмулировать OISC (один компьютер с набором инструкций). Если вы можете эмулировать одну из инструкций, то, поскольку эти единственные инструкции можно использовать для создания машины Turing Complete, вы доказали, что ваш язык также должен быть Turing Complete.
Если вы можете реализовать машину Тьюринга (насколько они могут быть реализованы, поскольку они представляют собой математические конструкции с неограниченной памятью [размер ленты бесконечен]), то вы можете быть уверены, что она завершена.
Некоторые показания:
- Вы можете проверить память и манипулировать ею на основе текущего значения, а также использовать его для управления потоком программ.
- Эта память может быть выделена памятью, строками, к которым вы можете добавлять, стеком, на который вы можете выделить память посредством рекурсии и т. Д.
- Поток программы может быть через итерацию или рекурсию на основе выбора.
Существует ли минимальный набор функций, без которых полнота по Тьюрингу невозможна? Есть ли набор функций, который практически гарантирует полноту?
Да, вы должны иметь контроль потока данных: что часто выражается как if, Например, +-*/ Карманный калькулятор не является полным по Тьюрингу, поскольку нет способа выразить условные выражения.
Вы также должны иметь возможность выразить переход к более ранней точке программы, поверх которой вы могли бы реализовать цикл. Например, BPF, который запрещает обратные переходы, чтобы гарантировать завершение программы, также не завершен по Тьюрингу.
Вам нужно некоторое пространство для чтения, записи и произвольно большого размера. Например, язык, который имеет только две 32-битные переменные, ограничен в том, что он может вычислять. У вас есть много вариантов структурирования хранилища: память, адресуемая указателями, массивами, стеками, консолидированными ячейками, чистыми структурами данных и т. Д.
Вдобавок к этому вы можете построить любой другой язык программирования: он может быть не простым или быстрым, но этого достаточно.
Любой язык, способный к прекращению, является в значительной степени Turing Complete. Вы можете сделать язык не способным завершаться, предоставив ему неограниченные циклические структуры (например, циклы While или Goto, который может снова достичь себя), или предоставив ему общую рекурсию (позволяя функции вызывать себя без ограничений.)
Как только вы завершите тестирование по Тьюрингу, вы можете выполнять такие действия, как интерпретация других языков Turing Complete, включая ваш собственный.
Реальный вопрос - что хорошего в этом? Если ваш язык будет использоваться в определенной области для решения конкретных проблем, может быть лучше найти способ сформулировать решения на языке, который не является полным по Тьюрингу, и, таким образом, гарантированно даст ответ.
Вы всегда можете добавить полноту Тьюринга, написав "Делайте это, то или что-то еще, но делайте это с результатом, предоставленным X" на любом другом языке Turing Complete, где X предоставляется языком, не полным по Тьюрингу.
Конечно, если вы хотите использовать только один язык, возможно, лучше использовать Turing Complete...
... чем практические последствия того, чтобы быть завершенным по Тьюрингу.
Я сомневаюсь, что есть практические последствия того, что Тьюринг завершен.
Если вы посмотрите на некоторые примеры полных машин Тьюринга, например, оригинальную машину Тьюринга, вы увидите, что они настолько далеки от того, чтобы быть полезными для реальных вычислений, что концепция должна представлять только теоретический интерес.