简介

可计算问题：

设函数f的定义域是D, 值域是R，如果存在一种算法，对D中任意给定的x，都能计算出f(x) 的值， 则称函数f是可计算的。

图灵机的组成

     一跳存储带

                双向无限延长

                上面有一个个的小方格

                每个小方格可存储一个数字/字母

     一个控制器  

            包含一个读写头， 可读/写/更改存储带上每一个的字母/数字

            可以接受设定好的程序语句

            可以存储当前自身的状态

            可以变换自身的状态

            可以沿着存储带一格一格地左移/右移

---------------------------------------------------------------------

准备：

1.存储带上符号初始化

2. 控制器设置好自身当前状态

3. 控制器置于起始位置

4.准备好工作程序

***************************************************************

工作内容：

1. 读写头读出存储带上当前方格中的字母/数字

2.根据自身当前状态和所读到的字符， 找到相应的程序语句

3.根据相应程序语句，做以下三个动作：

        在当前存储带方格上写入对应的字母/数字

        变更自身状态至新状态

        读写头向左或者向右移动一步