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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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