多带图灵机 非确定性的图灵机 ·在计算的任何时刻机器可以在多种可能 灵机相似,M 性中选择一种继续进行【永远选择正确 只是有多 的,可以理解为全部分支都计算完后选 个带子每 出正确的】它的计算是一课树,不同的分 个带子都 枝对应着机器不同的可能性如果某个计 有自己的 算分枝导致接受状态,则接受该输入.与多 读写头,用 带图灵机相同的是,它的计算能力与普通 于读和写 图灵机也是一样的当然他的计算速度就 不一样了 清华大学宋域恒 请华大学宋恒 现代计算机模型 随机存取机RAM CPU 类似现代计算机,有一个只读输入 运算器控制器出 只写输出带、指令计数器、内存储器 其零号寄存器用作累加器,内存不能 存储器 写,每个内存可以存放任意大的整数 有12条指令:load、 store、add、su mult、div、read、 write、jump、jgtz 外存设备 Izero、halt 清华大学末斌恒 请华大学宋恒 练习 随机存取存储程序机RASP ·利用RAM设计一个计算多项式函数求值 ·除了程序可以存储在存储器中并可以修 的程序:其中多项式为<a0al,an>,变 改,其它与RAM都一样 量为 ·考虑问题:程序是什么?输入是什么? 复杂度是多少? 清华大学末域恒 请华大学宋3 清华大学 宋斌恒 13 多带图灵机, • 和普通图 灵机相似, 只是有多 个带子,每 个带子都 有自己的 读写头,用 于读和写. 如图 清华大学 宋斌恒 14 非确定性的图灵机 • 在计算的任何时刻,机器可以在多种可能 性中选择一种继续进行【永远选择正确 的，可以理解为全部分支都计算完后选 出正确的】.它的计算是一课树,不同的分 枝对应着机器不同的可能性.如果某个计 算分枝导致接受状态,则接受该输入.与多 带图灵机相同的是,它的计算能力与普通 图灵机也是一样的.当然他的计算速度就 不一样了。 清华大学 宋斌恒 15 现代计算机模型 清华大学 宋斌恒 16 随机存取机RAM • 类似现代计算机，有一个只读输入带、 只写输出带、指令计数器、内存储器、 其零号寄存器用作累加器，内存不能 写，每个内存可以存放任意大的整数。 有12条指令：load、store、add、sub、 mult、div、read、write、jump、jgtz、 jzero、halt。 清华大学 宋斌恒 17 练习 • 利用RAM设计一个计算多项式函数求值 的程序：其中多项式为<a0,a1,…,an>，变 量为x。 • 考虑问题：程序是什么？输入是什么？ 复杂度是多少？ 清华大学 宋斌恒 18 随机存取存储程序机RASP • 除了程序可以存储在存储器中并可以修 改，其它与RAM都一样