TAOCP第一章 - 集合论表述算法的一些困惑

fxb248 2013-09-13
TAOCP中关于集合论描述算法如下:
我们定义一个计算方法为一个四元组(Q, I, Ω, f),每个字母的意义为:
Q: 表示计算状态的集合
I: 表示输入的集合
Ω: 表示输出的集合
f: 表示计算规则的集合
满足如下约束:
I, Ω都是Q的子集, f:Q → Q
存在属于Ω的元素q, f(q)=q

对集合I中的每一个输入x定义一个序列:X(0),X(1),...,满足如下规则:
X(0)=X
X(k+1) = f(X(k))

如果k是使在Ω中为最小的整数,那么就说这个计算序列在k步中终止,而且在此种情况下说x产生了输出。

这里对于“存在属于Ω的元素q, f(q)=q”不是很理解。f本身是一个规则,相当于函数,元素经过它计算后肯定仍是属于Q的,也就是上面的“f:Q → Q”。
但是对于Ω中的元素q,我觉得经过计算,假设结果是元素y, 那么 f(q)=y, 且y是属于集合Ω的。我的理解是这样的,所以我对f(q)=q很不理解。
还有,对于用集合论描述的算法E(也就是欧几里得算法), 我对f((n))也不是很理解。
还请各位大侠多多指教!

相关讨论

相关资源推荐

Global site tag (gtag.js) - Google Analytics