离散数学在计算机中的应用

对于一个数, 如果存在一个A L-GOL (或PL/1, 或FORTRAN等等) 程序P, 当给出任一非负整数 (作为输入) , 经过有限但可任意长的时间, 它恰好输出的十进制展开式的第个数字后停机, 则称是可计算的。所谓数是可计算的, 意思指存在程序P能用来确定到任意精确度, 或产生的展开式的任意一位数字。反之, 则称数是不可计算的, 例如, 是可计算的, 因为存在以下计算它的过程。

接下来我们将用基数理论来证明如下定理。

定理:区间 (0, 1) 中存在不可计算的数.

现在我们引入一些概念和引理:

定义1度量集合A大小的数叫基数, 并记为。

定义2 N的初始段是前个 (包括0个) 自然数的集合或N自身。

定义3如果有从N的初始段到A的双射函数, 那么集合A是有限的, 具有基数, 如果集合A不是有限的, 那么它是无限的。

引理1:自然数集合N是无限的。

对于有限集的基数, 我们把称作N的初始段的集合作为”标准集合”, 双射函数做工具, 对它们进行比较.当且仅当从到集合A存在一双射函数时, 称集合A具有基数, 记为, 对于无限集, 我们引入如下定义。

定义4如果存在一个从N到A的双射函数, 那么集合A的基数是, 记为。

显然, 存在从N到N的双射函数, 所以,

定义5如果存在从N的初始段到集合A的双射函数, 则称集合A是可数的或可列的;如果, 则称集合A是可数无限的;如果集合A不是可数的, 则称集合A是不可数的或不可数无限的。

定义6设A是一集合, A的枚举是从N的初始段到A的一个满射函数, 如果也单射的, 那么是一个无重复枚举;如果不是单射的, 那么是重复枚举。

引理2:一个集合A是可数的当且仅当存在A的枚举。

引理3:实数的子集不是可数无限。

由 (引理3) 我们知道不是所有无限集都是可数无限的, 这就需要我们引入新的无限集基数。

定义7如果有从[0, 1]到集合A的双射函数, 那么A的基数是c, 记为。

接下来我们证明 (0, 1) 中存在不可计算的数。所用的证明方法叫基数论证, 是非构造性的, 将涉及以下集合:

:ALGOL的字符集合,

A:所有ALGOL程序集合,

C:计算 (0, 1) 中某个数的ALGOL程序集合,

S:在 (0, 1) 中能被某ALGOL程序计算的数的集合。

因为是一有限集合, 字母表上非空串的集合有基数, 即。以为任何A L G O L程序是上的有限串, 所以

因为C是A的真子集, 所以

任一程序P至多能计算S的一个元素的数字, 但不同程序能计算同样数的数字。这得出

这样, 我们有

由引理3我们知道| (0, 1) |=c, 又。因此, 。即在 (0, 1) 中某些数是不可计算的。定理得证。

摘要：随着离散数学的不断发展和完善, 它在现代科学中的重要性日益增加, 特别在计算机中的应用优为突出。本文我们将用离散数学中的基数理论来解决计算机中的一个输出问题。

关键词：基数,枚举,初始段

参考文献

[1] 　Tremblay　JP, Manohar　R.　Discrete Mathermatic　Saructures　With Applicatiaons　to　Computer　Science.New　York:　MeGrew-Hill　Book Company, 1975.

[2] 　Arthur　Gill, 　Applied　Algebra　for Computer　Sciences.Englewood　cliffs, NJ:Prentice-Hall, Inc, 1976.

[3] 　Liu　CL.Elements　of　Discrete　Mathematic.New　york:　McGraw-Hill　Book Ccmpany, 1970.