Существуют ли минимальные критерии для языка Тьюринга?

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

Из того, что я могу сказать из Википедии , язык должен поддерживать рекурсию или, по-видимому, должен иметь возможность работать без остановки. Это все, что нужно?

Я всегда думал, что -рекурсивные функции прибили его. Вот что определяет весь набор вычислимых функций; это наименьший набор функций, содержащий соотв. закрыто против:$\mu$

1. Константа функция$0$
2. Функция преемника
3. Выбор параметров
4. Композиция функций
5. Примитивная рекурсия
6. Оператор (ищите наименьший такой, что ...)$\mu$$x$

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

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

1. Постоянная 0
2. Шаг по _ + 1
3. Переменный доступ x
4. Объединение программ / операторов _; _
5. Обратные отсчеты for ( x to 0 ) do _ end
6. Пока петли while ( x != 0 ) do _ end

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

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

Из того, что я могу сказать из Википедии, язык должен поддерживать рекурсию или, по-видимому, должен иметь возможность работать без остановки. Это все, что нужно?

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

Кроме того, язык не должен поддерживать рекурсию так, как вы думаете. Просто неограниченный способ выражения циклов. Это может быть рекурсия, но также может быть цикл while или goto. Язык, у которого вообще нет функций, все еще может быть завершен по Тьюрингу. И снова циклы или рекурсивные функции не являются достаточным условием. Вам по-прежнему нужен способ выполнения другого кода в зависимости от условия и способ вычисления новых значений из старых (в противном случае все циклы / рекурсия будут либо бесконечными, либо вообще не будут выполняться).

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

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

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

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

Это не общий ответ на ваш вопрос, но по теореме о структурированном программировании все, что нужно, - это умение делать выбор (например, ifв C / C ++) и повторяться (например, whileв C / C ++). Редактировать: как отметил Дейв Кларк в комментариях, теорема о структурном программировании также требует последовательности. Первоначально я не перечислял это, поскольку считал само собой разумеющимся, что читатель поймет, что основные блоки других инструкций, такие как те, которые упоминались позже для чтения и записи в хранилище памяти и т. Д., Также были необходимы). Конечно, лучше быть явным; Вы должны быть в состоянии сделать эти вещи тоже.

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

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

Обратите внимание, что это не обязательно противоречит ответу sepp2k; это своего рода другой способ думать об одном и том же вопросе.

РЕДАКТИРОВАТЬ:

Также обратите внимание, что вам не нужно и то, ifи другое whileв C / C ++. Вы можете моделировать, ifиспользуя whileследующие:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

Следующий код всегда эквивалентен:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

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

РЕДАКТИРОВАТЬ:

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

Комбинаторы и где, и достаточно для выражения любого (замкнутого) лямбда-члена, следовательно, любой вычислимой функции. Смотрите эту страницу википедии для деталей.K ( S x y z ) = ( x z ( y z ) ) ( K x y ) = $\mathbf{S}$$\mathbf{K}$$(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$$(\mathbf{K}\ x\ y) = x$

Фактически, лямбда-член является достаточным основанием для выражения всех лямбда-терминов. Смотрите позже на той же странице википедии .$\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$

Языковые конструкции взаимозаменяемы

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

Чтобы доказать это - язык, который обеспечивает только операцию «вычитания и ветвления, если ноль» завершен по Тьюрингу; существуют полные языки Тьюринга, которые не предоставляют отдельную конструкцию "substract and ветвь, если ноль", следовательно, не существует конструкции или набора конструкций, которые являются обязательными.

Эффекты любой TP-полной языковой конструкции можно эмулировать с помощью конструкций любого другого TP-полного языка.