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))也不是很理解。 还请各位大侠多多指教! |