可计算问题：
设函数f的定义域是D, 值域是R，如果存在一种算法，对D中任意给定的x，都能计算出f(x) 的值， 则称函数f是可计算的。
图灵机的组成
一跳存储带
双向无限延长
上面有一个个的小方格
每个小方格可存储一个数字/字母
一个控制器
包含一个读写头， 可读/写/更改存储带上每一个的字母/数字
可以接受设定好的程序语句
可以存储当前自身的状态
可以变换自身的状态
可以沿着存储带一格一格地左移/右移
---------------------------------------------------------------------
准备：
1.存储带上符号初始化
2. 控制器设置好自身当前状态
3. 控制器置于起始位置
4.准备好工作程序
***************************************************************
工作内容：
1. 读写头读出存储带上当前方格中的字母/数字
2.根据自身当前状态和所读到的字符， 找到相应的程序语句
3.根据相应程序语句，做以下三个动作：
在当前存储带方格上写入对应的字母/数字
变更自身状态至新状态
读写头向左或者向右移动一步
网友评论