1.2 图灵机\ 演草纸 演草纸包含k条带,每条带均由单向无限延伸的很多单元构成,每个单元能够存储称为机器的字母表的有限集Γ中的一个符号.每条带均有一个带头,它具有在带上每次读或写一个符号的能力.机器的计算划分为一系列离散的时间步骤,带头在每个步骤中能够向左或向右移动一个单元. 机器的第一条带是输入带,其带头只能从该带上读取符号而不能写符号,因此这是一条只读带.另外的k-1条读写带称为工作带,其中最后一条带是输出带,机器在计算终止前把最终计算结果写在输出带上. 图灵机还允许使用随机访问存储器.然