图灵机
图灵机提供了简单又强大的数学计算模型
起因是因为德国科学家的一个问题;
是否存在一种算法,输入正式逻辑语句,输出准确的"是"或者"否" 答案?
如果这样的算法存在,那么可以回答比如"是否有一个数字大于所有数字"
1935年美国科学家开发了一种"Lambda算子"的数学表达系统, 证明这种算法不存在, 但是它的计算非常复杂难以理解
同时在大西洋另一边,提出了图灵机:
假设有无限长的纸带, 纸带可以存储符号.
TU 还有一个读写头NE, 读写纸带: 第二列
还有一个状态变量, 保存当前状态: 第一列
还有一组规则描述机器做什么: 第三列
读写头读取数据后, 或者改变状态,或者把读写头右移一格
举例:
让图灵机读取一个以0结尾的字符串,并计算1出现的次数是不是偶数次,如果是,写一个1
首先要定义"图灵机"的规则:
01 如果当前状态是"偶数",当前符号是1.那么把状态更新为"奇数", 把读写头向右移动.
02 如果当前状态为偶数, 当前符号是0,意味着到了字符结尾, 那么在纸带上写一个1, 并且把状态改成, 停机(Halt)
还需处理状态为奇数的情况:
奇数 + 1 时 和 奇数 + 0 时
定好机器的起始状态: 这里定成"偶数"
机器起始状态为"偶数",看到的第一个数是1,符号第一条规则, 机器状态变为"奇数" ,读写头向右移动.
然后看到1, 此时机器为"奇数"状态,所有执行第三条规则.机器状态变成"偶数",读写头向右移动.
图灵机证明: 如果有足够的内存和时间, 可以执行任何计算.
它是一台通用计算机, 当然效率很低.但是理论可行.
图灵完备
图灵机计算 “停机问题”:
给定图灵机描述和输入纸带,是否有算法可以确定, 机器会永远算下去还是到某一点会停机?
输入 110 , 图灵机会停机
有没有办法, 有些问题在不计算的情况下知道是否有结果. 比如计算一个运行好多年的程序是否会有结果?
图灵通过一个巧妙的逻辑矛盾证明了停机问题是无法解决的.
如果有个问题, H 无法判断是否会停机, 那么"停机问题"无法解决
于是设计了另外一个机器 新H , 和 H相反.
如果H说程序会 停机 , 那么新H会永远运行.
如果H说会停机, 那么新H停止运行.
在 新H上加一个分离器, 让机器只接受一个输入
把 新H的输出 作为自己的输入, 这个机器 叫 “异魔”
意味着在问H, 当异魔的输入是自己时会怎么样?
如果H说异魔会停机, 那么异魔会永远运行下去.
如果H说异魔不会停机, 那么异魔停止运行.
这是一个逻辑矛盾,是一个悖论, 没有答案.
刚开始证明, 图灵机可以进行任何计算, " 停机问题"证明, 不是所有的问题都可以用计算解决.
长话短说: 丘奇和图灵证明了计算机的能力有极限.
1950年图灵设想未来的计算机和人类的智力难分上下, 这个领域很新, 直到1956年才有"人工智能"的名字, 并且提出: 如果计算机能欺骗人类相信它是人类,才算智能. 后来叫做"图灵测试", 现在叫做"公开全自动图灵测试, 用于区分人类和计算机",简称"验证码"
