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