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

Question

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

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

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

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

---

EDIT:

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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