Почему проблема остановки, решительна для Goto языков, ограниченных на самых высоком цене констант и переменных?

Question

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

Дано - это язык $ \ text {goto} _ {17} ^ c \ subsEtq \ text {goto} $ . Этот язык содержит именно те эти $ \ text {goto} $ Программы, в которых нет постоянного превышения $ 17 $ Ни никакой переменной никогда не выше $ C $ .

$ Goto $ Здесь описывает набор всех программ, написанных в $ Goto $ Из следующих элементов:

с переменными $ v_i \ in \ mathbb {n} $ и константы $ c \ in \ mathbb {n} $

Назначение: $ x_i:= c, x_i:= x_i \ pm c $
Условный прыжок: если (сравнение) GoTo $ l_i $
HaltCommand: HALT

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

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

Это правильно? Кроме того, как бы более официальный доказательств выглядит, если это? Если нет, как будет правильный вид доказательства?

Answer 1

Существует конечное число разных состояний (набор значений переменных и счетчик программы).Ваши «ограниченные программы GOTO» являются просто (грязным) способом описания детерминированного конечного автомата.

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