|
|
楼主 |
发表于 2008-3-23 22:19:00
|
显示全部楼层
Re:虚拟机和图灵机原理:专为程序员写的!一看就懂!
普适（万能）图灵机
引子
严格地说，ENIAC不是“1台”图灵机，而是“若干台”图灵机。
为了让ENIAC完成不同的任务，工作人员们必须改变它的电路结构。。。
即，ENIAC的每一个电路结构，都是1个不同的图灵机。
我们回到上面的图灵机的函数表达式中，继续我们的数学讨论。
回想一下，我们说：
一台编码为 n 的图灵机的行为，可以表示为：
T n ( m ) == p
请注意，这里的“T n”中的“ n ”也是一个变量！
故上式也可以看成是 n, m 这两个变量，到 结果 p 的映射。即，
( n , m ) --> p
实际上也只不过是表达式的书写形式变了
我们举个具体的例子来说明，
比方说，假如在某个编码规范下， 0x45454545代表加法器，0x8888ffff1111代表减法器，
0x123456789abcdefedcba87654321代表圆周率计算器，等等......
加法器 T 45454545 ( m ) == p 其实，也可以记作：
( 0x45454545, m ) --> p
减法器 T 888899991111 ( m ) == p 也可以记作：
( 0x8888ffff1111, m ) --> p
而理论上有无数台图灵机，所以，编码为 n 的图灵机，可以表示为：
( n, m ) --> p
！！问题：上式中的“n”“m”代表什么？你没有忘记吧？
----上面的 n 代表某种编码规范下的图灵机(处理器)代码，m 代表纸带(内存)中的数据。
他们是不同的概念。打个比方， n 就类似于程序代码，m就类似于程序数据。
图灵机的缺点
还记得吗？每一台特定的图灵机 T n1 ，只能完成一个特定的功能，比如 加法。
如果需要完成其他功能，就需要更换另一台图灵机 T n2 ,
比如ENIAC，为了作不同的计算就需要修改电路结构。
那么这就相当麻烦，成本也很大。。。
好吧，回到正题。
我们说，某台图灵机 n ，可以表示为 ( n, m ) --> p 这个映射。
请问大家：图灵机是干什么用的阿？
----做数学计算用的。
我们知道，图灵机可以计算很多东西，比如2个数字的加法，减法，
某个函数，圆周率，等等，各种各样的图灵机，可以代替人脑完成各种各样的运算。
那么，同样存在某台图灵机，可以完成“ ( n, m ) --> p ” 这个计算！！
这台图灵机，叫做“普适(万能)图灵机”，记作 " U " 。而且同样也有一个编码！ |
|
发表于 2008-3-23 04:12:00
