RAM的变形与简化 (1)实随机存取机RRAM; (2)直线式程序; (3)位式计算; (4)位向量计算; (5)判定数; (6代数计算树ACT; (7)代数判定树 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 RAM的变形与简化 ◼ (1)实随机存取机RRAM； ◼ (2)直线式程序； ◼ (3)位式计算； ◼ (4)位向量计算； ◼ (5)判定数； ◼ (6)代数计算树ACT； ◼ (7)代数判定树
图林机的构造 图林机( Turing Machine是英国数学家 Turing在 1936年提出的计算模型,被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造: 输入带 磁头 输入带被视为右无穷,并被划分为一个个 有限单元用于存放符号(带符号 控制器有限控制器由有限个状态构成。 磁头可左右移动,读写带符号 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 图林机的构造 ◼ 图林机(Turing Machine)是英国数学家Turing在 1936年提出的计算模型，被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造： …… 输入带 有限 控制器 磁头 输入带被视为右无穷，并被划分为一个个 单元用于存放符号(带符号)。 有限控制器由有限个状态构成。 磁头可左右移动，读写带符号
TM的数学描述 M=(Q,T,L,δ,b,q,qr) 其中: Q是有限状态的集合; ■T是有限个带符号的集合; ■IcT,是输入符号的集合; 6:Q×T→Q×T×{L,R}为转移函数; ■b是唯一的空白符,b∈T-1; q0和q分别为初始状态和终止状态。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 TM的数学描述 ◼ Q是有限状态的集合； ◼ T是有限个带符号的集合； ◼ I T，是输入符号的集合； ◼ δ：Q×T→Q×T×{L, R}为转移函数； ◼ b是唯一的空白符，b∈T – I； ◼ q0和qf分别为初始状态和终止状态。 M = (Q, T, I, δ, b, q0 , qf ) 其中：