Остановка на нетурингово-полных языках

Question

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

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

Answer 1

Проблема остановки не действует на языки. Скорее действует на машины (то есть программы): он спрашивает, останавливается ли данная программа на заданном входе.

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

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

Обычно модели с бесконечными ресурсами (например, неограниченные ТМ и КПК), не может быть остановлен, но было бы лучше исследовать модели и их открытые проблемы индивидуально.

(Извините за все ссылки на Википедию, но на самом деле это очень хороший ресурс для такого рода вопрос.)

Answer 2

Да. Одним из важных классов такого рода являются примитивно-рекурсивные функции . Этот класс включает в себя все основные вещи, которые вы ожидаете сделать с числами (сложение, умножение и т. Д.), А также некоторые сложные классы, такие как @adrian, упомянутые (регулярные выражения / конечные автоматы, контекстно-свободные грамматики / pushdown автоматы). Однако существуют функции, которые не являются примитивно-рекурсивными, такие как функция Аккермана .

На самом деле довольно просто понять примитивные рекурсивные функции. Это функции, которые вы можете получить в языке программирования, который не имеет истинной рекурсии (поэтому функция f не может вызывать сама себя, напрямую или через другую функцию g, которая затем вызывает f и т. Д.) И не имеет циклов while, вместо этого, ограниченный для петель. Ограниченный цикл for похож на «for i от 1 до r», где r - это переменная, которая уже была вычислена ранее в программе; Кроме того, я не могу быть изменен в течение цикла. Смысл такого языка программирования в том, что каждая программа останавливается.

Большинство программ, которые мы пишем, на самом деле являются примитивно-рекурсивными (я имею в виду, могут быть переведены на такой язык).

Answer 3

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

Несколько месяцев назад на LtU была дискуссия об этом: http://lambda -the-ultimate.org / узел / 2846