“简单 For 循环”在可计算性理论中意味着什么？

Question

我正在阅读维基百科页面 原始递归函数 但有一个短语来描述简单的 for 循环，我真的不明白。谁能向我解释一下吗？

词组： 在进入循环之前可以确定每个循环的迭代次数的上限

这 维基百科 页

Answer 1

Wikipedia陈述是非正式的，非常暧昧。例如，让 $ a（n，n）$ 是 ackermann函数，并考虑以下程序，其中 $ n $ 是输入：

x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x

.

此函数不是原始递归，尽管存在提前已知的迭代次数的绑定。

更好的解释是循环编程语言。循环中的每个循环都运行 $ x_i $ times，其中 $ x_i $ 是一个变量，以及数量迭代是 $ x_i $ 运行之前的值。例如：

  LOOP x DO
      x ← x + 1
  END

.

是一个问题 $ x $ ，和

  z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END

.

是一个问题，它分配 $ x + y $ 到 $ z $ 。

功能可以在循环中计算（使用合理的输入/输出惯例）IFF它是原始递归。因此，如果您只允许迭代数量的循环是在循环之前的一些变量的值，那么结果函数将是原始递归，而且，只能计算每个原始递归函数使用此类循环。

Answer 2

这条线是非常自我描述的。不过，让我解释一下。 for 循环在特定的值范围内工作。例如：当你迭代一个数组时，你有意或无意地知道了 length 该数组的，这意味着您知道编号。您的循环将执行的迭代次数。

看一下下面的伪代码：

FRUITS = ["APPLE", "BANANA", "MANGO"]

FOR FRUIT OF FRUITS
    PRINT FRUIT

上面， for 循环将运行 3 times, ，因此你知道没有。在你开始迭代之前。

我希望你能很好地理解这句话。