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

Ответ 1

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

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

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

Ответ 2

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

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

Примером широко распространенной системы, которая не является Turing Complete, является реляционная алгебра, теоретическая основа SQL, описанная в документе Codd Реляционная модель для больших общих данных банки. Реляционная алгебра обладает свойством Godel Completeness, что означает, что она может выражать любые вычисления, которые могут быть определены в терминах исчисление предикатов первого порядка (т.е. обычные логические выражения). Однако это не Turing-Complete, поскольку он не может выразить произвольное алгоритмическое вычисление.

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

Некоторые более вопиющие примеры Turing Полноценные языки, относящиеся к домену, TeX и sendmail.cf,. В последнем случае на самом деле есть известный пример того, кто использует sendmail.cf для реализовать универсальный тренажер Turing Machine.

Ответ 3

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

Ответ 4

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

for i=1 to N {...}

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

while bool_expr {...}

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

• Способ записи в переменную
• Способ чтения переменной
• Форма условного goto (если инструкция, while loop и т.д.)

Ответ 8

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

Ответ 9

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

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

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

Ответ 10

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

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

Реальный вопрос: "Что хорошего?" Если ваш язык будет использоваться в определенном домене для решения конкретных проблем, может быть лучше найти способ формулировать решения на языке, который не является Turing Complete, и, таким образом, гарантировать ответ.

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

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

Ответ 11

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

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

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

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

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

Ответ 12

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

Ответ 13

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

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

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