|
|
[计算问题的化约]
从前有一个很古老的民族，他们商品的计量方式很特别，没有计算器，只有豆子。怎么算呢? 例如11x15=?
是这样算的，取出11个豆子作为除数，取出15个豆子作为乘数(取法任意)，做一个对应的乘除法，左边的豆子每次减半，右边的豆子每次倍增。
(11,15) 起始状态
(11除以2得到5，乘法15x2=30)
( 5除以2得到2，乘法30x2=60)
( 2除以2得到1，乘法60x2=120)
然后除法算到1就停止了。找到除法过程中，左边被除数是奇数的(11,5,1)，把右边的乘数结果加起来，也就是15+30+120=165，正好使11x15！
这是巧合吗? 不是，这就是最古老的二进制运算！11x15=? 相当于把11写成2进制数字11=1011，二进制的”1”项，其实就是除2得到余数1的项，也就是奇数。那么11x15=2^0*15+2^1*15+2^3*15，于是就得到了右边的倍增加和结果。
因为他们没有抽象化的数学符号，无法列示计算，所以找到了计算的本质方法: 二元关系和判定。10进制的乘法式子，九九表，同样可以用二进制演算得到，二元关系运算是所有运算的基础，所有的可计算问题都可以表达成二元运算的递归形式，只要确定起始条件和终止条件就可以了，这就是一个状态机问题。二元关系表示为具体的形式，可以是”01”，”有无”，”奇偶”，”是否是质数”，”大于小于”，”等于不等于”，等等，都是最基础的判定问题。所有的可计算问题，都可以归约为一系列的判定问题。
因此，计算科学的核心也就是:
”01”，”有多少”，”能否推出”----累加问题，数值算法问题，函数演算问题，组合数学问题。
”有无”，”真假”------存在性问题，数理逻辑问题，代数系统问题
”奇偶”， ”是否是质数”------数论问题
”大于小于”，”等于不等于”，””包含不包含”------集合论的序数问题和关系运算问题，图论问题
以上几点加在一起就是关于逻辑和离散的数学理论了。 至于实现的手段和效能，那就是数据结构和算法讨论的问题了，数学是抽象的，和实现无关。而问题能否表示，就是形式语言的问题了----元语言。
这就是计算的实质。
[自然数和序数]
如果说数学分析和泛函分析是建立在实数以及扩充的复数基础之上的，那么计算数学就是建立在更基础的前提上: 自然数和序数。那么所有的计算，因为都可以化简为二进制运算，所以计算本身就变成了取反和判定而已。判定的实现，其形式表现为条件的划分，也就是程序设计里面的顺序循环分支的区别。因此，所有的算法，所有的计算，通过分析，都可以变成一个可数的代数系统：也就是二元关系为元素的一个递归描述。计算科学的一切，都在于此。因为计算就是判定，任何非判定的问题，辩证的问题，用计算机来实现，都不会取得很理想的判定效果，计算机只是退化成了一个累加器而已。只要是可以表示成形而上学的问题的，就是可判定问题；凡是可以写出递归关系的，就是可计算问题。
那么，计算的基本要素是什么呢? 也就是最基本的不变量，或者说具有常量意义的元素----单位元。整数集合代数构成的群，加法群单位元是0，乘法群的单位元是1；对于多项式而言，单位元是一个不可化约式；对于更复杂数字运算而言，基本元素不止单位元那么简单，它有很多个基本要素----积分/微分不变量是自然对数e，线性映射/变换的基本要素是单位矩阵I，整数算法的基本要素是所有的质数，复杂有联系系统的基本要素是汉密尔顿图，等等。当我们用一个代数系统来表示问题的时候，总是希望把它最后化解为一个一个的基本问题，就好像我有一个锤子我就把问题化成一个一个钉子一样。只要这种化解能成立，那么问题的形式化表述就有了，剩下的解答只是一个运算过程而已。
因此，基本的数学问题，必然是讨论实数/自然数的性质，而基本的数学问题必然集中于集合论和数论，也使得所有的问题都可以化约成集合论的问题和数论的问题。
[单位元的思想]
公理化数学体系的根本思想: 单位元素。
如果我有一个锤子，那么我就试图把所有的问题变成钉子。那么钉子就是最基本的问题和假设，而计算的过程就是把我所见的材料变成钉子的过程----而锤子锤钉子的过程是如此的简单，只是作为最后一步得出结果而已。钉子就是单位元，就是基本的运算因子。
二次方程，最简单的形式是X^2=p(p>=0)，那么非其次的呢? Ax^2+Bx+C=0，我通过配方法化成一个X’^2=0的形式就可以了，解出来以后做一个形式化的代换，就得到了原方程的解。概率论里面研究符合抽样规律N(0,1)的平稳高斯过程，那么一般的高斯过程，同样化简为某种形式的单位高斯白噪。
首先构造一些最基本的表述对象，然后设定一些最基础的显而易见的"公设"，从而推导出整个公理化的理论体系。利用这个体系解决问题，说白了就是把所有的问题都通过一些列定义和定理做反向推演，最后归约成基本的问题的不同参数输入和组合的形式。无穷的问题，通过归约化为递归的问题。可计算的问题就是可递归的问题。所有的问题都被归约成一系列相同自问题的递归组合。解决问题的方式变成了用基础元素去重构它，就是锤子和钉子的关系。 |
|
IP卡
狗仔卡
发表于 2010-5-27 18:17
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主