为什么要解除的淘汰问题可判定到Goto语言限制常量和变量的最高值？

Question

这是从我大学的旧考试中获取，我正在使用我为即将到来的考试做好准备：

给定是一种语言 $ \ text {goto} _ {17} ^ c \ subseteq \ text {goto} $ 。此语言完全包含那些 $ \ text {got and {got 程序，其中没有常数超过 $ 17 $ NOR以上的任何变量 $ c $ 。

$ goto $ 这里描述了在 $ goto $ 语言中写入的所有程序集以下元素：

与变量 $ v_i \ in \ mathbb {n} $ 和常量 $ c \ in \ mathbb {n} $
赋值： $ x_i：= c，x_i：= x_i \ pm c $
条件跳转：如果（比较）转到 $ l_i $
haltcommand：停止

我目前正在努力追究证据的形式化，但这就是我到目前为止所在的，措辞非常随便： 对于此集合中的任何给定的程序，我们知道它是有限的。有限程包含有限量的变量和有限量的状态，或者是进入的线条。因此，存在该过程的有限配置。如果我们让这个程序运行，我们可以保留我们已经看到的所有配置的列表。也就是说，所有使用的变量值和程序状态的组合。如果我们让程序运行，必须有两件事之一最终发生： 程序停止。在这种情况下，我们返回是的，并已决定停止。 该程序达到以前已记录的配置。当语言是确定性的，这意味着我们必须已经完成了全循环，这将完全重复。

否其他案例可以存在，因为这将是指我们在没有重复配置的情况下继续在有限代码上运行。这意味着在每一步之后，在我们的无限步骤中，有一个新配置。这意味着存在无限的配置，这是一个矛盾。

这是正确的吗？此外，如果是，如何更正式的证明？如果没有，如何正确证明？

Answer 1

有一个有限数量的不同状态（变量的值和程序计数器的一组）。您的“有限的Goto程序”只是一种（凌乱）的方式来描述一个确定性有限自动机。

或只是程序状态是有限的，肯定可以映射所有可能的非循环计算（通过宽度首先搜索状态和邻居图的东西）。